Hitting Set for hypergraphs of low VC-dimension

DOI10.4230/LIPICS.ESA.2016.23zbMATH Open1397.68092arXiv1512.00481OpenAlexW2962684085MaRDI QIDQ4606292FDOQ4606292

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

Publication date: 2 March 2018

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.

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

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

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)

Cited In (12)

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

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)