Matching with optional and required vertices

Question

I'm interested in the problem of deciding whether an input undirected graph $G = (V, E)$ contains a matching, i.e., a subset $E' \subseteq E$ of pairwise disjoint edges, that satisfies an additional requirement of covering a subset $V' \subseteq V$ of the vertices. More precisely, a matching $E'$ covers a subset $V' \subseteq V$ if each vertex of $V'$ has some incident edge in $E'$. For the vertices in $V \setminus V'$ there is no requirement.

Is it in PTIME, given an undirected graph $G = (V, E)$ and vertices $V' \subseteq V$, of deciding whether there is a matching of $G$ that covers $V'$?

Note that this problem is a generalization of the perfect matching problem, which corresponds to the case $V' := V$. Note that there is no reason to expect that a maximum matching would necessarily be the solution.

• Karagounis Z: In a bipartite graph the constraint matrix is Totally Unimodular. I believe that in general graphs it will be a half-integral and that there is a perfect formulation which can be optimized.

Answer 1

The problem is in PTIME by reducing to perfect matching. The argument is from the end of this preprint, but I explained it in a self-contained fashion below for clarity.

We first determine the parity of the number of vertices of $V \setminus V'$ that would be matched in a putative matching covering $V'$. A matching always covers an even number of vertices and it must cover all vertices of $V'$, so the number of matched vertices of $V \setminus V'$ has the same parity as $V'$:

• Case 1: $V'$ is even, so a matching that covers $V'$ covers an even number of vertices of $V \setminus V'$. In this case, we build a graph $G'$ by adding to every vertex $v$ of $V \setminus V'$ a fresh neighbor $v'$, and by connecting the vertices $v'$ thus created in a clique. We claim that $G'$ has a perfect matching iff $G$ has a matching that covers $V'$. In the forward direction, as $G'$ is a supergraph of $G$ and the vertices of $V'$ have no new neighbors in $G'$ relative to $G$, we know that a perfect matching of $G'$ restricted to the edges of $G$ is a matching of $G$ that covers $V'$. In the backward direction, assuming that $G$ has a matching $E'$ that covers $V'$, then $E'$ covers an even number of vertices of $V \setminus V'$. We take the edges connecting the vertices $v$ of $V \setminus V'$ that are unmatched in $E'$ to their fresh vertex $v'$, giving a matching that covers all vertices of $G$ in $G'$. The remaining vertices to cover in $G'$ are the $v'$ corresponding to the $v\in V\setminus V'$ that were covered in $E'$, which are of even number; these $v'$ can be covered by pairing them in an arbitrary way in the clique and selecting the corresponding edges.
• Case 2: $V'$ is odd. The construction of $G'$ is the same except that we add a fresh vertex $z$ to the clique connected to all the other vertices $v'$ of the clique. The reasoning is similar: a perfect matching of $G'$ gives a matching of $G$ that covers $V'$, and conversely a matching of $E'$ that covers $V'$ can be extended using the edges $\{v,v'\}$ for unmatched $v \in V \setminus V'$ and connecting the other $v'$ together with $z$ in the clique (as this is now an even set of vertices).

This reduction is obviously in polynomial time, so we have reduced our problem in polynomial time to the perfect matching problem. This problem is in polynomial time, which concludes.