Document Open Access Logo

Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial

Authors Christian Komusiewicz , Nils Morawietz

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2022.20.pdf
  • Filesize: 0.79 MB
  • 18 pages

Document Identifiers

Author Details

Christian Komusiewicz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany
Nils Morawietz
  • Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Germany

Funding

  • Morawietz, Nils: {Supported by the Deutsche Forschungsgemeinschaft (DFG), project OPERAH, KO 3669/5-1.}

Cite As Get BibTex

Christian Komusiewicz and Nils Morawietz. Parameterized Local Search for Vertex Cover: When Only the Search Radius Is Crucial. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.IPEC.2022.20

Abstract

A k-swap W for a vertex cover S of a graph G is a vertex set of size at most k such that S' = (S ⧵ W) ∪ (W ⧵ S), the symmetric difference of S and W, is a vertex cover of G. If |S'| < |S|, then W is improving. In LS-Vertex Cover, one is given a vertex cover S of a graph G and wants to know if there is an improving k-swap for S in G. In applications of LS-Vertex Cover, k is a very small parameter that can be set by a user to determine the trade-off between running time and solution quality. Consequently, k can be considered to be a constant. Motivated by this and the fact that LS-Vertex Cover is W[1]-hard with respect to k, we aim for algorithms with running time 𝓁^f(k) ⋅ n^𝒪(1) where 𝓁 is a structural graph parameter upper-bounded by n. We say that such a running time grows mildly with respect to 𝓁 and strongly with respect to k. We obtain algorithms with such a running time for 𝓁 being the h-index of G, the treewidth of G, or the modular-width of G. In addition, we consider a novel parameter, the maximum degree over all quotient graphs in a modular decomposition of G. Moreover, we adapt these algorithms to the more general problem where each vertex is assigned a weight and where we want to find a d-improving k-swap, that is, a k-swap which decreases the weight of the vertex cover by at least d.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Computing methodologies → Discrete space search
Keywords
  • Local Search
  • Structural parameterization
  • Fixed-parameter tractability

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant’s parser. SIAM Journal on Computing, 47(6):2527-2555, 2018. URL: https://doi.org/10.1137/16M1061771.
  2. Faisal N. Abu-Khzam, Shaowei Cai, Judith Egan, Peter Shaw, and Kai Wang. Turbo-charging dominating set with an FPT subroutine: Further improvements and experimental analysis. In Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation (TAMC '17), volume 10185 of Lecture Notes in Computer Science, pages 59-70, 2017. Google Scholar
  3. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21), pages 522-539. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.32.
  4. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, 1996. URL: https://doi.org/10.1137/S0097539793251219.
  5. Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Lukasz Kowalik. Fine-grained complexity of k-OPT in bounded-degree graphs for solving TSP. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA '19), volume 144 of LIPIcs, pages 23:1-23:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  6. Shaowei Cai, Kaile Su, Chuan Luo, and Abdul Sattar. NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 46:687-716, 2013. Google Scholar
  7. 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
  8. Alexander Dobler, Manuel Sorge, and Anaïs Villedieu. Turbocharging heuristics for weak coloring numbers. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA '22), volume 244 of LIPIcs, pages 44:1-44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  9. 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. Google Scholar
  10. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, and Yngve Villanger. Local search: Is brute-force avoidable? Journal of Computer and System Sciences, 78(3):707-719, 2012. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michal Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms, 14(3):34:1-34:45, 2018. URL: https://doi.org/10.1145/3186898.
  12. Serge Gaspers, Joachim Gudmundsson, Mitchell Jones, Julián Mestre, and Stefan Rümmele. Turbocharging treewidth heuristics. Algorithmica, 81(2):439-475, 2019. URL: https://doi.org/10.1007/s00453-018-0499-1.
  13. Serge Gaspers, Eun Jung Kim, Sebastian Ordyniak, Saket Saurabh, and Stefan Szeider. Don't be strict in local search! In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI '12). AAAI Press, 2012. Google Scholar
  14. Jiong Guo, Sepp Hartung, Rolf Niedermeier, and Ondrej Suchý. The parameterized complexity of local search for TSP, more refined. Algorithmica, 67(1):89-110, 2013. Google Scholar
  15. Jiong Guo, Danny Hermelin, and Christian Komusiewicz. Local search for string problems: Brute-force is essentially optimal. Theoretical Computer Science, 525:30-41, 2014. Google Scholar
  16. Holger H. Hoos and Thomas Stützle. Stochastic Local Search: Foundations & Applications. Elsevier / Morgan Kaufmann, 2004. Google Scholar
  17. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. Google Scholar
  18. Maximilian Katzmann and Christian Komusiewicz. Systematic exploration of larger local search neighborhoods for the minimum vertex cover problem. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, (AAAI '17), pages 846-852. AAAI Press, 2017. Google Scholar
  19. Christian Komusiewicz and Nils Morawietz. Finding 3-swap-optimal independent sets and dominating sets is hard. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS '22), volume 241 of LIPIcs, pages 66:1-66:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  20. Ruizhi Li, Shuli Hu, Shaowei Cai, Jian Gao, Yiyuan Wang, and Minghao Yin. NuMWVC: A novel local search for minimum weighted vertex cover problem. Journal of the Operational Research Society, 71(9):1498-1509, 2020. Google Scholar
  21. Dániel Marx. Searching the k-change neighborhood for TSP is W[1]-hard. Operations Research Letters, 36(1):31-36, 2008. Google Scholar
  22. Ross M. McConnell and Jeremy P. Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pages 536-545. ACM/SIAM, 1994. Google Scholar
  23. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  24. Stefan Szeider. The parameterized complexity of k-flip local search for SAT and MAX SAT. Discrete Optimization, 8(1):139-145, 2011. Google Scholar
  25. Gerhard J. Woeginger. Space and time complexity of exact algorithms: Some open problems (invited talk). In Proceedings of the First International Workshop on Parameterized and Exact Computation (IWPEC '04), volume 3162 of Lecture Notes in Computer Science, pages 281-290. Springer, 2004. 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