Paper Info
Title
Chordless paths through three vertices
Abstract
Consider the following problem, which we call "Chordless path through three vertices" or Cp3v, for short: Given a simple undirected graph G = (V, E), a positive integer k, and three distinct vertices s, t, and v ∈ V, is there a chordless path of length at most k from s via v to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of Cp3v by proving it W[1]-complete with respect to its natural parameter k. Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s, t)-path in a digraph is also W[1]-complete with respect to the length of the path.
Year
DOI
Venue
2006
10.1016/j.tcs.2005.10.021
Theor. Comput. Sci.
Keywords
DocType
Volume
induced path,distinct vertex,following problem,parametric complexity,graph theory,simple undirected graph,chordless path,positive integer k,natural parameter k,parameterized complexity.,service deployment,parameterized complexity,related problem,communication network
Journal
351
Issue
ISSN
Citations 
3
Theoretical Computer Science
14
PageRank 
References 
Authors
0.81
18
2
Name
Order
Citations
PageRank
Robert Haas126115.05
Michael Hoffmann222722.74