The ACO Seminar (2020–2021)

We propose an algorithmic version of the hypergraph Turán problem (AHTP): given a $t$-uniform hypergraph $H=(V, E)$, the goal is to find the smallest collection of $(t-1)$-element subsets of V such that every hyperedge $e\in E$ contains one of these subsets. In addition to its inherent combinatorial interest—for instance, the $t=3$ case is connected to Tuza’s famous conjecture on covering triangles of a graph with edges—variants of AHTP arise in recently proposed reductions to fundamental Euclidean clustering problems. AHTP admits a trivial factor t approximation algorithm as it can be cast as an instance of vertex cover on a structured $t$-uniform hypergraph that is a “blown-up” version of H. Our main result is an approximation algorithm with ratio $t/2+o(t)$. The algorithm is based on rounding the natural LP relaxation using a careful combination of thresholding and color coding.

We also present results motivated by structural aspects of the blown-up hypergraph. The blown-up is a simple hypergraph with hyperedges intersecting in at most one element. We prove that vertex cover on simple t-uniform hypergraphs is as hard to approximate as general t-uniform hypergraphs. The blown-up hypergraph further has many forbidden structures, including a “tent” structure for the case $t=3$. Whether a generalization of Tuza’s conjecture could also hold for tent-free $3$-uniform hypergraphs was posed in a recent work. We answer this question in the negative by giving a construction based on combinatorial lines that is tent-free, and yet needs to include most of the vertices in a vertex cover.

Please email Boris Bukh (bbukh ~at~ math) for a password.