Vertex disjoint paths on clique-width bounded graphs

AbstractWe show that the l vertex disjoint paths problem between l 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 l pairs of vertices can be solved in polynomial time for co-graphs, if l is given to the input, and for graphs of bounded clique-width, if l is fixed