Trouver un cycle négatif avec des contraintes de sommet

Étant donné un graphique avec des arêtes pondérées, comment trouver un cycle négatif qui contient au moins un sommet dans un ensemble de sommets donné ? Merci.$\{V_1, V_2, \ldots, V_k\}$

Si vous n'avez pas besoin que le cycle soit simple, alors divisez le graphe (dirigé) en ses composants fortement connectés, et pour chaque composant contenant l'un des sommets donnés , vérifiez si le composant contient un cycle négatif. Si aucun composant ne le fait, il n'y a pas de cycle négatif contenant un . Mais si certains composants le font, vous pouvez trouver un cycle négatif (non simple) contenant en prenant de nombreuses copies du cycle négatif et en ajoutant à ces chemins vers et depuis un sommet du cycle vers . (Le temps total pour trouver une représentation implicite du cycle souhaité sera le même que le temps pour trouver un cycle négatif dans un graphique dirigé, par exemple , si je me souviens bien.)V i V i V i O ( n m $V_i$$V_i$$V_i$$V_i$$O(nm)$

Si vous avez besoin que le cycle soit simple, alors le problème devient NP-complet, même si un seul sommet est donné. (Vous pouvez réduire le chemin hamiltonien au problème: pour trouver un chemin hamiltonien d'une source donnée à un puits donné dans un graphe donné , donnez le poids des arêtes existantes -1, puis ajoutez un sommet artificiel avec deux arêtes de coût chacun, un de à et un de à .) S T G V 1 N / 2 - 0,01 V 1 S T V $V_1$$S$$T$$G$$V_1$$N/2-0.01$$V_1$$S$$T$$V_1$

Si vous autorisez le cycle à répéter les sommets mais pas les arêtes, je pense qu'il est toujours NP-complet (par une réduction similaire, mais en divisant chaque sommet en une arête dirigée de manière standard).( v , v ′$v$$(v,v')$

Je vais supposer que votre entrée est un graphique dirigé; Je ne sais pas comment faire cela pour le cas non dirigé.

Faites copies de l'ensemble de sommets de votre graphique, où est le nombre de sommets du graphique. Remplacez chaque arête de à dans votre graphique d'origine par des arêtes allant de la copie de à la copie de , pour tous les choix de . De plus, si appartient à l'ensemble de sommets spécifié mais pas autrement, incluez également une arête qui va de la copie de à la copie de .n u v i u i + 1 $n$$n$$u$$v$$i$$u$$i+1$$v$u i u 0 $i$$u$$i$$u$$0$$v$

Les cycles du graphique développé se projettent tous vers le bas jusqu'aux cycles du graphique d'origine, mais chaque cycle du graphique développé contient l'un des sommets spécifiés (sinon vous ne pouvez pas reculer dans les couches d'expansion), donc le graphique d'origine contient un cycle négatif contenant un sommet spécifié si le graphique développé ne contient aucun cycle négatif.