DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.28

Pathfinding in Self-Deleting Graphs

Authors: Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Cite as

Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi. Pathfinding in Self-Deleting Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2025.28,
  author =	{Dvo\v{r}\'{a}k, Michal and Knop, Du\v{s}an and Opler, Michal and Pokorn\'{y}, Jan and Such\'{y}, Ond\v{r}ej and Szil\'{a}gyi, Krisztina},
  title =	{{Pathfinding in Self-Deleting Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.28},
  URN =		{urn:nbn:de:0030-drops-249365},
  doi =		{10.4230/LIPIcs.ISAAC.2025.28},
  annote =	{Keywords: Parameterized complexity, self-deleting graphs, pathfinding}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.36

Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Authors: Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small edge separators. Let p,q ∈ ℕ such that p is a prime and q ≥ 3. We show: - If p divides q-1, there is a (q-1)^{ctw}n^{O(1)} time algorithm for counting list q-colorings modulo p of n-vertex graphs of cutwidth ctw. Furthermore, there is no ε > 0 for which there is a (q-1-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming the Strong Exponential Time Hypothesis (SETH). - If p does not divide q-1, there is no ε > 0 for which there exists a (q-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming SETH. The lower bounds are in stark contrast with the existing 2^{ctw}n^{O(1)} time algorithm to compute the chromatic number of a graph by Jansen and Nederlof [Theor. Comput. Sci.'18]. Furthermore, by building upon the above lower bounds, we obtain the following lower bound for counting connected spanning edge sets: there is no ε > 0 for which there is an algorithm that, given a graph G and a cutwidth ordering of cutwidth ctw, counts the number of spanning connected edge sets of G modulo p in time (p - ε)^{ctw} n^{O(1)}, assuming SETH. We also give an algorithm with matching running time for this problem. Before our work, even for the treewidth parameterization, the best conditional lower bound by Dell et al. [ACM Trans. Algorithms'14] only excluded 2^{o(tw)}n^{O(1)} time algorithms for this problem. Both our algorithms and lower bounds employ use of the matrix rank method, by relating the complexity of the problem to the rank of a certain "compatibility matrix" in a non-trivial way.

Cite as

Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.STACS.2022.36,
  author =	{Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Szil\'{a}gyi, Krisztina},
  title =	{{Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.36},
  URN =		{urn:nbn:de:0030-drops-158464},
  doi =		{10.4230/LIPIcs.STACS.2022.36},
  annote =	{Keywords: connected edge sets, cutwidth, parameterized algorithms, colorings, counting modulo p}
}

Search Results

Documents authored by Szilágyi, Krisztina

Pathfinding in Self-Deleting Graphs

Abstract

Cite as

Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Abstract

Cite as

Thanks for your feedback!

Could not send message