En la teoría de grafos, un camino inducido en un grafo simple no dirigido es un camino que es un subgrafo inducido de , y que corresponde a su vez a un grafo camino. Es decir, es una secuencia de vértices en 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 , y que corresponde a un ciclo sin cuerdas.
Algoritmos y complejidad Dado un grafo simple no dirigido , con y , y un entero positivo , decidir si tiene un camino inducido de tamaño al menos 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. Sin embargo, dado un fijo, contar todos los caminos inducidos de tamaño puede hacerse en tiempo polinomial, aunque contar todos los caminos inducidos para todo incremente el costo exponencialmente. Más aún, el número de caminos inducidos de tamaño puede acotarse superiormente por , si es impar, o , si es par. Por lo tanto, enumerar todos los caminos inducidos de un tamaño fijo puede hacerse en tiempo polinomial en función del tamaño del grafo.
Referencias
Categoría:Conectividad de grafos