Document Type
Article
Original Publication Date
2012
Journal/Book/Conference Title
Networks
Volume
59
Issue
4
First Page
400
Last Page
410
DOI
10.1002/net.20459
Date of Submission
June 2014
Abstract
Ryser's conjecture postulates that for r -partite hypergraphs, τ ≤ (r - 1)ν where τ is the covering number of the hypergraph and ν is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where r ≤ 5. In this article, we prove several results pertaining to matchings and coverings in r -partite intersecting hypergraphs. First, we prove that finding a minimum cardinality vertex cover for an r -partite intersecting hypergraph is NP-hard. Second, we note Ryser's conjecture for intersecting hypergraphs is easily resolved if a given hypergraph does not contain a particular subhypergraph, which we call a “tornado.” We prove several bounds on the covering number of tornados. Finally, we prove the integrality gap for the standard integer linear programming formulation of the maximum cardinality r -partite hypergraph matching problem is at least r - k where k is the smallest positive integer such that r - k is a prime power.
Rights
Copyright © Wiley This is the peer reviewed version of the following article: Altner, D. S. and Brooks, J. P. (2012), Coverings and matchings in r-partite hypergraphs. Networks, 59: 400–410, which has been published in final form at http://dx.doi.org/10.1002/net.20459 This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for self-archiving.
Is Part Of
VCU Statistical Sciences and Operations Research Faculty Publications