Finding Paths in Graphs Avoiding Forbidden TransitionsDiscrete Applied Mathematics 126 no.2-3, pp. 239-251, 2003. Download: [paper ps] [paper pdf] 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 systemsT = { T(v) | v is a vertex of 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 A 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 T subset A. Our main result is that a dichotomy holds (subject to the assumption that P is not equal NP). That is, for a considered class A, 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 A. [back to Stefan Szeider's homepage] |