Finding Paths in Graphs Avoiding Forbidden Transitions;

Szeider, Stefan

Abstract

Let v be a vertex of a graph G; a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T={T(v) | vV(G)}. A path P in G is called T-compatible, if each pair uv,vw of consecutive edges of P form an edge in T(v). Let be a given class of graphs (closed under isomorphism). We study the computational complexity of finding T-compatible paths between two given vertices of a graph for a specified transition system . Our main result is that a dichotomy holds (subject to the assumption P≠NP). That is, for a considered class , the problem is either (1) NP-complete, or (2) it can be solved in linear time. We give a criterion—based on vertex induced subgraphs—which decides whether (1) or (2) holds for any given class.

Citation

Szeider, S. (2003). Finding Paths in Graphs Avoiding Forbidden Transitions;. Discrete Applied Mathematics, 126(2-3), 261-273. https://doi.org/10.1016/s0166-218x%2802%2900251-2

• Journal Article Type: Article
• Publication Date: Mar 15, 2003
• Deposit Date: Oct 14, 2008
• Publicly Available Date: Oct 14, 2008
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 126
• Issue: 2-3
• Pages: 261-273
• DOI: https://doi.org/10.1016/s0166-218x%2802%2900251-2
• Keywords: Compatible path, Transition, Edge-colored graph, Forbidden pairs, NP-Completeness, Linear time algorithm.