Document Open Access Logo

Hitting Set for Hypergraphs of Low VC-dimension

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.23.pdf
  • Filesize: 0.64 MB
  • 18 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting Set for Hypergraphs of Low VC-dimension. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.23

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önnimann 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.

Subject Classification

Keywords
  • hitting set
  • VC-dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. In 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, page 271, 2014. URL: http://dx.doi.org/10.1145/2582112.2582152.
  2. Noga Alon, Shay Moran, and Amir Yehudayoff. Sign rank, VC dimension and spectral gaps. Electronic Colloquium on Computational Complexity (ECCC), 21:135, 2014. URL: http://eccc.hpi-web.de/report/2014/135.
  3. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms, 2(2):153-177, 2006. URL: http://dx.doi.org/10.1145/1150334.1150336.
  4. Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis Dimension. J. ACM, 36(4):929-965, October 1989. URL: http://dx.doi.org/10.1145/76359.76371.
  5. Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, and Stéphan Thomassé. Identifying codes in hereditary classes of graphs and vc-dimension. CoRR, abs/1407.5833, 2014. URL: http://arxiv.org/abs/1407.5833.
  6. Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Olivier Bousquet, Ulrike von Luxburg, and Gunnar Rätsch, editors, Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2 - 14, 2003, Tübingen, Germany, August 4 - 16, 2003, Revised Lectures, pages 169-207. Springer, Berlin, Heidelberg, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28650-9_8.
  7. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry, 14(4):463-479, 1995. URL: http://dx.doi.org/10.1007/BF02570718.
  8. Bernard Chazelle. The discrepancy method - randomness and complexity. Cambridge University Press, 2001. Google Scholar
  9. Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43-58, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1273-8.
  10. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An o(2^o(k)n^3) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst., 41(3):479-492, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1345-z.
  11. Michael Dom, MichaelR. Fellows, and FrancesA. Rosamond. Parameterized complexity of stabbing rectangles and squares in the plane. In Sandip Das and Ryuhei Uehara, editors, WALCOM: Algorithms and Computation, volume 5431 of Lecture Notes in Computer Science, pages 298-309. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-00202-1_26.
  12. Rod G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, New York, 1999. Google Scholar
  13. P. Erdős. Personal reminiscences and remarks on the mathematical work of Tibor Gallai. Combinatorica, 2(3):207-212, 1982. URL: http://dx.doi.org/10.1007/BF02579228.
  14. Guy Even, Dror Rawitz, and Shimon Shahar. Hitting sets when the VC-dimension is small. Inf. Process. Lett., 95(2):358-362, 2005. URL: http://dx.doi.org/10.1016/j.ipl.2005.03.010.
  15. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2006. Google Scholar
  16. Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281-309, 2006. URL: http://dx.doi.org/10.1137/S0097539702419649.
  17. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  18. Panos Giannopoulos, Christian Knauer, and Sue Whitesides. Parameterized complexity of geometric problems. Comput. J., 51(3):372-384, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm053.
  19. Magdalene Grantson and Christos Levcopoulos. Covering a set of points with a minimum number of lines. In Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, pages 6-17, 2006. URL: http://dx.doi.org/10.1007/11758471_4.
  20. Jiong Guo and Rolf Niedermeier. Exact algorithms and applications for tree-like weighted set cover. J. Discrete Algorithms, 4(4):608-622, 2006. URL: http://dx.doi.org/10.1016/j.jda.2005.07.005.
  21. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of generalized vertex cover problems. In Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, pages 36-48, 2005. URL: http://dx.doi.org/10.1007/11534273_5.
  22. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG, 3(1):65-85, 2012. URL: http://jocg.org/index.php/jocg/article/view/77.
  23. David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. URL: http://dx.doi.org/10.1007/BF02187876.
  24. Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization. Inf. Comput., 231:109-116, 2013. URL: http://dx.doi.org/10.1016/j.ic.2013.08.007.
  25. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, pages 462-473, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22006-7_39.
  26. James King (http://cstheory.stackexchange.com/users james king). Parameterized complexity of hitting set in finite vc-dimension. Theoretical Computer Science Stack Exchange. URL: http://cstheory.stackexchange.com/q/182.
  27. Stefan Langerman and Pat Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. URL: http://dx.doi.org/10.1007/s00454-004-1108-4.
  28. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41(5):960-981, September 1994. URL: http://dx.doi.org/10.1145/185675.306789.
  29. Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, pages 154-165, 2006. URL: http://dx.doi.org/10.1007/11847250_14.
  30. Dániel Marx. Can you beat treewidth? In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS'07, pages 169-179, Washington, DC, USA, 2007. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2007.18.
  31. Jiri Matousek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. Google Scholar
  32. Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff. Teaching and compressing for low vc-dimension. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015. Google Scholar
  33. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. URL: http://dx.doi.org/10.1007/s00454-010-9285-9.
  34. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  35. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, pages 694-705, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_62.
  36. Venkatesh Raman and Saket Saurabh. Short cycles make w-hard problems hard: Fpt algorithms for w-hard problems with no short cycles. Algorithmica, 52(2):203-225, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9148-9.
  37. Norbert Sauer. On the density of families of sets. J. Comb. Theory, Ser. A, 13(1):145-147, 1972. URL: http://dx.doi.org/10.1016/0097-3165(72)90019-2.
  38. Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in biclique-free graphs. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 802-812, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33090-2_69.
  39. Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability &Its Applications, 16(2):264-280, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact