Optimization Online


Coverings and Matchings in r-Partite Hypergraphs

D.S. Altner (altner***at***usna.edu)
J.P. Brooks (jpbrooks***at***vcu.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.


Entry Submitted: 06/25/2010
Entry Accepted: 06/25/2010
Entry Last Modified: 03/15/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society