Asset Details
Do you wish to reserve the book?
How many matchings cover the nodes of a graph?
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
How many matchings cover the nodes of a graph?
Do you wish to request the book?
How many matchings cover the nodes of a graph?
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
How many matchings cover the nodes of a graph?
2024
Overview
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
à la Kőnig
:
for
k
≥
2
,
there exist
k
matchings covering every node if and only if for every stable set
S
,
we have
|
S
|
≤
k
·
|
N
(
S
)
|
. 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’.
Publisher
Springer Berlin Heidelberg,Springer,Springer Verlag
