How many matchings cover the nodes of a graph?

• 成果类型: Article
• 署名作者: Ferhat, Dehia Ait; Kiraly, Zoltan; Sebo, Andras; Stauffer, Gautier
• 署名单位: Mentor Graphics Inc; Eotvos Lorand University; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University of Lausanne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01804-9
• 发表日期: 2024
• 页码: 271-284
• 关键词: Existence; packings

摘要

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'.