CISPA
Browse

The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs

Download (848.27 kB)
journal contribution
posted on 2024-02-19, 09:37 authored by Thomas 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" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC