Premium
Coverings and matchings in r ‐partite hypergraphs
Author(s) -
Altner Douglas S.,
Brooks J. Paul
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20459
Subject(s) - hypergraph , combinatorics , conjecture , mathematics , cardinality (data modeling) , vertex (graph theory) , matching (statistics) , integer (computer science) , integer programming , bipartite graph , cover (algebra) , discrete mathematics , graph , computer science , algorithm , mechanical engineering , statistics , engineering , data mining , programming language
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. © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012