How many matchings cover the nodes of a graph?

Given an undirected graph, are there k matchings whose union covers all of its nodes, that is, a matching-k-cover? When k = 1, the problem is equivalent to the existence of a perfect matching for which Tutte's celebrated matching theorem (J. Lon. Math. Soc., 1947) provides a `good' characterization. We prove here, when k is greater than one, a `good' characterization a la Konig: for k >= 2, there exist k matchings covering every node if and only if for every stable set S, we have vertical bar S vertical bar <= k .vertical bar N(S)vertical bar. Moreover, somewhat surprisingly, we use only techniques from bipartite matching in the proof, through a simple, polynomial algorithm. A different approach to matching-k-covers has been previously suggested by Wang et al. (Math. Prog., 2014), relying on general matching and using matroid union for matching-matroids, or the Edmonds-Gallai structure theorem. Our approach provides a simpler polynomial algorithm together with an elegant certificate of non-existence when appropriate. Further results, generalizations and interconnections between several problems are then deduced as consequences of the new minimax theorem, with surprisingly simple proofs (again using only the level of difficulty of bipartite matchings). One of the equivalent formulations leads to a solution of weighted minimization for non-negative edge-weights, while the edge-cardinality maximization of matching-2-covers turns out to be already NP-hard. We have arrived at this problem as the line graph special case of a model arising for manufacturing integrated circuits with the technology called 'Directed Self Assembly'.

Automated summary

This paper investigates the existence of k matchings that cover all nodes in a given undirected graph, known as a matching-k-cover problem. When k = 1, the problem is equivalent to finding a perfect matching. For k greater than 1, the paper provides a characterization condition and proves the existence using a simple polynomial algorithm. Surprisingly, the approach only uses bipartite matching techniques. The paper also introduces a new minimax theorem that leads to further results, generalizations, and connections between different problems.