Classes de graphes où les problèmes de cycle hamiltonien et de chemin hamiltonien ont une complexité différente

En recherchant le système d'information sur les classes de graphes et leurs inclusions , j'ai trouvé plusieurs classes de graphes pour lesquelles le problème du cycle hamiltonien est NP-complet alors que la complexité des problèmes de chemin hamiltonien n'est PAS connue. Certaines de ces classes sont des graphiques bipartites de degré 3 maximum, des graphiques de grille de degré 3 maximum et des graphiques planaires cubiques à 2 connexions. Ce phénomène s'applique également aux graphiques circulaires et aux graphiques à grille triangulaire.

Existe-t-il une mise à jour de la complexité du problème de chemin hamiltonien sur ces classes? Y a-t-il une explication à ce phénomène?

EDIT : J'ai trouvé dans la base de données des classes de graphes un cas étrange de graphes à grille solide où le problème du cycle hamiltonien est en tandis que le problème du chemin hamiltonien est d' une complexité inconnue . $P$

cc.complexity-theory graph-theory Mohammad Al-Turkistany
la source

Je me demande s'il existe une classe de graphes intéressante pour laquelle HP est en

mais HC est

complet.

P

$P$

N P

$NP$

Mohammad Al-Turkistany

En général, existe-t-il une classe de graphes pour laquelle l'un des problèmes (HC et HP) est

complet et l'autre est en

ou en

? Je recherche des résultats publiés pour les problèmes HC et HP.

N P

$NP$

P

$P$

N P I

$NPI$

Mohammad Al-Turkistany

Pour ce que ça vaut (pas beaucoup), Hamiltonian Path et Hamiltonian Cycle ont une complexité différente sur les arbres: le cycle est trivial mais le chemin nécessite un balayage linéaire pour voir s'il y a un sommet de degré supérieur à deux.

David Richerby

Il est peu probable que HP soit en

et HC soit

-complet pour n'importe quelle classe de graphique car il y a une réduction de Cook de HC à HP qui fait au plus

appels vers l'oracle de HP. La vraie question est de savoir s'il existe une réduction de Karp (

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

H C <_{P}^{m} H P

$HC<_P^m HP$

Mohammad Al-Turkistany

Réponses:

Le problème du chemin hamiltonien sur les graphes de grille avec un degré maximum 3 est NP-complet. La preuve se trouve dans CH Papadimitriou et UV 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 (Théorème 2)

Marzio De Biasi
la source

Merci Marzio, utilisent-ils la même définition que celle utilisée dans la base de données pour les graphiques en grille? (car ce sont des définitions différentes dans la littérature)

Mohammad Al-Turkistany

Un graphe est un sous-graphe fini induit par des nœuds de

, le graphe infini dont l'ensemble des sommets se compose de tous les points du plan avec des coordonnées entières et dans lequel deux sommets sont connectés si et seulement si la distance euclidienne entre eux est 1; un graphe peut donc avoir des "trous" et le théorème est prouvé (limité à) des graphes dans lesquels les sommets ont un degré maximum 3.

G^{\infty}

$G^\infty$

Marzio De Biasi

Merci Marzio, donc, pour cette classe, HC et HP ont la même complexité.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: une autre remarque: les graphiques en grille (et les graphiques en grille avec un degré maximum 3) sont également bipartis, donc HP devrait être NP-complet pour les graphiques bipartites avec un degré maximum 3 aussi.

Marzio De Biasi

Il y a eu une mise à jour du système d'information sur les classes de graphes et leurs inclusions. Maintenant, le problème du cycle hamiltonien et le problème du chemin hamiltonien sont déclarés NP-complets sur des graphes planaires cubiques à 2 connexions.

Cependant, la complexité des problèmes informatiques HC et HP sont répertoriés inconnu pour un problème et NP-complet pour l'autre sur des diagrammes circulaires , des graphiques de grille triangulaires et graphiques de grille solides .

Mohammad Al-Turkistany
la source

Vous dites "... les complexités des problèmes HC et HP sont toujours différentes ..."; peut-être vaut-il mieux dire que "pour ces classes de graphes, HC est NPC, mais HP a encore une complexité inconnue"

Marzio De Biasi

@MarzioDeBiasi Merci pour votre précieux commentaire. J'ai modifié pour refléter votre suggestion.

Mohammad Al-Turkistany

Dois-je manquer quelque chose? HC est soluble dans le temps polynomial dans les graphiques à grille solide. ieeexplore.ieee.org/document/646138

Saeed