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.
Citation
Networks, 59:400-410, 2012.