DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2025.41

Token Sliding Reconfiguration on DAGs

Authors: Jona Dirks and Alexandre Vigny

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

Given a graph G and two independent sets of same size, the Independent Set Reconfiguration Problem under token sliding asks whether one can, in a step by step manner, transform the first independent set into the second one. In each step we must preserve the condition of independence. Further, referring to solution vertices as tokens, we are only permitted to slide a token along an edge. Until the recent work of Ito et al. [Ito et al. MFCS 2022] this problem was only considered on undirected graphs. In this work, we study reconfiguration under token sliding focusing on DAGs. We present a complete dichotomy of intractability in regard to the depth of the DAG, by proving that this problem is NP-complete for DAGs of depth 3 and W[1]-hard for depth 4 when parameterized by the number of tokens k, and that these bounds are tight. Further, we prove that it is fixed parameter tractable on DAGs parameterized by the combination of treewidth and k. We show that this result applies to undirected graphs, when the number of times a token can visit a vertex is restricted.

Cite as

Jona Dirks and Alexandre Vigny. Token Sliding Reconfiguration on DAGs. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dirks_et_al:LIPIcs.MFCS.2025.41,
  author =	{Dirks, Jona and Vigny, Alexandre},
  title =	{{Token Sliding Reconfiguration on DAGs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.41},
  URN =		{urn:nbn:de:0030-drops-241486},
  doi =		{10.4230/LIPIcs.MFCS.2025.41},
  annote =	{Keywords: Graph theory, FPT algorithms, Reconfiguration, Independent Sets}
}

Document

PACE Solver Description

DOI: 10.4230/LIPIcs.IPEC.2022.30

PACE Solver Description: GraPA-JAVA

Authors: Moritz Bergenthal, Jona Dirks, Thorben Freese, Jakob Gahde, Enna Gerhard, Mario Grobler, and Sebastian Siebertz

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract

We present an exact solver for the DFVS, submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2022. The solver heavily relies on data reduction (known from the literature and new reduction rules). The instances are then further processed by integer linear programming approaches. We implemented the algorithm in the scope of a student project at the University of Bremen.

Cite as

Moritz Bergenthal, Jona Dirks, Thorben Freese, Jakob Gahde, Enna Gerhard, Mario Grobler, and Sebastian Siebertz. PACE Solver Description: GraPA-JAVA. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bergenthal_et_al:LIPIcs.IPEC.2022.30,
  author =	{Bergenthal, Moritz and Dirks, Jona and Freese, Thorben and Gahde, Jakob and Gerhard, Enna and Grobler, Mario and Siebertz, Sebastian},
  title =	{{PACE Solver Description: GraPA-JAVA}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{30:1--30:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.30},
  URN =		{urn:nbn:de:0030-drops-173861},
  doi =		{10.4230/LIPIcs.IPEC.2022.30},
  annote =	{Keywords: complexity theory, parameterized complexity, linear programming, java, directed feedback vertex set, PACE 2022}
}

Document

PACE Solver Description

DOI: 10.4230/LIPIcs.IPEC.2021.30

PACE Solver Description: PACA-JAVA

Authors: Jona Dirks, Mario Grobler, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, and Maximilian Sonneborn

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract

We describe PACA-JAVA, an algorithm for solving the cluster editing problem submitted for the exact track of the Parameterized Algorithms and Computational Experiments challenge (PACE) in 2021. The algorithm solves the cluster editing problem by applying data-reduction rules, performing a layout heuristic, local search, iterative ILP verification, and branch-and-bound. We implemented the algorithm in the scope of a student project at the University of Bremen.

Cite as

Jona Dirks, Mario Grobler, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, and Maximilian Sonneborn. PACE Solver Description: PACA-JAVA. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 30:1-30:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dirks_et_al:LIPIcs.IPEC.2021.30,
  author =	{Dirks, Jona and Grobler, Mario and Rabinovich, Roman and Schnaubelt, Yannik and Siebertz, Sebastian and Sonneborn, Maximilian},
  title =	{{PACE Solver Description: PACA-JAVA}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{30:1--30:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.30},
  URN =		{urn:nbn:de:0030-drops-154138},
  doi =		{10.4230/LIPIcs.IPEC.2021.30},
  annote =	{Keywords: Cluster editing, parameterized complexity, PACE 2021}
}

Search Results

Documents authored by Dirks, Jona

Token Sliding Reconfiguration on DAGs

Abstract

Cite as

PACE Solver Description: GraPA-JAVA

Abstract

Cite as

PACE Solver Description: PACA-JAVA

Abstract

Cite as

Thanks for your feedback!

Could not send message