Document Open Access Logo

Order Reconfiguration Under Width Constraints

Authors Emmanuel Arrighi , Henning Fernau , Mateus de Oliveira Oliveira , Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.8.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Author Details

Emmanuel Arrighi
  • University of Bergen, Norway
Henning Fernau
  • University of Trier, Germany
Mateus de Oliveira Oliveira
  • University of Bergen, Norway
Petra Wolf
  • University of Trier, Germany

Funding

  • Arrighi, Emmanuel: Research Council of Norway (274526), IS-DAAD (309319).
  • Fernau, Henning: DAAD PPP (57525246).
  • de Oliveira Oliveira, Mateus: Research Council of Norway (288761), IS-DAAD (309319).
  • Wolf, Petra: DFG project FE 560/9-1, DAAD PPP (57525246).

Cite As Get BibTex

Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf. Order Reconfiguration Under Width Constraints. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.8

Abstract

In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω' have cutwidth (pathwidth) at most k/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Combinatorial optimization
  • Theory of computation → Equational logic and rewriting
Keywords
  • Parameterized Complexity
  • Order Reconfiguration
  • String Rewriting Systems

Metrics

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

References

  1. Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, 1999. Google Scholar
  2. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pages 684-697. ACM, 2016. Google Scholar
  3. László Babai, D. Yu. Grigoryev, and David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC '82, pages 310-324. ACM, 1982. Google Scholar
  4. László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science, FOCS '83, pages 162-171. IEEE, 1983. Google Scholar
  5. Erik Barendsen. Term Rewriting Systems. Cambridge University Press, 2003. Google Scholar
  6. Ronald V. Book and Friedrich Otto. String-rewriting systems. In String-Rewriting Systems, pages 35-64. Springer, 1993. Google Scholar
  7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Paramterized Complexity. Springer, 2013. Google Scholar
  8. John A. Ellis, Ivan H. Sudborough, and Jonathan S. Turner. The vertex separation and search number of a graph. Information and Computation, 113(1):50-79, 1994. Google Scholar
  9. Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science, FOCS '80, pages 36-41. IEEE Computer Society, 1980. Google Scholar
  10. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects. Algorithmica, 81(2):557-588, 2019. Google Scholar
  11. Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. Journal of the ACM, 59(5):27, 2012. Google Scholar
  12. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM Journal on Computing, 44(1):114-159, 2015. Google Scholar
  13. Martin Grohe, Daniel Neuen, and Pascal Schweitzer. A faster isomorphism test for graphs of small degree. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 89-100. IEEE, 2018. Google Scholar
  14. Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pages 67:1-67:14, 2018. Google Scholar
  15. Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 1010-1029. IEEE, 2015. Google Scholar
  16. Nao Hirokawa, Aart Middeldorp, Christian Sternagel, and Sarah Winkler. Abstract completion, formalized. Logical Methods in Computer Science, 15(3), 2019. Google Scholar
  17. 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. Google Scholar
  18. Deepak Kapur and Paliath Narendran. The Knuth-Bendix completion procedure and Thue systems. SIAM Journal on Computing, 14(4):1052-1072, 1985. Google Scholar
  19. Jan Willem Klop. Term Rewriting Systems. Centrum voor Wiskunde en Informatica, 1990. Google Scholar
  20. Stefan Kratsch and Pascal Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. In Haim Kaplan, editor, Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, volume 6139 of Lecture Notes in Computer Science, pages 81-92. Springer, 2010. Google Scholar
  21. Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 186-195. IEEE, 2014. Google Scholar
  22. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, 1982. Google Scholar
  23. Gary Miller. Isomorphism testing for graphs of bounded genus. In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC '80, pages 225-235. ACM, 1980. Google Scholar
  24. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. Google Scholar
  25. Christian Sternagel and René Thiemann. Formalizing Knuth-Bendix orders and Knuth-Bendix completion. In Femke van Raamsdonk, editor, 24th International Conference on Rewriting Techniques and Applications, RTA 2013, volume 21 of LIPIcs. Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2013. Google Scholar
  26. Ian Wehrman, Aaron Stump, and Edwin Westbrook. Slothrop: Knuth-Bendix completion with a modern termination checker. In Frank Pfenning, editor, Term Rewriting and Applications, 17th International Conference, RTA 2006, volume 4098 of Lecture Notes in Computer Science, pages 287-296. Springer, 2006. Google Scholar
  27. Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer and System Sciences, 93:1-10, 2018. 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