Document Open Access Logo

Covering Many (Or Few) Edges with k Vertices in Sparse Graphs

Authors Tomohiro Koana , Christian Komusiewicz , André Nichterlein , Frank Sommer

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.42.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Tomohiro Koana
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Christian Komusiewicz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany
André Nichterlein
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Frank Sommer
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany

Funding

  • Koana, Tomohiro: Supported by the Deutsche Forschungsgemeinschaft (DFG), project DiPa, NI 369/21.
  • Sommer, Frank: Supported by the Deutsche Forschungsgemeinschaft (DFG), project EAGR, {KO 3669/{6-1}}.

Cite AsGet BibTex

Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering Many (Or Few) Edges with k Vertices in Sparse Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.42

Abstract

We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed α between zero and one we are given a graph and two numbers k ∈ ℕ and t ∈ ℚ. The task is to find a vertex subset S of exactly k vertices that has value at least (resp. at most for minimization) t. Here, the value of a vertex set computes as α times the number of edges with exactly one endpoint in S plus 1-α times the number of edges with both endpoints in S. These two problems generalize many prominent graph problems, such as Densest k-Subgraph, Sparsest k-Subgraph, Partial Vertex Cover, and Max (k,n-k)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max (k,n-k)-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Kernelization
  • Partial Vertex Cover
  • Densest k-Subgraph
  • Max (k,n-k)-Cut
  • Degeneracy

Metrics

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

Related Versions

References

  1. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Implicit Branching and Parameterized Partial Cover Problems. Journal of Computer and System Sciences, 77(6):1159-1171, 2011. Google Scholar
  2. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  3. Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, and Emeric Tourniaire. Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization. Algorithmica, 71(3):566-580, 2015. Google Scholar
  4. Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, and Rémi Watrigant. An Algorithmic Weakening of the Erdős-Hajnal Conjecture. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA '20), volume 173 of LIPIcs, pages 23:1-23:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  5. Nicolas Bourgeois, Aristotelis Giannakos, Giorgio Lucarelli, Ioannis Milis, and Vangelis Th. Paschos. Exact and superpolynomial approximation algorithms for the Densest k-Subgraph problem. European Journal of Operational Research, 262(3):894-903, 2017. Google Scholar
  6. Maurizio Bruglieri, Matthias Ehrgott, Horst W. Hamacher, and Francesco Maffioli. An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. Discrete Applied Mathematics, 154(9):1344-1357, 2006. Google Scholar
  7. Leizhen Cai. Parameterized Complexity of Cardinality Constrained Optimization Problems. The Computer Journal, 51(1):102-121, 2008. Google Scholar
  8. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. In Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC '06), volume 4169 of LNCS, pages 239-250. Springer, 2006. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. ACM Transactions on Algorithms, 13(3):43:1-43:22, 2017. Google Scholar
  11. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Applied Mathematics, 160(15):2131-2141, 2012. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. Pavel Dvorák, Andreas Emil Feldmann, Ashutosh Rai, and Pawel Rzazewski. Parameterized Inapproximability of Independent Set in H-Free Graphs. In Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG '20), volume 12301 of Lecture Notes in Computer Science, pages 40-53. Springer, 2020. Google Scholar
  14. David Eppstein and Emma S. Spiro. The h-Index of a Graph and its Application to Dynamic Subgraph Statistics. Journal of Graph Algorithms and Applications, 16(2):543-567, 2012. URL: https://doi.org/10.7155/jgaa.00273.
  15. Uriel Feige and Michael Seltser. On the densest k-subgraph problem. Technical report, Weizmann Institute of Science. Department of Applied Mathematics and Computer Science, 1997. Google Scholar
  16. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding Cliques in Social Networks: A New Distribution-Free Model. SIAM Journal on Computing, 49(2):448-464, 2020. Google Scholar
  17. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized Complexity of Vertex Cover Variants. Theory of Computing Systems, 41(3):501-520, 2007. Google Scholar
  18. Satoshi Hara, Takayuki Katsuki, Hiroki Yanagisawa, Takafumi Ono, Ryo Okamoto, and Shigeki Takeuchi. Consistent and Efficient Nonparametric Different-Feature Selection. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS '17), volume 54 of Proceedings of Machine Learning Research, pages 130-138. PMLR, 2017. Google Scholar
  19. Satoshi Hara, Tetsuro Morimura, Toshihiro Takahashi, Hiroki Yanagisawa, and Taiji Suzuki. A Consistent Method for Graph Based Anomaly Localization. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (AISTATS '15), volume 38 of Proceedings of Machine Learning Research, pages 333-341. PMLR, 2015. Google Scholar
  20. Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2011. Google Scholar
  21. Joachim Kneis, Alexander Langer, and Peter Rossmanith. Improved Upper Bounds for Partial Vertex Cover. In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '08), volume 5344 of LNCS, pages 240-251, 2008. Google Scholar
  22. Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer. Covering Many (or Few) Edges with k Vertices in Sparse Graphs. CoRR, abs/2201.05465, 2022. URL: http://arxiv.org/abs/2201.05465.
  23. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. In Proceedings of the 31st International Symposium on Algorithms and Computation, (ISAAC '20), volume 181 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-Closure in Kernelization Algorithms for Graph Problems. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA '20), volume 173 of LIPIcs, pages 65:1-65:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  25. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially Tight Kernels For (Weakly) Closed Graphs. In Proceedings of the 32nd International Symposium on Algorithms and Computation, (ISAAC '21), volume 212 of LIPIcs, pages 35:1-35:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  26. Christian Komusiewicz and Manuel Sorge. An Algorithmic Framework for Fixed-Cardinality Optimization in Sparse Graphs Applied to Dense Subgraph Problems. Discrete Applied Mathematics, 193:145-161, 2015. Google Scholar
  27. William Lochet, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Exploiting Dense Structures in Parameterized Complexity. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS '21), volume 187 of LIPIcs, pages 50:1-50:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.50.
  28. Fahad Panolan and Hannane Yaghoubizade. Partial Vertex Cover on Graphs of Bounded Degeneracy. CoRR, abs/2201.03876, 2022. URL: http://arxiv.org/abs/2201.03876.
  29. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial Kernels for Dominating Set in Graphs of Bounded Degeneracy and Beyond. ACM Transactions on Algorithms, 9(1):11:1-11:23, 2012. Google Scholar
  30. Venkatesh Raman and Saket Saurabh. Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles. Algorithmica, 52(2):203-225, 2008. Google Scholar
  31. Saket Saurabh and Meirav Zehavi. (k, n - k)-MAX-CUT: An 𝒪^*(2^p)-time algorithm and a polynomial kernel. Algorithmica, 80(12):3844-3860, 2018. URL: https://doi.org/10.1007/s00453-018-0418-5.
  32. Hadas Shachnai and Meirav Zehavi. Parameterized Algorithms for Graph Partitioning Problems. Theory of Computing Systems, 61(3):721-738, 2017. URL: https://doi.org/10.1007/s00224-016-9706-0.
  33. Rémi Watrigant, Marin Bougeret, and Rodolphe Giroudeau. Approximating the Sparsest k-Subgraph in Chordal Graphs. Theory of Computing Systems, 58(1):111-132, 2016. 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