  


Coverings and Matchings in rPartite Hypergraphs
D.S. Altner (altnerusna.edu) Abstract: Ryser's conjecture postulates that, for $r$partite hypergraphs, $\tau \leq (r1) \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 NPhard. 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 {\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 $rk$ where $k$ is the smallest positive integer such that $rk$ is a prime power. Keywords: covering, matching, Ryser's conjecture, rpartite hypergraphs, intersecting hypergraphs Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Integer Programming (01 Programming ) Citation: Networks, 59:400410, 2012. Download: Entry Submitted: 06/25/2010 Modify/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  