Trayectoria inducida

En el ámbito matemático de la teoría de grafos , un camino inducido en un grafo no dirigido G es un camino que constituye un subgrafo inducido de G. Es decir, es una secuencia de vértices en G tal que cada par de vértices adyacentes en la secuencia están conectados por una arista en G , y cada par de vértices no adyacentes en la secuencia no están conectados por ninguna arista en G. Un camino inducido a veces se denomina serpiente , y el problema de encontrar caminos inducidos largos en grafos hipercubos se conoce como el problema de la serpiente en la caja .

De forma similar, un ciclo inducido es un ciclo que es un subgrafo inducido de G ; los ciclos inducidos también se denominan ciclos sin cuerdas o (cuando la longitud del ciclo es de cuatro o más) agujeros . Un antiagujero es un agujero en el complemento de G , es decir, un antiagujero es el complemento de un agujero.

La longitud del camino inducido más largo en un grafo se ha denominado a veces número de desvío del grafo; ^{[ 1 ]} para grafos dispersos , tener un número de desvío acotado es equivalente a tener una profundidad de árbol acotada . ^{[ 2 ]} El número de camino inducido de un grafo G es el número más pequeño de caminos inducidos en los que se pueden particionar los vértices del grafo, ^{[ 3 ]} y el número de cobertura de caminos estrechamente relacionado de G es el número más pequeño de caminos inducidos que juntos incluyen todos los vértices de G. ^{[ 4 ]} La circunferencia de un grafo es la longitud de su ciclo más corto, pero este ciclo debe ser un ciclo inducido ya que cualquier cuerda podría usarse para producir un ciclo más corto; por razones similares, la circunferencia impar de un grafo es también la longitud de su ciclo inducido impar más corto.

La ilustración muestra un cubo, un grafo con ocho vértices y doce aristas, y un camino inducido de longitud cuatro en dicho grafo. Un análisis sencillo del caso demuestra que ya no puede existir un camino inducido en el cubo, aunque este tenga un ciclo inducido de longitud seis. El problema de encontrar el camino o ciclo inducido más largo en un hipercubo, planteado por primera vez por Kautz (1958) , se conoce como el problema de la serpiente en la caja y ha sido ampliamente estudiado debido a sus aplicaciones en la teoría de la codificación y la ingeniería.

Muchas familias de grafos importantes pueden caracterizarse en términos de los caminos o ciclos inducidos por los grafos de la familia.

• Obviamente, los grafos conectados sin camino inducido de longitud dos son los grafos completos , y los grafos conectados sin ciclo inducido son los árboles .
• Un grafo libre de triángulos es un grafo que no tiene ningún ciclo inducido de longitud tres.
• Los cografos son precisamente los grafos sin trayectoria inducida de longitud tres.
• Las gráficas cordales son aquellas que no presentan ningún ciclo inducido de longitud cuatro o más.
• Los grafos sin agujeros pares son aquellos que no contienen ciclos inducidos con un número par de vértices.
• Los grafos trivialmente perfectos son aquellos que no tienen ni un camino inducido de longitud tres ni un ciclo inducido de longitud cuatro.
• Según el teorema de los grafos perfectos fuertes, los grafos perfectos son aquellos que no tienen agujeros impares ni antiagujeros impares.
• Los grafos hereditarios de distancia son aquellos en los que cada camino inducido es el camino más corto, y aquellos en los que dos caminos inducidos entre los mismos dos vértices tienen la misma longitud.
• Los grafos de bloques son aquellos en los que existe como máximo un camino inducido entre dos vértices cualesquiera, y los grafos de bloques conexos son aquellos en los que existe exactamente un camino inducido entre cada par de vértices.

Determinar, para un grafo G y un parámetro k , si el grafo tiene un camino inducido de longitud al menos k es un problema NP-completo . Garey y Johnson (1979) atribuyen este resultado a una comunicación no publicada de Mihalis Yannakakis . Sin embargo, este problema puede resolverse en tiempo polinomial para ciertas familias de grafos, como los grafos asteroidales triple-libres ^{[ 5 ]} o los grafos sin agujeros largos ^{[ 6 ] .}

También es NP-completo determinar si los vértices de un grafo se pueden particionar en dos caminos inducidos o en dos ciclos inducidos. ^{[ 7 ]} En consecuencia, determinar el número de caminos inducidos de un grafo es NP-difícil.

La complejidad de aproximar los problemas de caminos o ciclos inducidos más largos se puede relacionar con la de encontrar grandes conjuntos independientes en grafos, mediante la siguiente reducción. ^{[ 8 ]} A partir de cualquier grafo G con n vértices, se forma otro grafo H con el doble de vértices que G , añadiendo a G n ( n − 1)/2 vértices que tengan dos vecinos cada uno, uno por cada par de vértices en G . Entonces, si G tiene un conjunto independiente de tamaño k , H debe tener un camino inducido y un ciclo inducido de longitud 2 k , formados alternando vértices del conjunto independiente en G con vértices de I . Recíprocamente, si H tiene un camino o ciclo inducido de longitud k , cualquier conjunto máximo de vértices no adyacentes en G de este camino o ciclo forma un conjunto independiente en G de tamaño al menos k /3. Por lo tanto, el tamaño del conjunto independiente máximo en G está dentro de un factor constante del tamaño del camino inducido más largo y del ciclo inducido más largo en H . Por lo tanto, según los resultados de Håstad (1996) sobre la inaproximabilidad de conjuntos independientes, a menos que NP=ZPP, no existe un algoritmo de tiempo polinomial para aproximar el camino inducido más largo o el ciclo inducido más largo a un factor de O( n ^1/2-ε ) de la solución óptima.  

Los agujeros (y antiagujeros en grafos sin ciclos sin cuerdas de longitud 5) en un grafo con n vértices y m aristas pueden detectarse en tiempo (n+m ² ). ^{[ 9 ]}

Los ciclos atómicos son una generalización de los ciclos sin cuerdas, que no contienen n- cuerdas. Dado un ciclo, una n -cuerda se define como un camino de longitud n que conecta dos puntos del ciclo, donde n es menor que la longitud del camino más corto del ciclo que conecta esos puntos. Si un ciclo no tiene n- cuerdas, se denomina ciclo atómico, ya que no puede descomponerse en ciclos más pequeños. ^{[ 10 ]} En el peor de los casos, los ciclos atómicos de un grafo pueden enumerarse en tiempo O( m ² ), donde m es el número de aristas del grafo.