Document Open Access Logo

On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension

Authors Johannes Blum , Yann Disser , Andreas Emil Feldmann , Siddharth Gupta , Anna Zych-Pawlewicz

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.5.pdf
  • Filesize: 1.47 MB
  • 23 pages

Document Identifiers

Author Details

Johannes Blum
  • Universität Konstanz, Germany
Yann Disser
  • Technische Universität Darmstadt, Germany
Andreas Emil Feldmann
  • Charles University, Prague, Czechia
Siddharth Gupta
  • University of Warwick, Coventry, UK
Anna Zych-Pawlewicz
  • University of Warsaw, Poland

Funding

  • Feldmann, Andreas Emil: Supported by the Czech Science Foundation GAČR (grant #19-27871X).
  • Gupta, Siddharth: Supported by the Engineering and Physical Sciences Research Council (EPSRC) grant no: EP/V007793/1.
  • Zych-Pawlewicz, Anna: This work is part of the project CUTACOMBS that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 714704).

Cite AsGet BibTex

Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, and Anna Zych-Pawlewicz. On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.IPEC.2022.5

Abstract

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system (V,ℱ,ℬ) with two families ℱ,ℬ of subsets of the universe V. The task is to find a hitting set for ℱ that minimizes the maximum number of elements in any of the sets of ℬ. This generalizes several problems that have been studied in the literature. Our focus is on determining the complexity of some of these special cases of Sparse-HS with respect to the sparseness k, which is the optimum number of hitting set elements in any set of ℬ (i.e., the value of the objective function). For the Sparse Vertex Cover (Sparse-VC) problem, the universe is given by the vertex set V of a graph, and ℱ is its edge set. We prove NP-hardness for sparseness k ≥ 2 and polynomial time solvability for k = 1. We also provide a polynomial-time 2-approximation algorithm for any k. A special case of Sparse-VC is Fair Vertex Cover (Fair-VC), where the family ℬ is given by vertex neighbourhoods. For this problem it was open whether it is FPT (or even XP) parameterized by the sparseness k. We answer this question in the negative, by proving NP-hardness for constant k. We also provide a polynomial-time (2-1/k)-approximation algorithm for Fair-VC, which is better than any approximation algorithm possible for Sparse-VC or the Vertex Cover problem (under the Unique Games Conjecture). We then switch to a different set of problems derived from Sparse-HS related to the highway dimension, which is a graph parameter modelling transportation networks. In recent years a growing literature has shown interesting algorithms for graphs of low highway dimension. To exploit the structure of such graphs, most of them compute solutions to the r-Shortest Path Cover (r-SPC) problem, where r > 0, ℱ contains all shortest paths of length between r and 2r, and ℬ contains all balls of radius 2r. It is known that there is an XP algorithm that computes solutions to r-SPC of sparseness at most h if the input graph has highway dimension h. However it was not known whether a corresponding FPT algorithm exists as well. We prove that r-SPC and also the related r-Highway Dimension (r-HD) problem, which can be used to formally define the highway dimension of a graph, are both W[1]-hard. Furthermore, by the result of Abraham et al. [ICALP 2011] there is a polynomial-time O(log k)-approximation algorithm for r-HD, but for r-SPC such an algorithm is not known. We prove that r-SPC admits a polynomial-time O(log n)-approximation algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Approximation algorithms analysis
Keywords
  • sparse hitting set
  • fair vertex cover
  • highway dimension

Metrics

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

