Induced Path - Algorithms and Complexity

Algorithms and Complexity

It is NP-complete to determine, for a graph G and parameter k, whether the graph has an induced path of length at least k. Garey & Johnson (1979) credit this result to an unpublished communication of Mihalis Yannakakis. However, this problem can be solved in polynomial time for certain graph families, such as asteroidal-triple-free graphs or graphs with no long holes.

It is also NP-complete to determine whether the vertices of a graph can be partitioned into two induced paths, or two induced cycles. As a consequence, determining the induced path number of a graph is NP-hard.

The complexity of approximating the longest induced path or cycle problems can be related to that of finding large independent sets in graphs, by the following reduction. From any graph G with n vertices, form another graph H with twice as many vertices as G, by adding to G n(n − 1)/2 vertices having two neighbors each, one for each pair of vertices in G. Then if G has an independent set of size k, H must have an induced path and an induced cycle of length 2k, formed by alternating vertices of the independent set in G with vertices of I. Conversely, if H has an induced path or cycle of length k, any maximal set of nonadjacent vertices in G from this path or cycle forms an independent set in G of size at least k/3. Thus, the size of the maximum independent set in G is within a constant factor of the size of the longest induced path and the longest induced cycle in H. Therefore, by the results of Håstad (1996) on inapproximability of independent sets, unless NP=ZPP, there does not exist a polynomial time algorithm for approximating the longest induced path or the longest induced cycle to within a factor of O(n1/2-ε) of the optimal solution.

Holes (and antiholes in graphs without chordless cycles of length 5) in a graph with n vertices and m edges may be detected in time (n+m2).