¿Es este problema de teoría de grafos NP-completo?

Question

En la universidad estaba en una clase de introducción a la teoría de los grafos (de grado). Para una tarea estaba creando un algoritmo para resolver el siguiente problema:

Encontrar un ciclo de longitud impar en un gráfico dirigido N

Mientras buscaba el problema en Google, encontré una referencia de que este problema era NP-Completo. Lo descarté porque ya pensaba que tenía un buen algoritmo, así que obviamente no podía ser NP-Completo, y también porque el problema no parece tan intuitivamente difícil como otros problemas NP-Completos con los que estoy familiarizado. Lamentablemente no he podido encontrar esta referencia desde entonces, así que no puedo enlazarla aquí.

Sin embargo, de vez en cuando pienso en esto, y como no conozca que no es NP-Completo, siempre me pregunto "¿y si?

Así que para tranquilizarme, lo que busco es:

1. Verificación de que este problema no es NP-Completo.
2. ¿Hay algún problema similar conocido que son en NP-Completo? ¿Algo como "Encontrar el ciclo de longitud impar más corto en un grafo dirigido N"? (He buscado en las listas de internet pero no he encontrado nada).

Answer 1

Estoy bastante seguro de que esto es polinómico. Esta es mi idea:

Hay un ciclo impar en un DAG si hay una progresión egde cerrada impar. Para ver " $\Leftarrow$ ": dada una progresión de aristas impar, busca un ciclo en ella. Si no es ya impar, elimínalo de la progresión de aristas. La progresión de aristas resultante sigue siendo impar y está cerrada.

Para encontrar una progresión de aristas impar, se puede utilizar una variante del algoritmo Moore-Bellman-Ford para comprobar para cada vértice si se encuentra en una progresión de aristas cerrada impar. Dado un vértice $s$ , marca $s$ como par y cualquier otro vértice como inalcanzable. Ahora para cada arista $(v, w)$ , si $v$ está marcado como par, marca $w$ como impar (o viceversa); un vértice puede ser marcado tanto como par como impar. Si después de $|V|$ iteraciones $s$ está marcada como impar, se encuentra en una progresión de aristas cerradas impar (se puede encontrar una trazando cómo fue marcada).