posted on 2024-02-19, 09:37authored byThomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting.
History
Primary Research Area
Algorithmic Foundations and Cryptography
Journal
Algorithmica
Volume
85
Page Range
1202-1250
Publisher
Springer Nature
Open Access Type
Hybrid
Sub Type
Article
BibTeX
@article{Bellitto:Li:Okrasa:Pilipczuk:Sorge:2023,
title = "The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs",
author = "Bellitto, Thomas" AND "Li, Shaohua" AND "Okrasa, Karolina" AND "Pilipczuk, Marcin" AND "Sorge, Manuel",
year = 2023,
month = 5,
journal = "Algorithmica",
number = "5",
pages = "1202--1250",
publisher = "Springer Nature",
issn = "0178-4617",
doi = "10.1007/s00453-022-01064-1"
}