Camino inducido

En la teoría de grafos, un camino inducido en un grafo simple no dirigido ${\displaystyle G}$ es un camino que es un subgrafo inducido de ${\displaystyle G}$, y que corresponde a su vez a un grafo camino.^[1]​ Es decir, es una secuencia de vértices en ${\displaystyle G}$ tal que cada par de vértices adyacentes en la secuencia está conectada por una arista, y cada par de vértices no adyacentes en la secuencia no está conectada por una arista. De manera análoga, un ciclo inducido es un ciclo que es un subgrafo inducido de ${\displaystyle G}$, y que corresponde a un ciclo sin cuerdas.

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]​