Dado un grafo simple no dirigido ${\displaystyle G=(V,E)}$ , con ${\displaystyle n=|V|}$  y ${\displaystyle m=|E|}$ , y un entero positivo ${\displaystyle k\leq n}$ , decidir si ${\displaystyle G}$  tiene un camino inducido de tamaño al menos ${\displaystyle k}$  es un problema NP-completo. Este resultado se señala en el libro Computers and Intractability: A Guide to the Theory of NP-Completeness, y sus autores, Michael Garey y David S. Johnson, adjudican el resultado a Mihalis Yannakakis.^[2]​ Sin embargo, dado un ${\displaystyle k}$  fijo, contar todos los caminos inducidos de tamaño ${\displaystyle k}$  puede hacerse en tiempo polinomial,^[3]​ aunque contar todos los caminos inducidos para todo ${\displaystyle k\leq n}$  incremente el costo exponencialmente. Más aún, el número de caminos inducidos de tamaño ${\displaystyle k}$  puede acotarse superiormente por ${\displaystyle O(nm^{(k-1)/2})}$ , si ${\displaystyle k}$  es impar, o ${\displaystyle O(m^{k/2})}$ , si ${\displaystyle k}$  es par. Por lo tanto, enumerar todos los caminos inducidos de un tamaño ${\displaystyle k}$  fijo puede hacerse en tiempo polinomial en función del tamaño del grafo.^[3]​