Independent Set Reconfiguration on Directed Graphs
Document Open Access Logo

Independent Set Reconfiguration on Directed Graphs

Authors Takehiro Ito , Yuni Iwamasa , Yasuaki Kobayashi , Yu Nakahata , Yota Otachi , Masahiro Takahashi, Kunihiro Wasa

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.58.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

Takehiro Ito
  • Graduate School of Information Sciences, Tohoku University, Sendai, Japan
Yuni Iwamasa
  • Graduate School of Informatics, Kyoto University, Kyoto, Japan
Yasuaki Kobayashi
  • Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan
Yu Nakahata
  • Division of Information Science, Nara Institute of Science and Technology, Ikoma, Japan
Yota Otachi
  • Graduate School of Informatics, Nagoya University, Nagoya, Japan
Masahiro Takahashi
  • Graduate School of Informatics, Kyoto University, Kyoto, Japan
Kunihiro Wasa
  • Faculty of Science and Engineering, Hosei University, Tokyo, Japan

Funding

  • Ito, Takehiro: JSPS KAKENHI Grant Numbers JP18H04091, JP19K11814, JP20H05793
  • Iwamasa, Yuni: JSPS KAKENHI Grant Numbers JP20K23323, JP20H05795, JP22K17854
  • Kobayashi, Yasuaki: JSPS KAKENHI Grant Numbers JP20H00595, JP20H05793, JP20K19742
  • Nakahata, Yu: JSPS KAKENHI Grant Numbers JP19H01103, JP20H05794, JP22H03549, JP22K17851
  • Otachi, Yota: JSPS KAKENHI Grant Numbers JP18H04091, JP20H05793, JP21K11752, JP22H00513
  • Wasa, Kunihiro: JSPS KAKENHI Grant Numbers JP19K20350, JP20H05793, JP22H03549, JP22K17849

Cite As Get BibTex

Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa. Independent Set Reconfiguration on Directed Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.58

Abstract

Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions.
In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al. TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Combinatorial reconfiguration
  • token sliding
  • directed graph
  • independent set
  • graph algorithm

Metrics

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

Related Versions

