Cycle de poids négatif vs cycle de poids maximum

J'ai du mal à comprendre pourquoi il est facile de détecter les cycles de poids négatifs (Bellman Ford) mais difficile de trouver le cycle de poids maximal dans un graphique non orienté.

Si nous nions le poids de chaque bord, nous pouvons facilement trouver s'il y a des cycles avec un poids total> 0. Cependant, il ne doit pas être facile de trouver s'il y a des cycles avec un poids> 1 ou bien nous pourrions répéter avec 2, 3 , 4 etc jusqu'à ce que la réponse soit non.

Est-ce correct? Pourquoi est-il tellement plus difficile de détecter s'il existe un cycle avec un poids> 1 puis de trouver s'il y a un cycle avec un poids> 0?

Je ne pense pas qu'il soit très surprenant qu'il soit plus facile de trouver un seul cycle de poids négatif que de trouver le cycle de poids le plus élevé. Si vous me demandez de trouver un cycle de poids négatif, je peux en trouver un et, si je vous donne ce que je prétends être une réponse, il est très facile pour vous de vérifier la séquence des sommets et de voir que le poids est vraiment négatif. Mais le cycle de poids maximum ressemble à un objet très spécial. Même si je prétendais l'avoir trouvé, comment pourrais-je vous convaincre qu'il n'y a pas un autre cycle avec un poids encore plus élevé?

D'un autre côté, cette intuition n'est peut-être pas utile, car il est également trivial de vérifier qu'un cycle donné a un poids d'au moins 1 ou 2 ou 17 ...

Ceci est une excellente question. Je n'ai pas d'explication pleinement satisfaisante, mais permettez-moi de vous donner un début.

Tout d'abord, il est important de comprendre que nous ne pouvons pas résoudre ce problème en énumérant simplement tous les cycles et en vérifiant le poids de chacun. Pourquoi pas? Parce qu'il peut y avoir (et il y en a souvent) de façon exponentielle de nombreux cycles. Par conséquent, le simple fait de les énumérer prendra nécessairement un temps exponentiel - trop long pour être réalisable.

Alors, comment fonctionne Bellman-Ford? Il fonctionne par une astuce astucieuse qui évite d'avoir à examiner individuellement chaque cycle un par un. Au lieu de cela, il construit un résumé qui résume quelque chose sur l'effet de tous les chemins et cycles de longueur jusqu'à$n$. Effectivement, pour chaque sommet$v$, il résume tous les chemins qui commencent à $v$, Fin à $v$, et prendre tout au plus $n$pas. Étant donné que chaque cycle doit contenir un chemin de cette forme, le résumé résume en quelque sorte l'effet de tous les cycles possibles.

Pourquoi ne pouvons-nous pas l'utiliser pour détecter (par exemple) s'il existe un cycle de poids $\ge 1$? C'est parce que le résumé de Bellman-Ford comprend des chemins qui parcourent le cycle plusieurs fois. Si le cycle est de longueur$k$, alors ça va inclure des chemins de longueur $n$, c.-à-d. des chemins qui parcourent le cycle $n/k$fois. Par exemple, si vous avez un cycle de longueur$n/3$, le résumé inclut un chemin qui fait trois fois le tour du cycle.

Quel est l'effet de marcher plusieurs fois sur un cycle? Si vous voulez distinguer les cycles de poids positif des cycles dont le poids n'est pas positif, faire plusieurs fois le tour d'un cycle ne fait pas de mal. Si le cycle a un poids positif, vous pouvez le contourner plusieurs fois et le poids total sera toujours positif. Si le poids du cycle n'est pas positif, vous pouvez le contourner plusieurs fois et le poids total sera toujours non positif. Donc, si nous nous soucions uniquement de la différence entre le poids positif et le poids non positif, faire plusieurs fois le tour du cycle ne fait pas de mal.

