Vertex disjoint paths on clique-width bounded graphs
We show that the I vertex disjoint paths problem between 1 pairs of vertices can be solved in linear time for co-graphs but is NP-complete for graphs of clique-width at most 6 and NLC-width at most 4. The NP-completeness follows from the fact that the line graph of a graph of tree-width k has clique-width at most 2k + 2 and NLC-width at most k + 2, and a result by Nishizeki et al. [The edge-disjoint paths problem is NP-complete for series-parallel graphs, Discrete Appl. Math. 115 (2001) 177-186]. The vertex disjoint paths problem is the first graph problem shown to be NP-complete on graphs of bounded clique-width but solvable in linear time on co-graphs and graphs of bounded tree-width. Additionally, we show that the r vertex disjoint paths problem between each of I pairs of vertices can be solved in polynomial time for co-graphs, if 1 is given to the input, and for graphs of bounded clique-width, if I is fixed. (C) 2006 Elsevier B.V. All rights reserved.
vertex disjoint paths clique-width nlc-width line graphs tree-width edge disjoint paths