ECCC-Report TR20-167https://eccc.weizmann.ac.il/report/2020/167Comments and Revisions published for TR20-167en-usMon, 09 Nov 2020 20:20:02 +0200
Paper TR20-167
| Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture |
Venkatesan Guruswami,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2020/167A 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.Mon, 09 Nov 2020 20:20:02 +0200https://eccc.weizmann.ac.il/report/2020/167