Cycle le plus long contenu en deux cycles

Le problème suivant est-il NP-complet? (Je suppose que oui).

Entrée: un graphique non orienté où l'ensemble de bords peut être décomposé en deux cycles simples à bords séparés (ceux-ci ne font pas partie de l'entrée). $k \in \mathbb{N},G=(V,E)$

Question: Existe - t-il un cycle simple en de longueur supérieure à ? $G$ $k$

Évidemment, le problème est dans NP et le degré maximum dans est , mais cela ne semble pas aider. $G$ $\leq 4$

graph-theory np-complete decision-problem Référencement
la source

Je ne pense pas que vous ayez raison sur "au plus 4 chemins reliant n'importe quelle paire". Voir: i.imgur.com/mYL4n1V.png

svinja

@svinja Vous avez raison, j'aurais dû dire qu'au plus 4 chemins disjoints de bord par paire existent entre n'importe quelle paire de deux sommets.

Listing

Votre titre est trompeur, car le cycle simple le plus long ne peut être aucun des deux cycles de décomposition de

(dans toute décomposition).

E

$E$

Denis

@dkuper ça peut en fait, regarder l'union de deux cycles simples disjoints de vertex.

Listing

Ce que je veux dire, ce n'est pas qu'il ne puisse jamais être l'un d'entre eux, c'est que parfois ce n'est pas l'un d'entre eux. Le problème n'est donc pas de trouver le plus gros des deux.

Denis

Réponses:

Une tentative de réduction ....

Réduction du chemin hamiltonien sur le digraphe avec un degré max 3 qui est NPC [G&J] $G = (V,E)$

ignorer la direction des bords, et en utilisant un premier balayage de profondeur (non orienté) à partir d'un nœud arbitraire, divisez les bords de en deux ensembles de chemins distincts (non orientés) (rouge et vert sur les figures); $G$
rejoindre les chemins rouges en ajoutant des "nœuds de liaison" supplémentaires (nœuds violets sur la figure B) et faire un circuit rouge non dirigé; rejoindre les chemins verts en ajoutant des "nœuds de liaison" supplémentaires (nœuds violets sur la figure) et faire un circuit vert non orienté;
transformer chaque nœud d'origine de degré 1 et de degré 2 (figure C), en ajoutant nœuds jaunes sur le bord rouge entrant , et en ajoutant nœuds jaunes sur le premier bord rouge sortant ; ajouter enfin nœuds jaunes "vers" le deuxième bord vert sortant utilisant un chemin "enveloppé" autour de qui touche les nœuds jaunes les plus externes des bords rouges (figure D). $b \in V$ $k$ $a\to b$ $k$ $b \to c$ $k$ $b \to d$ $b$

Dans le graphe résultant, tous les nœuds jaunes ne peuvent être parcourus par un chemin simple que dans les deux sens représentés sur la figure E et la figure F, qui correspondent aux deux traversées valides du nœud d'origine ; de manière informelle si un bord vers le nœud violet supplémentaire "de liaison" est utilisé, nœuds jaunes ne peuvent pas être traversés. $3k$ $b \in V$ $k$

transformer chaque nœud d'origine de V de degré 2 et de degré 1 de manière similaire

Choisir un assez grand , le graphe résultant a un chemin simple de longueur supérieure à si et seulement si le graphe original a un chemin hamiltonien (de longueur ) $k \gg |V|$ $G'$ $3k(|V|-1)$ $G$ $|V|-1$

entrez la description de l'image ici

L'image plus grande peut être téléchargée ici

Vor
la source

C'est une très belle preuve, peut-être devriez-vous orienter les bords de la figure 'A' pour qu'il soit plus facile de comprendre comment obtenir les chemins (je pense que je l'ai compris cependant).

Listing

@Listing: la construction des chemins ne dépend pas des bords dirigés (en effet j'ai écrit la recherche "non dirigée" dans la réponse). Vous devez commencer à partir d'un nœud arbitraire, faire un premier balayage en profondeur à partir de celui-ci en colorant en rouge les bords traversés, puis revenir en arrière jusqu'au nœud du premier degré 3 rencontré et continuer le premier balayage en profondeur à partir de celui-ci en coloriant en vert les bords traversés, etc. .. peut-être qu'il a une définition plus formelle, mais cela ne me vient pas à l'esprit maintenant. Faites-moi savoir si vous avez besoin de plus de détails.

Vor

Je vois, la propriété que les bords sont traversés dans la direction «correcte» est renforcée par la dernière transformation. Merci pour la clarification.

Listing

Inspiré par la réponse de Vor, je veux donner une réponse plus simple.

Commençons par le problème du cycle hamiltonien pour le problème des graphiques en grille qui a été prouvé par Itai.

On peut facilement voir qu'un ensemble de bords d'un graphe peut être partitionné en 2 sous-ensembles disjoints: horizontal et vertical.

Alors maintenant, nous devons tisser tous les horizontaux dans un cycle simple, et tisser tous les verticaux dans un autre cycle simple.

C'est une tâche très facile: pour les verticales, balayez de gauche à droite, connectez simplement les espaces verticaux, puis connectez la ligne verticale coordonnée x consécutive, puis connectez le sommet le plus à gauche le plus bas avec le sommet le plus à droite. Faites de même pour les bords horizontaux.

Notez que le graphique obtenu est toujours simple, non orienté et satisfait aux exigences. C'est simple car aux dernières étapes de la phase verticale et de la phase horizontale, nous avons affaire à deux paires de sommets différentes.

$k$ $k$ $2k|V|$

Thinh D. Nguyen
la source