Détecter les cycles de petits poids total dans un graphe à {0,1}-pondéré bords

Question

Jouir d'un avantage pondérée par le digraphe $G = (V, E \subseteq V^2, w \in E \ \ pour \{0, 1\})$, est-il un algorithme qui retourne TRUE si il y a un cycle dans ce graphe dont le poids total est impair et FALSE sinon, qui court plus vite que $O (|V| + |E|)(c + 1))$ (où $c$ est le nombre de cycles simples dans le graphe, ce qui est évidemment $\Omega(2^{|V|})$)?

Comme la question l'indique, j'ai déjà venu avec un algorithme qui s'exécute en $O (|V| + |E|)(c + 1))$ temps.Cet algorithme implique d'abord de course Johnson cycle simple algorithme d'énumération, qui nous donne à tous la simple cycles dans le graphe.Depuis even + even = even, et tous les cycles sont effectués par l'addition simple des cycles, le graphe contient un cycle de longueur impaire ssi il contient un simple cycle de longueur impaire.Ainsi, nous pouvons calculer la parité des cycles simples et retour TRUE si l'un d'eux sont impairs, et FALSE sinon.

Quelqu'un peut venir avec une approche plus efficace?Idéalement, celui qui n'est pas juste "remplacer l'algorithme de Johnson avec un autre cycle simple algorithme d'énumération qui a un peu mieux asymptotique", depuis les graphiques que je traite ne sont pas vraiment que grand, et des facteurs constants pourrait bien dominer comme un résultat.

Answer 1

Vous pouvez résoudre ce problème en $O(|V| \cdot |E|)$ temps.

La construction d'un digraphe avec les sommets de la forme $\langle v,b angle$ où $v \in V$, $b \in \{0,1\}$, comme suit:pour chaque bord $v \stackrel{t}{\pour} w$ dans votre graphique, ajouter les bords $\langle v,b angle \pour \langle w,b + t \bmod 2 angle$ pour chaque $b \in \{0,1\}$ pour le nouveau graphe.

Ensuite, pour chaque $v \in V$, vérifiez s'il existe un chemin de $\langle v,0 angle$ pour $\langle v,1 angle$ ou de $\langle v, 1 angle$ pour $\langle v,0 angle$ dans ce nouveau graphe.Cela peut être fait avec deux DFS recherches par vertex $v \in V$;chaque DFS recherche prend $O(|E|)$ temps, de sorte que le temps total d'exécution est $O(|V| \cdot |E|)$ temps.La recherche peut être accéléré par la décomposition de ce nouveau graphe en composantes fortement connexes une fois et puis la recherche dans le groupe de composants (metagraph).

Answer 2

Construire le bord sommet de l'incidence de la matrice:les lignes correspondent aux bords, les colonnes de sommets, et il y a un $1$ si l'arête est incidente au sommet.Ajouter un autre colonnes plein de $1$s'.Vous voulez savoir si il existe un sous-ensemble de lignes résumant le vecteur $0,\ldots,0,1$ (modulo 2).Vous pouvez trouver à l'aide de l'élimination de Gauss, en temps polynomial.

Ce qui se passe ici?Penchons-nous sur l'origine de bord-sommet de l'incidence de la matrice.Les lignes correspondant à des cycles de somme nulle, puisque chaque sommet apparaît dans exactement deux bords.A l'inverse, si nous avons un ensemble de lignes résumant à zéro, alors le degré de chaque sommet est même.Départ à l'arbitraire d'un bord, on peut retrouver la trace d'un pied, qui va finalement fermer sur lui-même.Nous allons supprimer le cycle correspondante (qui n'a pas besoin de contenir de l'arête d'origine), et de continuer.De cette façon, nous voyons que d'un ensemble de lignes résumant à zéro correspond à une arête-disjoints de l'union de cycles.

En ajoutant $1$ colonne de la matrice, nous traçons la parité du cycle.Une drôle de cycles sommes jusqu'à le vecteur $0,\ldots,0,1$.A l'inverse, si un ensemble de lignes de sommes $0,\ldots,0,1$, puis il correspond à un ensemble de cycles dont la longueur totale est impair, donc, l'un des cycles est impair.

Enfin, si un vecteur est dans la ligne de l'espace de la matrice est un problème classique d'algèbre linéaire, qui peut être résolu à l'aide de l'élimination de Gauss et liées à des algorithmes.