Document Open Access Logo

Distributed Vertex Cover Reconfiguration

Authors Keren Censor-Hillel , Yannic Maus , Shahar Romem-Peled, Tigran Tonoyan



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.36.pdf
  • Filesize: 0.91 MB
  • 23 pages

Document Identifiers

Author Details

Keren Censor-Hillel
  • Department of Computer Science, Technion, Haifa, Israel
Yannic Maus
  • Institute of Software Technology, TU Graz, Austria
Shahar Romem-Peled
  • Department of Computer Science, Technion, Haifa, Israel
Tigran Tonoyan
  • Department of Computer Science, Technion, Haifa, Israel

Cite AsGet BibTex

Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled, and Tigran Tonoyan. Distributed Vertex Cover Reconfiguration. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.36

Abstract

Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes {{cycles, trees, forests, chordal, cactus, even-hole-free, claw-free}}, there are schedules that use O(ε^{-1}) batches and incur only a 1+ε multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in a distributed setting O(ε^{-1} {log^*} n) rounds, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • reconfiguration
  • vertex cover
  • network decomposition

Metrics

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

References

  1. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 364-369, 1989. Google Scholar
  2. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1-45, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00228-4.
  3. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Shortest reconfiguration of colorings under Kempe changes. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pages 35:1-35:14, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.35.
  4. Marthe Bonamy, Paul Ouvrard, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Distributed recoloring. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, pages 12:1-12:17, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.12.
  5. Paul S. Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theor. Comput. Sci., 410(50):5215-5226, 2009. Google Scholar
  6. Paul S. Bonsma, Marcin Kaminski, and Marcin Wrochna. Reconfiguring independent sets in claw-free graphs. In R. Ravi and Inge Li Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, volume 8503 of Lecture Notes in Computer Science, pages 86-97. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_8.
  7. Keren Censor-Hillel and Mikaël Rabie. Distributed reconfiguration of maximal independent sets. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 135:1-135:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.135.
  8. Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. Connectedness of the graph of vertex-colourings. Discret. Math., 308(5-6):913-919, 2008. URL: https://doi.org/10.1016/j.disc.2007.07.028.
  9. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control, 70(1):32-53, July 1986. URL: https://doi.org/10.1016/S0019-9958(86)80023-7.
  10. Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. Independent-set reconfiguration thresholds of hereditary graph classes. Discret. Appl. Math., 250:165-182, 2018. URL: https://doi.org/10.1016/j.dam.2018.05.029.
  11. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Linear-time algorithm for sliding tokens on trees. Theoretical Computer Science, 600:132-142, 2015. Google Scholar
  12. Hristo Djidjev and Shankar M. Venkatesan. Reduced constants for simple cycle graph separation. Acta Informatica, 34(3):231-243, 1997. URL: https://doi.org/10.1007/s002360050082.
  13. Salwa Faour and Fabian Kuhn. Approximating bipartite minimum vertex cover in the CONGEST model. In Quentin Bramas, Rotem Oshman, and Paolo Romano, editors, 24th International Conference on Principles of Distributed Systems, OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference), volume 184 of LIPIcs, pages 29:1-29:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2020.29.
  14. R. G. Gallager, P. A. Humblet, and P. M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst., 5(1):66-77, January 1983. URL: https://doi.org/10.1145/357195.357200.
  15. Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput., 27(1):302-316, 1998. URL: https://doi.org/10.1137/S0097539794261118.
  16. Dennis Geller and Bennet Manvel. Reconstruction of cacti. Canadian Journal of Mathematics, 21:1354-1360, 1969. URL: https://doi.org/10.4153/CJM-1969-149-3.
  17. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 784-797. ACM, 2017. Google Scholar
  18. John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, 1984. URL: https://doi.org/10.1016/0196-6774(84)90019-1.
  19. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci., 343(1-2):72-96, 2005. Google Scholar
  20. Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: https://doi.org/10.1017/CBO9781139506748.005.
  21. Duc A. Hoang and Ryuhei Uehara. Sliding tokens on a cactus. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, volume 64 of LIPIcs, pages 37:1-37:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2016.37.
  22. Takehiro Ito, Erik D. Demaine, Nicholas J.A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
  23. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest reconfiguration of perfect matchings via alternating cycles. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, pages 61:1-61:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.61.
  24. Takehiro Ito, Marcin Kaminski, and Erik D. Demaine. Reconfiguration of list edge-colorings in a graph. Discret. Appl. Math., 160(15):2199-2207, 2012. URL: https://doi.org/10.1016/j.dam.2012.05.014.
  25. Takehiro Ito, Hiroyuki Nooka, and Xiao Zhou. Reconfiguration of vertex covers in a graph. IEICE Transactions on Information and Systems, E99.D(3):598-606, 2016. URL: https://doi.org/10.1587/transinf.2015FCP0010.
  26. Matthew Johnson, Dieter Kratsch, Stefan Kratsch, Viresh Patel, and Daniël Paulusma. Finding shortest paths between graph colourings. Algorithmica, 75(2):295-321, 2016. Google Scholar
  27. Marcin Kaminski, Paul Medvedev, and Martin Milanic. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9-15, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.004.
  28. Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka. The time complexity of the token swapping problem and its parallel variants. In Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen, editors, WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings, volume 10167 of Lecture Notes in Computer Science, pages 448-459. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-53925-6_35.
  29. Ken-ichi Kawarabayashi and Bruce A. Reed. A separator theorem in minor-closed classes. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 153-162. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.22.
  30. N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. Google Scholar
  31. Nati Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  32. Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: https://doi.org/10.1137/0209046.
  33. Daniel Lokshtanov and Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms, 15(1):7:1-7:19, 2019. URL: https://doi.org/10.1145/3280825.
  34. Adam Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families I: bipartite Ramanujan graphs of all degrees. Annals of Mathematics, 182:307-325, 2015. Google Scholar
  35. Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1-29, 1997. URL: https://doi.org/10.1145/256292.256294.
  36. Amer Mouawad, Naomi Nishimura, Venkatesh Raman, and Sebastian Siebertz. Vertex cover reconfiguration and beyond. Algorithms, 11(2):20, February 2018. URL: https://doi.org/10.3390/a11020020.
  37. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  38. David Peleg. Distributed computing. SIAM Monographs on Discrete Mathematics and Applications, 5, 2000. Google Scholar
  39. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 350-363. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384298.
  40. Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci., 93:1-10, 2018. URL: https://doi.org/10.1016/j.jcss.2017.11.003.
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