@inproceedings{8f66fde936b943a89183c114f555311b,

title = "Simultaneous matchings",

abstract = "Given a bipartite graph G = (X ∪ D, E ⊆ X × D), an X-perfect matching is a matching in G that covers every node in X. In this paper we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F ⊆ 2X of k subsets of X, find a subset M ⊆ E of the edges such that for each C ∈ F, the edge set M ∩ (C × D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k = O(1) and even APX-complete already for k = 2. On the positive side, we show that a 2/(k + 1)-approximation can be found in 2kpoly(k, |X ∪ D|) time.",

author = "Khaled Elbassioni and Irit Katriel and Martin Kutz and Meena Mahajan",

year = "2005",

doi = "10.1007/11602613_12",

language = "British English",

isbn = "3540309357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "106--115",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

note = "16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

}