We propose an algorithmic version of the hypergraph Tur\'{a}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 \frac{t simple %DIFAUXCMD 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 hypergraphswas 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 .
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 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 %DIFAUXCMD 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 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 .
R
We propose
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
R
: given a t-uniform hypergraph H=(V,E), the goal is to find
. The objective in AHTP is to pick
R
-element subsets of V
-sized subsets of vertices of an input t-uniform hypergraph
D
e \in E
R
In addition to its inherent combinatorial interest---for instance, the t=3 case is connected to
Aharoni and Zerbib also posed whether
D
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 \frac{t
D
simple
R
hypergraph with hyperedges intersecting in
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
R
element
vertex
R
vertex cover on simple
the trivial factor t approximation for vertex cover is hard to improve for simple
D
hypergraphs is as hard to approximate as general t-uniform
R
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 hypergraphswas 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
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