Rileva cicli di peso totale dispari in un grafico con bordi ponderati {0,1}

Question

Dato un digrafo ponderato per gli archi $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, esiste un algoritmo che restituisce TRUE se in questo grafico è presente un ciclo il cui peso totale è dispari e FALSE altrimenti, che funziona più velocemente di $O((|V| + |E|)(c + 1))$ (Dove $c$ è il numero di cicli semplici nel grafico, che ovviamente è $\Omega(2^{|V|})$)?

Come suggerisce la domanda, ho già trovato un algoritmo che funziona $O((|V| + |E|)(c + 1))$ tempo.Questo algoritmo prevede la prima esecuzione Algoritmo di enumerazione dei cicli semplici di Johnson, che ci fornisce tutti i cicli semplici nel grafico.Da even + even = even, e tutti i cicli sono ottenuti sommando cicli semplici, il grafico contiene un ciclo di lunghezza dispari se e solo se contiene un ciclo semplice di lunghezza dispari.Pertanto, calcoliamo semplicemente la parità dei cicli semplici e restituiamo TRUE se qualcuno di loro è strano, e FALSE Altrimenti.

Qualcuno può trovare un approccio più efficiente?Idealmente, uno che non si limiti a "sostituire l'algoritmo di Johnson con un altro semplice algoritmo di enumerazione del ciclo che abbia asintotici leggermente migliori", poiché i grafici con cui ho a che fare in realtà non sono così grandi e di conseguenza i fattori costanti potrebbero dominare.

Answer 1

Puoi risolverlo in $O(|V| \cdot |E|)$ tempo.

Costruisci un digrafo con i vertici della forma $\angolo v,b\angolo$ Dove $v \in V$, $b \in \{0,1\}$, come segue:per ciascun bordo $v \stackrel{t}{ o} w$ nel tuo grafico, aggiungi gli spigoli $\langle v,b angle o \langle w,b + t \bmod 2 angle$ per ciascuno $b \in \{0,1\}$ al nuovo grafico.

Quindi, per ciascuno $v \in V$, controlla se esiste un percorso da $\langle v,0 angle$ A $\langle v,1 angle$ o da $\angolo v, 1\angolo$ A $\langle v,0 angle$ in questo nuovo grafico.Questo può essere fatto con due ricerche DFS per vertice $v \in V$;richiede ogni ricerca DFS $O(|E|)$ tempo, quindi il tempo di esecuzione totale è $O(|V| \cdot |E|)$ tempo.La ricerca può essere accelerata scomponendo una volta il nuovo grafo in componenti fortemente connesse e poi cercando nel gruppo delle componenti (il metagrafo).

Answer 2

Costruisci la matrice di incidenza bordo-vertice:le righe corrispondono ai bordi, le colonne ai vertici e c'è a $1$ se il bordo è incidente al vertice.Aggiungi un'altra colonna piena di $1$'S.Vuoi sapere se esiste un sottoinsieme delle righe che si sommano al vettore $0,\ldots,0,1$ (modulo 2).Puoi scoprirlo usando l'eliminazione gaussiana, in tempo polinomiale.

Cosa sta succedendo qui?Consideriamo la matrice di incidenza bordo-vertice originale.Le righe corrispondenti ai cicli si sommano a zero, poiché ciascun vertice appare esattamente in due bordi.Viceversa, se abbiamo un insieme di righe la cui somma è zero, allora il grado di ciascun vertice è pari.Partendo da un bordo arbitrario, possiamo tracciare un cammino che alla fine si chiuderà su se stesso.Rimuoviamo il ciclo corrispondente (che non deve necessariamente contenere il bordo originale) e continuiamo.In questo modo, vediamo che un insieme di righe la cui somma è zero corrisponde a un'unione di cicli disgiunti per archi.

Aggiungendo un ulteriore $1$ colonna alla matrice, stiamo tracciando la parità del ciclo.Un ciclo dispari si somma al vettore $0,\ldots,0,1$.Al contrario, se la somma di un insieme di righe è pari a $0,\ldots,0,1$, allora corrisponde a un insieme di cicli la cui lunghezza totale è dispari, quindi uno dei cicli è dispari.

Infine, scoprire se un vettore si trova nello spazio delle righe della matrice è un problema standard in algebra lineare, che può essere risolto utilizzando l'eliminazione gaussiana e i relativi algoritmi.