Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-167 | 9th November 2020 20:18

Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture



A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this conjecture, and also studied its implied fractional versions. We establish the fractional version of the Aharoni-Zerbib conjecture up to lower order terms. Specifically, we give a factor $t/2+ O(\sqrt{t \log t})$ approximation based on LP rounding for an algorithmic version of the hypergraph Tur\'{a}n problem (AHTP). The objective in AHTP is to pick the smallest collection of $(t-1)$-sized subsets of vertices of an input $t$-uniform hypergraph such that every hyperedge contains one of these subsets.

Aharoni and Zerbib also posed whether Tuza's conjecture and its hypergraph versions could follow from non-trivial duality gaps between vertex covers and matchings on hypergraphs that exclude certain sub-hypergraphs, for instance, a ``tent" structure that cannot occur in the incidence of triangles and edges. We give a strong negative answer to this question, by exhibiting tent-free hypergraphs, and indeed $\mathcal{F}$-free hypergraphs for any finite family $\mathcal{F}$ of excluded sub-hypergraphs, whose vertex covers must include almost all the vertices.

The algorithmic questions arising in the above study can be phrased as instances of vertex cover on \emph{simple} hypergraphs, whose hyperedges can pairwise share at most one vertex. We prove that the trivial factor $t$ approximation for vertex cover is hard to improve for simple $t$-uniform hypergraphs. However, for set cover on simple $n$-vertex hypergraphs, the greedy algorithm achieves a factor $(\ln n)/2$, better than the optimal $\ln n$ factor for general hypergraphs.

ISSN 1433-8092 | Imprint