Name
Abstract | ||
|---|---|---|
Given a bipartite graph G=(X@?@?D,E@?XxD), 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@?2^X of k subsets of X, find a subset M@?E of the edges such that for each C@?F, the edge set M@?(CxD) 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 poly(k,|X@?D|) time. We show also that such an approximation M can be found in time (k+(k2)2^k^-^2)poly(|X@?D|), with the further restriction that each vertex in D has degree at most 2 in M. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jcss.2008.02.001 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
corresponding optimisation problem,decision problem,perfect matchings,constraint programming,hardness of approximation,x-perfect matching,approximation m,subset m,matchings,bipartite graph,np-completeness,k subsets,hardness of approximation.,c-perfect matching,x-perfect matching problem,simultaneous matchings,optimisation,collection f,np completeness | Discrete mathematics,Decision problem,Combinatorics,Vertex (geometry),Hardness of approximation,Generalization,Constraint programming,Bipartite graph,3-dimensional matching,Mathematics,Blossom algorithm | Journal |
Volume | Issue | ISSN |
74 | 5 | Journal of Computer and System Sciences |
Citations | PageRank | References |
9 | 0.52 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kutz | 1 | 99 | 6.83 |
| khaled elbassioni | 2 | 473 | 35.78 |
| Irit Katriel | 3 | 176 | 13.72 |
| Meena Mahajan | 4 | 688 | 56.90 |