Le problème de chemin le plus long est-il plus facile que le problème de chemin le plus long?

Le problème de chemin le plus long est NP-difficile. La preuve (typique?) Repose sur une réduction du problème du chemin hamiltonien (qui est NP-complet). Notez qu'ici, le chemin est considéré comme (nœud-) simple. Autrement dit, aucun sommet ne peut apparaître plus d'une fois dans le chemin. Évidemment, il est donc également simple (aucun bord ne se produira plus d'une fois dans le chemin).

Que se passe-t-il si nous abandonnons l'exigence de trouver un chemin simple (nœud) et que nous nous en tenons à trouver un chemin simple (piste). À première vue, comme il est beaucoup plus facile de trouver un sentier eulérien que de trouver un chemin hamiltonien, on pourrait espérer qu'il serait plus facile de trouver le chemin le plus long que de trouver le chemin le plus long. Cependant, je ne trouve aucune référence le prouvant, sans parler de celle qui fournit un algorithme.

Notez que je suis au courant de l'argument avancé ici: /programming/8368547/how-to-find-the-longest-heaviest-trail-in-an-undirected-weighted-graph Cependant, l'argument semble imparfait dans sa forme actuelle, car il montre essentiellement que vous pouvez résoudre le cas de bord simple en résolvant le cas de nœud simple sur un graphique différent (la réduction est donc dans le mauvais sens). Il n'est pas certain que la réduction puisse facilement être modifiée pour fonctionner également dans l'autre sens. (Pourtant, cela montre qu'au moins le problème des sentiers les plus longs n'est pas plus difficile que le problème des chemins les plus longs.)

Existe-t-il des résultats connus pour trouver les sentiers les plus longs (sentiers simples)? Complexité (classe)? Algorithme (efficace)?

graph-theory graph-algorithms hamiltonian-paths Jaspe
la source

Ce n'est pas exactement le même problème, mais jetez un œil au problème de l'extension euilérienne minimale qui est assez similaire.

Peut-être que je n'ai pas bien compris la question, mais le chemin hamiltonien est NP-complet même sur les graphiques cubiques, car chaque traversée d'un nœud nécessite deux bords, il n'y a aucun moyen de réutiliser un nœud deux fois même si nous assouplissons la condition de node-simple chemins vers des chemins simples; le problème du chemin hamiltonien reste donc NP-complet.

Marzio De Biasi

@Bangye: ok mais dans les graphes cubiques si un nœud est traversé une fois, alors 2 arêtes doivent être utilisées ... et le nœud ne peut plus être traversé (car il n'y a qu'une arête non traversée). Ainsi, dans les graphiques cubiques, les nœuds ne peuvent pas être "répétés" (sauf pour le dernier bord de la piste qui peut être incident à un nœud déjà traversé)

Marzio De Biasi

Voici la référence: AA Bertossi, The edge hamiltonian path problem is NP-complete, Information Processing Letters, 13 (1981) 157-159.

Lamine

@Lamine: Merci pour la clarification. Je ne pense pas que vous ayez à supprimer vos commentaires, car il serait très naturel de proposer d'abord une idée similaire et voir que cela ne fonctionne pas est vraiment utile.

Yota Otachi

Réponses:

D'après les commentaires ci-dessus: le problème du cycle hamiltonien reste NP-complet même dans les graphiques de grille avec un degré maximum 3 [1], mais dans ces graphiques, chaque traversée d'un nœud nécessite deux bords et au plus un bord reste inutilisé, donc un nœud ne peut pas être traversé deux fois par un chemin eulérien.

Donc, apparemment, il y a une réduction immédiate du problème du cycle hamiltonien à votre problème: étant donné un graphique de grille avec un degré maximum 3 , demandez simplement une traînée de longueur. $G = (V,E)$ $|V|$

Mais les trois bords du nœud à la fin du chemin peuvent être utilisés; pour éviter cette situation, vous pouvez choisir le nœud supérieur gauche du graphique en grille (qui a le degré deux) et ajouter deux nœuds: et de nouveaux bords et demander une traînée de longueur : de manière informelle, le bord ajouté force à être les extrémités du chemin. $u$ $V' = V \cup \{u',u''\}$ $E = E \cup \{(u,u'), (u,u'')\}$ $|V'| = |V|+2$ $u',u''$

[1] Christos H Papadimitriou, Umesh V Vazirani, Sur deux problèmes géométriques liés au problème du voyageur de commerce, Journal of Algorithms, Volume 5, Numéro 2, juin 1984, Pages 231-246, ISSN 0196-6774

Marzio De Biasi
la source

J'ai un peu de mal à marier cela, ainsi que certains des autres commentaires, à la facilité connue de trouver une piste eulérienne. Ou est le point crucial qui (en vous appuyant sur votre exemple) décide s'il existe ou non une traînée "eulérienne" de longueurest plus facile que de décider s'il y a ou non une traînée de longueur? Ce serait certainement un peu une surprise pour moi, mais certainement intéressant.

| E |

$|E|$

| V |

$|V|$

Jasper

Dans les graphiques cubiques, vous êtes sûr qu'il n'y a pas de traînée de longueur, en effet, tous les bords ont un degré impair 3 ( complexité ). Donc, les problèmes de trouver une piste de longueur(avec l'astuce supplémentaire ) est plus difficile (NPC); de manière informelle: pour chaque nœud, il existe trois paires d'arêtes qui peuvent être utilisées pour créer le parcours, et vous ne connaissez pas les "effets" d'un choix tant que vous n'avez pas construit le reste du parcours. Dans un graphique normal, le chemin eulérien est facile à calculer car à chaque étape, vous pouvez être sûr de pouvoir "revenir" au nœud de départ (voir l'algorithme de Fleury).

| E |

$|E|$

O (1)

$O(1)$

| V |

$|V|$

u^{'}, u^{″}

$u',u''$

Marzio De Biasi