License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.8
URN: urn:nbn:de:0030-drops-144486
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14448/
Go to the corresponding LIPIcs Volume Portal

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

Order Reconfiguration Under Width Constraints

pdf-format:
LIPIcs-MFCS-2021-8.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{arrighi_et_al:LIPIcs.MFCS.2021.8,
  author =	{Arrighi, Emmanuel and Fernau, Henning and de Oliveira Oliveira, Mateus and Wolf, Petra},
  title =	{{Order Reconfiguration Under Width Constraints}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14448},
  URN =		{urn:nbn:de:0030-drops-144486},
  doi =		{10.4230/LIPIcs.MFCS.2021.8},
  annote =	{Keywords: Parameterized Complexity, Order Reconfiguration, String Rewriting Systems}
}

Keywords: Parameterized Complexity, Order Reconfiguration, String Rewriting Systems
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI