Detectar ciclos de peso total impar en un gráfico con bordes ponderados {0,1}

Question

Dado un dígrafo ponderado por aristas $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, ¿hay algún algoritmo que devuelva TRUE si hay un ciclo en este gráfico cuyo peso total es impar y FALSE de lo contrario, que corre más rápido que $O((|V| + |E|)(c + 1))$ (dónde $c$ es el número de ciclos simples en el gráfico, que por supuesto es $\Omega(2^{|V|})$)?

Como implica la pregunta, ya se me ocurrió un algoritmo que se ejecuta en $O((|V| + |E|)(c + 1))$ tiempo.Este algoritmo implica ejecutar primero Algoritmo de enumeración de ciclo simple de Johnson, que nos da todos los ciclos simples en el gráfico.Desde even + even = even, y todos los ciclos se forman sumando ciclos simples, el gráfico contiene un ciclo de longitud impar si y solo contiene un ciclo simple de longitud impar.Por lo tanto, simplemente calculamos la paridad de los ciclos simples y devolvemos TRUE si alguno de ellos es impar, y FALSE de lo contrario.

¿Alguien puede encontrar un enfoque más eficiente?Idealmente, uno que no sea simplemente "reemplazar el algoritmo de Johnson con otro algoritmo de enumeración de ciclo simple que tenga asintóticas ligeramente mejores", ya que los gráficos con los que estoy tratando realmente no son tan grandes y, como resultado, los factores constantes bien pueden dominar.

Answer 1

Puedes resolver esto en $O(|V| \cdot |E|)$ tiempo.

Construir un dígrafo con vértices de la forma. $\langle v,b angle$ dónde $v \en V$, $b \en \{0,1\}$, como sigue:para cada borde $v \stackrel{t}{ o} w$ en tu gráfica, suma los bordes $\langle v,b angle o \langle w,b + t \bmod 2 angle$ para cada $b \en \{0,1\}$ al nuevo gráfico.

Entonces, para cada $v \en V$, compruebe si hay una ruta desde $\langle v,0 angle$ a $\langle v,1 angle$ o de $\langle v, 1 angle$ a $\langle v,0 angle$ en este nuevo gráfico.Esto se puede hacer con dos búsquedas DFS por vértice. $v \en V$;cada búsqueda DFS toma $O(|E|)$ tiempo, por lo que el tiempo total de ejecución es $O(|V| \cdot |E|)$ tiempo.La búsqueda se puede acelerar descomponiendo el nuevo gráfico en componentes fuertemente conectados una vez y luego buscando en el dag de componentes (el metagrama).

Answer 2

Construya la matriz de incidencia borde-vértice:las filas corresponden a aristas, las columnas a vértices, y hay una $1$ si la arista incide sobre el vértice.Añade otras columnas llenas de $1$'s.Quiere saber si hay un subconjunto de filas que suman el vector $0,\lpuntos,0,1$ (módulo 2).Puedes averiguarlo mediante eliminación gaussiana, en tiempo polinómico.

¿Que está sucediendo aquí?Consideremos la matriz de incidencia borde-vértice original.Las filas correspondientes a ciclos suman cero, ya que cada vértice aparece exactamente en dos aristas.Por el contrario, si tenemos un conjunto de filas que suman cero, entonces el grado de cada vértice es par.Partiendo de un borde arbitrario, podemos trazar un camino que eventualmente se cerrará sobre sí mismo.Eliminamos el ciclo correspondiente (que no tiene por qué contener el borde original), y continuamos.De esta manera, vemos que un conjunto de filas que suman cero corresponden a una unión de ciclos de borde disjunto.

Al agregar un adicional $1$ columna a la matriz, estamos rastreando la paridad del ciclo.Un ciclo impar se suma al vector. $0,\lpuntos,0,1$.Por el contrario, si un conjunto de filas suma $0,\lpuntos,0,1$, entonces corresponde a un conjunto de ciclos cuya duración total es impar, por lo que uno de los ciclos es impar.

Finalmente, encontrar si un vector está en el espacio de filas de la matriz es un problema estándar en álgebra lineal, que puede resolverse mediante eliminación gaussiana y algoritmos relacionados.