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 P3 P 3 s in O(m1.5+p3(G)) O ( m 1.5 + p 3 ( G ) ) time, and for k?4 k ? 4 all Pk P k s in O(nk?1+pk(G)+k?ck(G)) O ( n k ? 1 + p k ( G ) + k ? c k ( G ) ) time, where pk(G) p k ( G ) , respectively, ck(G) c k ( G ) , are the number of Pk P k s, respectively, Ck C k s, of a graph G G . We also provide an algorithm to find a Pk P k , k?5 k ? 5 , in time O(k!!?m(k?1)/2) O ( k ! ! ? m ( k ? 1 ) / 2 ) if k k is odd, and O(k!!?nm(k/2)?1) O ( k ! ! ? n m ( k / 2 ) ? 1 ) if k k 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.
induced path graph algorithm induced cycle