Mais considérons maintenant comment les choses changent si ce qui nous importe est la différence entre $\ge 1$"vs" poids $< 1$". Si nous avons un cycle dont le poids est $< 1$ et nous parcourons ce cycle plusieurs fois, le poids total pourrait devenir $\ge 1$. Par exemple, si le poids du cycle est$1/2$ et nous parcourons le cycle trois fois, puis le poids total de ce chemin est $1.5$, lequel est $\ge 1$: nous avons commencé avec un cycle de poids $< 1$ et a fini avec un chemin de poids $\ge 1.5$. Ce fait fout totalement Bellman-Ford et le rend inutile pour vérifier s'il existe un cycle de poids$\ge 1$. (Voyez-vous la différence?)

Je me rends compte que ce n'est pas une réponse 100% satisfaisante. Il vous explique pourquoi Bellman-Ford ne va pas travailler pour résoudre votre problème. Cependant, cela ne vous donne aucune intuition pour expliquer pourquoi cela est difficile en général (par exemple, pourquoi il est difficile de trouver un autre algorithme pour le résoudre). Je n'ai pas vraiment une bonne intuition pour ça - peut-être que quelqu'un d'autre aura une meilleure explication pour vous. En attendant, cela vous donne peut-être un aperçu de la raison pour laquelle ce problème est difficile.

Décider $weight \geq c$ est toujours facile pour toute constante $c$et les poids de bord entiers. Je peux vérifier tous les cycles de longueur$c$ dans $O(n^c)$(en supposant des poids unitaires). Mais si$c$ n'est pas une constante, par exemple $c=n/2$? Ce ne serait plus un polynôme.