References

  1. Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. Flip distances between graph orientations. Algorithmica, 83:116-143, 2021. URL: https://doi.org/10.1007/s00453-020-00751-1.
  2. Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), volume 181 of LIPIcs, pages 44:1-44:17, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.44.
  3. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token sliding on split graphs. Theory of Computing Systems, 65:662-686, 2021. URL: https://doi.org/10.1007/s00224-020-09967-8.
  4. Marthe Bonamy and Nicolas Bousquet. Token sliding on chordal graphs. In Proceedings of the 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), volume 10520 of LNCS, pages 127-139, 2017. URL: https://doi.org/10.1007/978-3-319-68705-6_10.
  5. Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The perfect matching reconfiguration problem. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of LIPIcs, pages 80:1-80:14, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.80.
  6. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Diameter of colorings under Kempe changes. Theoretical Computer Science, 838:45-57, 2020. URL: https://doi.org/10.1016/j.tcs.2020.05.033.
  7. Paul S. Bonsma and Luis Cereceda. Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215-5226, 2009. URL: https://doi.org/10.1016/j.tcs.2009.08.023.
  8. Paul S. Bonsma, Marcin Kaminski, and Marcin Wrochna. Reconfiguring independent sets in claw-free graphs. In Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), volume 8503 of LNCS, pages 86-97, 2014. URL: https://doi.org/10.1007/978-3-319-08404-6_8.
  9. Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, and Moritz Mühlenthaler. Shortest reconfiguration of matchings. In Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019), volume 11789 of LNCS, pages 162-174, 2019. URL: https://doi.org/10.1007/978-3-030-30786-8_13.
  10. Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token jumping in minor-closed classes. In Proceedings of the 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), volume 10472 of LNCS, pages 136-149, 2017. URL: https://doi.org/10.1007/978-3-662-55751-8_12.
  11. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015. Google Scholar
  12. 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. URL: https://doi.org/10.1016/j.tcs.2015.07.037.
  13. Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, and Ryuhei Uehara. Sliding token on bipartite permutation graphs. In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), volume 9472 of LNCS, pages 237-247, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_21.
  14. Komei Fukuda, Alain Prodon, and Tadashi Sakuma. Notes on acyclic orientations and the shelling lemma. Theoretical Computer Science, 263(1-2):9-16, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00226-7.
  15. Curtis Greene and Thomas Zaslavsky. On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Transactions of the American Mathematical Society, 280(1):97-126, 1983. Google Scholar
  16. Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, and Youcef Tebbal. The complexity of dominating set reconfiguration. Theoretical Computer Science, 651:37-49, 2016. URL: https://doi.org/10.1016/j.tcs.2016.08.016.
  17. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005. URL: https://doi.org/10.1016/j.tcs.2005.05.008.
  18. Duc A. Hoang and Ryuhei Uehara. Sliding tokens on a cactus. In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of LIPIcs, pages 37:1-37:26, 2016. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2016.37.
  19. 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-14):1054-1065, 2011. URL: https://doi.org/10.1016/j.tcs.2010.12.005.
  20. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 1342-1355, 2022. Google Scholar
  21. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa. Independent set reconfiguration on directed graphs. CoRR, abs/2203.13435, 2022. URL: https://doi.org/10.48550/arXiv.2203.13435.
  22. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, and Kunihiro Wasa. Reconfiguring directed trees in a digraph. In Proceedings of the 27th International Computing and Combinatorics Conference (COCOON 2021), volume 13025 of LNCS, pages 343-354, 2021. Google Scholar
  23. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest reconfiguration of perfect matchings via alternating cycles. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of LIPIcs, pages 61:1-61:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.61.
  24. Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. On the parameterized complexity for token jumping on graphs. In Proceedings of the 11th Annual Conference on Theory and Applications of Models of Computation (TAMC 2014), volume 8402 of LNCS, pages 341-351, 2014. URL: https://doi.org/10.1007/978-3-319-06089-7_24.
  25. Takehiro Ito, Marcin Jakub Kaminski, and Hirotaka Ono. Fixed-parameter tractability of token jumping on planar graphs. In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 208-219, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_17.
  26. Takehiro Ito, Marcin Jakub Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. Parameterized complexity of independent set reconfiguration problems. Discrete Applied Mathematics, 283:336-345, 2020. URL: https://doi.org/10.1016/j.dam.2020.01.022.
  27. Takehiro Ito, Hirotaka Ono, and Yota Otachi. Reconfiguration of cliques in a graph. In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC 2015), volume 9076 of LNCS, pages 212-223, 2015. URL: https://doi.org/10.1007/978-3-319-17142-5_19.
  28. Marcin Kaminski, Paul Medvedev, and Martin Milanic. Complexity of independent set reconfigurability problems. Theoretical Computer Science, 439:9-15, 2012. URL: https://doi.org/10.1016/j.tcs.2012.03.004.
  29. Daniel Lokshtanov and Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms, 15(1):7:1-7:19, 2019. URL: https://doi.org/10.1145/3280825.
  30. Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. Journal of Computer and System Sciences, 95:122-131, 2018. URL: https://doi.org/10.1016/j.jcss.2018.02.004.
  31. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  32. Hiroki Osawa, Akira Suzuki, Takehiro Ito, and Xiao Zhou. Algorithms for coloring reconfiguration under recolorability constraints. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 37:1-37:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.37.
  33. Ken Sugimori. A polynomial-time algorithm for shortest reconfiguration of sliding tokens on a tree. Master’s thesis, The University of Tokyo, 2019. (In Japanese). Google Scholar
  34. Akira Suzuki, Amer E. Mouawad, and Naomi Nishimura. Reconfiguration of dominating sets. Journal of Combinatorial Optimization, 32(4):1182-1195, 2016. URL: https://doi.org/10.1007/s10878-015-9947-x.
  35. Jan van den Heuvel. The complexity of change. In Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013. URL: https://doi.org/10.1017/CBO9781139506748.005.
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