2006.01.24 | Gerth Stølting Brodal

Title: Simultaneous Matchings
Abstract:
Given a bipartite graph $G=(X \\dotcup D, E\\subseteq X\\times D)$,
an $X$-perfect matching is a matching in $G$ that covers
every node in $X$. In this talk 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 \\subseteq 2^X$ of $k$ subsets of $X$,
find a subset $M\\subseteq E$ of the edges such that for each
$C\\in F$,the edge set $M\\cap (C\\times 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 $2^k poly(k,|X\\cup D|)$ time.

This is joint work with Khaled Elbassioni, Martin Kutz and Meena Mahajan,
to be presented at ISAAC 2005. The paper can be downloaded from
www.brics.dk/~irit/pub/SM.ps