Par contre avec le problème général de décision (ie quand $c$ n'est pas constant), nous pouvons décider du problème du cycle hamiltonien qui est NP-complet.

Considérons les versions plus simples de ces problèmes où les arêtes ne sont pas pondérées.

1. Étant donné un graphique $G$, vérifier si $G$ a un cycle.

2. Étant donné un graphique $G$ et un certain nombre $k$, vérifier si $G$ a un cycle de longueur au moins $k$.

Le premier est facile et peut être résolu en utilisant DFS. Le second est NP-dur.

Regardons un problème encore plus simple:

1. Étant donné un graphique $G$ et deux sommets $s$ et $t$, vérifiez s'il existe un chemin simple à partir de $s$ à $t$ dans $G$.

2. Étant donné un graphique $G$ et deux sommets $s$ et $t$ et un certain nombre $k$, vérifiez s'il existe un chemin simple à partir de $s$ à $t$ dans $G$ de longueur au moins $k$.

Tous ces problèmes ont la même saveur. Celui du haut est facile tandis que celui du bas est dur NP. Je vais expliquer la différence pour le dernier car c'est plus simple mais la même explication s'applique aux autres paires.

La raison pour laquelle ceux du haut sont faciles alors que ceux du bas ne le sont pas est le résultat de la structure des réponses à ces problèmes.

Examinons d'abord le problème de la recherche d'un chemin simple et essayons de le résoudre récursivement. Si nous essayons simplement de résoudre ce problème directement, nous aurions besoin de garder une trace des sommets que nous avons utilisés jusqu'à présent:

$SimplePath(s,t,G) :=$ il y a un chemin de $s$ à $t$ dans $G$.

$SimplePath(s,t,G)$ ssi
$s=t$ ou pour certains $u\in G$ $SimplePath(s,u,G-t)$ et $ut \in G$.

Si nous essayons de résoudre le problème avec cet algorithme récursif naïf, cela prendra du temps exponentiel: il y a exponentiellement de nombreuses possibilités pour l'ensemble des sommets inutilisés! Nous devons être plus intelligents.

Pourquoi avons-nous obtenu de façon exponentielle de nombreuses possibilités? Parce que nous essayions de trouver un chemin simple et d'appliquer cette condition, nous devions garder une trace des sommets inutilisés.

OK, alors abandonnons cette condition et voyons où nous pouvons obtenir:

Considérez le problème de trouver un chemin (pas nécessairement simple) à partir de $s$ à $t$. Puisque le chemin n'a pas besoin d'être simple, nous n'avons pas besoin de garder une trace des sommets inutilisés. En d'autres termes, le graphique ne change pas avec le temps.

$Path^G(s,t) :=$ il y a un chemin de $s$ à $t$.

$Path^G(s,t)$ ssi
$s=t$ou
pour certains$u\in G$ $Path^G(s,t)$ et $ut \in G$.

Mais nous n'avons pas encore fini. Le problème est que nous ne savons pas si$Path^G(s,u)$ est un problème plus petit que $Path^G(s,t)$. Cette solution récursive peut donc se terminer en boucle et ne jamais se terminer.

Pour éviter cela, nous pouvons ajouter un paramètre supplémentaire qui s'assure que le problème diminue: le nombre d'arêtes dans le chemin.

$Path^G(s,t,k) :=$ il y a un chemin de $s$ à $t$ avec au plus $k$ bords.

$Path^G(s,t,k)$ ssi
$k=0$ et $s=t$ ou
$k>0$ et pour certains $u\in G$ $Path^G(s,u,k-1)$ et $ut \in G$.

Notez maintenant qu'il existe un chemin simple de $s$ à $t$ ssi il y a un chemin de $s$ à $t$ avec au plus $n$bords. En d'autres termes:

$SimplePath(s,t,G)$ ssi $Path^G(s,t,n)$.

Les points essentiels ici sont:

1. Chaque chemin simple (non trivial) de $s$ à $t$ consiste en un chemin simple de $s$ à un sommet $u$ et un bord $ut$.

2. On peut supposer que $t$ n'apparaît pas dans le chemin simple de $s$ à $u$.

3. Nous n'avons pas besoin de conserver explicitement la liste des sommets inutilisés.

Ces propriétés nous permettent d'avoir une récursivité intelligente pour l'existence d'un problème de chemin simple.

Maintenant, ceux-ci ne s'appliquent pas au problème de trouver un chemin de longueur au moins $k$. Nous ne savons pas comment réduire au moins le problème de trouver un chemin simple de longueur$k$ à un sous-problème plus petit sans conserver la liste des sommets inutilisés. Ces propriétés nous permettent de résoudre efficacement l'existence d'un problème de chemin.

Lorsqu'un graphe n'a pas de cycle négatif, il nous permet de résoudre l'existence d'un chemin de longueur au plus $k$ problème et les problèmes de chemin simple les plus courts efficacement.

Cependant, ils ne tiennent pas à l'existence d'un chemin de longueur au moins $k$. Considérons un graphique avec$3$ sommets $s, u, t$. $w(su) =1000, w(st) =1000, w(ut)=10, w(tu)=10$. Le chemin de la longueur au moins$1001$ de $s$ à $t$ contient $u$ et le chemin de longueur au moins $1001$ de $s$ à $u$ contient $t$. Nous ne pouvons donc pas réduire une instance du problème à une instance plus petite du problème sans donner explicitement la liste des sommets inutilisés.

En d'autres termes, nous ne connaissons pas de récursivité intelligente pour l'existence d'un chemin simple de longueur au moins $k$ problème alors que nous connaissons une récursivité intelligente pour l'existence d'un chemin simple.

Pour revenir à la dernière partie de votre question, il y a un problème avec votre argument.

Il est en effet vrai que l'existence d'un cycle de longueur $>k$ peut être résolu en temps polynomial pour tout fixe $k$ (c'est à dire $k$ne fait pas partie de l'entrée). (Similaire à la façon dont on peut vérifier si un graphique non pondéré a un cycle de longueur$k$ à l'heure $O(n^k)$.)

Cependant quand $k$ fait partie de l'entrée cela ne tient plus puisque le temps de fonctionnement dépend de $k$ dans le mauvais sens.