Related Versions

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Vc-dimension and shortest path algorithms. In International Colloquium on Automata, Languages, and Programming, pages 690-699. Springer, 2011. Google Scholar
  2. Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 782-793. SIAM, 2010. Google Scholar
  3. Akanksha Agrawal, Pratibha Choudhary, NS Narayanaswamy, KK Nisha, and Vijayaragunathan Ramamoorthi. Parameterized complexity of minimum membership dominating set. In International Conference and Workshops on Algorithms and Computation, pages 288-299. Springer, 2022. Google Scholar
  4. Holger Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, and Dominik Schultes. In transit to constant time shortest-path queries in road networks. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 46-59. SIAM, 2007. Google Scholar
  5. Amariah Becker, Philip N Klein, and David Saulpic. Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  6. Johannes Blum. Hierarchy of transportation network parameters and hardness results. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 2019. Google Scholar
  7. Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke, and Bertrand Simon. On hop-constrained steiner trees in tree-like metrics. SIAM Journal on Discrete Mathematics, 36(2):1249-1273, 2022. Google Scholar
  8. Vladimir Braverman, Shaofeng H-C Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2679-2696. SIAM, 2021. Google Scholar
  9. Karl Bringmann, László Kozma, Shay Moran, and NS Narayanaswamy. Hitting set for hypergraphs of low vc-dimension. In 24th Annual European Symposium on Algorithms (ESA 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  10. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved parameterized upper bounds for vertex cover. In Rastislav Kralovic and Pawel Urzyczyn, editors, Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 238-249. Springer, 2006. URL: https://doi.org/10.1007/11821069_21.
  11. Yann Disser, Andreas Emil Feldmann, Max Klimm, and Jochen Könemann. Travelling on graphs with small highway dimension. Algorithmica, 83(5):1352-1370, 2021. URL: https://doi.org/10.1007/s00453-020-00785-5.
  12. Andreas Emil Feldmann. Fixed-parameter approximations for k-center problems in low highway dimension graphs. Algorithmica, 81(3):1031-1052, 2019. URL: https://doi.org/10.1007/s00453-018-0455-0.
  13. Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post. A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM Journal on Computing, 47(4):1667-1704, 2018. Google Scholar
  14. Andreas Emil Feldmann and David Saulpic. Polynomial time approximation schemes for clustering in low highway dimension graphs. J. Comput. Syst. Sci., 122:72-93, 2021. URL: https://doi.org/10.1016/j.jcss.2021.06.002.
  15. Martin Fürer and Balaji Raghavachari. Approximating the minimum degree spanning tree to within one from the optimal degree. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, pages 317-324, 1992. Google Scholar
  16. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, 1979. Google Scholar
  17. Michael R Garey, David S Johnson, and Larry Stockmeyer. Some simplified np-complete problems. In Proceedings of the sixth annual ACM symposium on Theory of computing, pages 47-63, 1974. Google Scholar
  18. Ashwin Jacob, Venkatesh Raman, and Vibha Sahlot. Deconstructing parameterized hardness of fair vertex deletion problems. In International Computing and Combinatorics Conference, pages 325-337. Springer, 2019. Google Scholar
  19. Aditya Jayaprakash and Mohammad R Salavatipour. Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.15034.
  20. Lawqueen Kanesh, Soumen Maity, Komal Muluk, and Saket Saurabh. Parameterized complexity of fair feedback vertex set problem. Theoretical Computer Science, 867:1-12, 2021. Google Scholar
  21. CS Karthik, Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. Journal of the ACM, 66(5), 2019. Google Scholar
  22. Dusan Knop, Tomás Masarík, and Tomás Toufar. Parameterized complexity of fair vertex evaluation problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  23. Petr Kolman, Bernard Lidický, and Jean-Sébastien Sereni. Fair edge deletion problems on tree-decomposable graphs and improper colorings, 2010. Technical report. Google Scholar
  24. Fabian Kuhn, Pascal von Rickenbach, Roger Wattenhofer, Emo Welzl, and Aaron Zollinger. Interference in cellular networks: The minimum membership set cover problem. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 188-198. Springer, 2005. Google Scholar
  25. Lishin Lin and Sartaj Sahni. Fair edge deletion problems. IEEE transactions on computers, 38(5):756-761, 1989. Google Scholar
  26. Tomáš Masařík and Tomáš Toufar. Parameterized complexity of fair deletion problems. Discrete Applied Mathematics, 278:51-61, 2020. Google Scholar
  27. J. Maňuch and D. R. Gaur. Fitting protein chains to cubic lattice is NP-complete. Journal of Bioinformatics and Computational Biology, 06.01:93-106, 2008. Google Scholar
  28. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. 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 Imprint Privacy Contact