Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture

DOI10.1002/RSA.21086MaRDI QIDQ6077050zbMATH OpenOpenAlexWikidataFDO

Authors N. Bansal, David G. Harris

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.07097

zbMATH Keywords

hypergraphiterative roundingmatching

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: A classic conjecture of F"{u}redi, Kahn and Seymour (1993) states that given any hypergraph with non-negative edge weights $w(e)$, there exists a matching $M$ such that $su{m}_{einM}(|e|-1+1/|e|),w(e)geq{w}^{\ast }$, where $w^{\ast }$ is the value of an optimum fractional matching. We show the conjecture is true for rank-3 hypergraphs, and is achieved by a natural iterated rounding algorithm. While the general conjecture remains open, we give several new improved bounds. In particular, we show that the iterated rounding algorithm gives $su{m}_{einM}(|e|-delta(e)),w(e)geq{w}^{\ast }$, where $delta(e)=|e|/(|e{|}^2+|e|-1)$, improving upon the baseline guarantee of $su{m}_{einM}|e|,w(e)geq{w}^{\ast }$.

Recommendations

• On matchings in hypergraphs
• On a criterion for matchability in hypergraphs
• On a hypergraph matching problem
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• On the matching polynomial of hypergraphs
• Matchings in hypergraphs and Castelnuovo-Mumford regularity
• On Erdős' extremal problem on matchings in hypergraphs
• Matchings in hypergraphs of large minimum degree
• Near perfect matchings in \(k\)-uniform hypergraphs
• An algorithmic framework for the matching problem in some hypergraphs

Cites work

• Algorithms to approximate column-sparse packing problems
• An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On linear and semidefinite programming relaxations for hypergraph matching
• On the fractional matching polytope of a hypergraph

Cited in

(2)

• Weighted fractional and integral k-matching in hypergraphs
• Fractional v. integral covers in hypergraphs of bounded edge size

This page was built for publication: Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6077050)