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.ESA.2022.61
URN: urn:nbn:de:0030-drops-169991
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16999/
Go to the corresponding LIPIcs Volume Portal

Gima, Tatsuya ; Ito, Takehiro ; Kobayashi, Yasuaki ; Otachi, Yota

Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited

pdf-format:
LIPIcs-ESA-2022-61.pdf (0.9 MB)

Abstract

Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting, Mouawad et al. [IPEC 2014] presented an algorithmic meta-theorem for reconfiguration problems that says if the feasibility can be expressed in monadic second-order logic (MSO), then the problem is fixed-parameter tractable parameterized by treewidth + ?, where ? is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna [J. Comput. Syst. Sci. 2018] that if ? is not part of the parameter, then the problem is PSPACE-complete even on graphs of bounded bandwidth.
In this paper, we present the first algorithmic meta-theorems for the case where ? is not part of the parameter, using some structural graph parameters incomparable with bandwidth. We show that if the feasibility is defined in MSO, then the reconfiguration problem under the so-called token jumping rule is fixed-parameter tractable parameterized by neighborhood diversity. We also show that the problem is fixed-parameter tractable parameterized by treedepth + k, where k is the size of sets being transformed. We finally complement the positive result for treedepth by showing that the problem is PSPACE-complete on forests of depth 3.

BibTeX - Entry

@InProceedings{gima_et_al:LIPIcs.ESA.2022.61,
  author =	{Gima, Tatsuya and Ito, Takehiro and Kobayashi, Yasuaki and Otachi, Yota},
  title =	{{Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{61:1--61:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16999},
  URN =		{urn:nbn:de:0030-drops-169991},
  doi =		{10.4230/LIPIcs.ESA.2022.61},
  annote =	{Keywords: Combinatorial reconfiguration, monadic second-order logic, fixed-parameter tractability, treedepth, neighborhood diversity}
}

Keywords: Combinatorial reconfiguration, monadic second-order logic, fixed-parameter tractability, treedepth, neighborhood diversity
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

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