- Coverings and Matchings in r-Partite Hypergraphs D.S. Altner (altnerusna.edu) J.P. Brooks (jpbrooksvcu.edu) Abstract: Ryser's conjecture postulates that, for $r$-partite hypergraphs, $\tau \leq (r-1) \nu$ where $\tau$ is the covering number of the hypergraph and $\nu$ 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 \leq 5$. In this paper, 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 sub-hypergraph, which we call a {\it 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. Keywords: covering, matching, Ryser's conjecture, r-partite hypergraphs, intersecting hypergraphs Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Integer Programming (0-1 Programming ) Citation: Networks, 59:400-410, 2012. Download: Entry Submitted: 06/25/2010Entry Accepted: 06/25/2010Entry Last Modified: 03/15/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.