Finding and listing induced paths and cycles

Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all P3P3’s in O(m1.5+p3(G))O(m1.5+p3(G)) time, and for k≥4k≥4 all PkPk’s in O(nk−1+pk(G)+k⋅ck(G))O(nk−1+pk(G)+k⋅ck(G)) time, where pk(G)pk(G), respectively, ck(G)ck(G), are the number of PkPk’s, respectively, CkCk’s, of a graph GG. We also provide an algorithm to find a PkPk, k≥5k≥5, in time O(k!!⋅m(k−1)/2)O(k!!⋅m(k−1)/2) if kk is odd, and O(k!!⋅nm(k/2)−1)O(k!!⋅nm(k/2)−1) if kk is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms’ time bounds are incomparable with previously known algorithms.