Hitting Set for hypergraphs of low VC-dimension

DOI10.4230/LIPICS.ESA.2016.23MaRDI QIDQ4606292zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, László Kozma, Shay Moran, N. S. Narayanaswamy

Publication date 2 March 2018

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

zbMATH Keywords

VC-dimensionhitting set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Hypergraphs (05C65)

Abstract: We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Br"onnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.

Recommendations

• Hitting sets when the VC-dimension is small
• Finding small hitting sets in infinite range spaces of bounded VC-dimension
• On the VC-dimension of uniform hypergraphs
• Hitting sets online and vertex ranking
• The VC-dimension of set systems defined by graphs
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Erdos-Hajnal conjecture for graphs with bounded VC-dimension
• scientific article; zbMATH DE number 1500656
• 3-\textsc{hitting set} on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension

Cited in

(11)

• Fractional covers of hypergraphs with bounded multi-intersection
• On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
• Finding and counting permutations via CSPs
• On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
• Hitting sets when the VC-dimension is small
• An approximation algorithm for submodular hitting set problem with linear penalties
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• scientific article; zbMATH DE number 398939 (Why is no real title available?)
• Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
• scientific article; zbMATH DE number 1500656 (Why is no real title available?)
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)

This page was built for publication: Hitting Set for hypergraphs of low VC-dimension

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