Detecte ciclos de peso total ímpar em um gráfico com arestas ponderadas {0,1}

Question

Dado um dígrafo ponderado nas arestas $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, existe um algoritmo que retorna TRUE se existe um ciclo neste gráfico cujo peso total é ímpar e FALSE caso contrário, que corre mais rápido do que $O((|V| + |E|)(c + 1))$ (onde $c$ é o número de ciclos simples no gráfico, que é obviamente $\Ômega(2^{|V|})$)?

Como a pergunta indica, já criei um algoritmo que roda em $O((|V| + |E|)(c + 1))$ tempo.Este algoritmo envolve primeiro a execução Algoritmo de enumeração de ciclo simples de Johnson, o que nos dá todos os ciclos simples no gráfico.Desde even + even = even, e todos os ciclos são feitos somando ciclos simples, o gráfico contém um ciclo de comprimento ímpar se contiver um ciclo simples de comprimento ímpar.Assim, apenas calculamos a paridade dos ciclos simples e retornamos TRUE se algum deles for estranho, e FALSE de outra forma.

Alguém pode criar uma abordagem mais eficiente?Idealmente, um que não seja apenas "substituir o algoritmo de Johnson por outro algoritmo simples de enumeração de ciclo que tenha assintóticos um pouco melhores", já que os gráficos com os quais estou lidando realmente não são tão grandes e fatores constantes podem dominar como resultado.

Answer 1

Você pode resolver isso em $O(|V| \cdot |E|)$ tempo.

Construa um dígrafo com vértices da forma $\langle v,b angle$ onde $v\em V$, $b\in\{0,1\}$, do seguinte modo:para cada borda $v \stackrel{t}{ o} w$ no seu gráfico, adicione as arestas $\langle v,b angle o \langle w,b + t \bmod 2 angle$ para cada $b\in\{0,1\}$ para o novo gráfico.

Então, para cada $v\em V$, verifique se existe um caminho de $\langle v,0 angle$ para $\langle v,1 angle$ ou de $\langle v, 1 angle$ para $\langle v,0 angle$ neste novo gráfico.Isso pode ser feito com duas pesquisas DFS por vértice $v\em V$;cada pesquisa DFS leva $O(|E|)$ tempo, então o tempo total de execução é $O(|V| \cdot |E|)$ tempo.A pesquisa pode ser acelerada decompondo o novo gráfico em componentes fortemente conectados uma vez e depois pesquisando no dag de componentes (o metágrafo).

Answer 2

Construa a matriz de incidência aresta-vértice:linhas correspondem a arestas, colunas a vértices, e há um $1$ se a aresta for incidente ao vértice.Adicione outras colunas cheias de $1$'s.Você quer saber se existe um subconjunto das linhas que somam o vetor $0,\ldots,0,1$ (módulo 2).Você pode descobrir usando a eliminação gaussiana, em tempo polinomial.

O que esta acontecendo aqui?Consideremos a matriz original de incidência aresta-vértice.As linhas correspondentes aos ciclos somam zero, pois cada vértice aparece em exatamente duas arestas.Por outro lado, se tivermos um conjunto de linhas que somam zero, então o grau de cada vértice é par.Começando em uma aresta arbitrária, podemos traçar um passeio que eventualmente se fechará sobre si mesmo.Removemos o ciclo correspondente (que não precisa conter a aresta original) e continuamos.Desta forma, vemos que um conjunto de linhas somando zero corresponde a uma união de ciclos aresta-disjunta.

Ao adicionar um adicional $1$ coluna para a matriz, estamos traçando a paridade do ciclo.Um ciclo ímpar resume-se ao vetor $0,\ldots,0,1$.Por outro lado, se um conjunto de linhas soma $0,\ldots,0,1$, então corresponde a um conjunto de ciclos cuja duração total é ímpar, portanto um dos ciclos é ímpar.

Finalmente, descobrir se um vetor está no espaço linha da matriz é um problema padrão em álgebra linear, que pode ser resolvido usando eliminação gaussiana e algoritmos relacionados.