Clases de grafos donde los problemas del Ciclo Hamiltoniano y del Camino Hamiltoniano tienen una complejidad diferente

Mientras buscaba en el Sistema de información sobre clases de gráficos y sus inclusiones , encontré varias clases de gráficos para las cuales el problema del Ciclo Hamiltoniano es NP completo, mientras que la complejidad de los problemas del Camino Hamiltoniano NO se conoce. Algunas de esas clases son gráficos bipartitos de grado máximo 3, gráficos de cuadrícula de grado máximo 3 y gráficos planos cúbicos conectados a 2. También este fenómeno se aplica a los gráficos circulares y a los gráficos de cuadrícula triangular.

¿Existe una actualización de la complejidad del problema del camino hamiltoniano en esas clases? ¿Hay alguna explicación para este fenómeno?

EDITAR : En la base de datos de clases de gráficos encontré un caso extraño de gráficos de cuadrícula sólida donde el problema del ciclo hamiltoniano está en mientras que el problema del camino hamiltoniano es de complejidad desconocida . $P$

cc.complexity-theory graph-theory Mohammad Al-Turkistany
fuente

Me pregunto si hay una clase de gráfico interesante para la cual HP está en

pero HC es

-completo.

P

$P$

N P

$NP$

Mohammad Al-Turkistany

En general, ¿hay alguna clase de gráfico para la cual uno de los problemas (HC y HP) es

-completo y el otro está en

o en

? Estoy buscando resultados publicados para problemas de HC y HP.

N P

$NP$

P

$P$

N P I

$NPI$

Mohammad Al-Turkistany

Para lo que vale (no mucho), Hamiltonian Path y Hamiltonian Cycle tienen una complejidad diferente en los árboles: el ciclo es trivial, pero la ruta requiere una exploración lineal para ver si hay un vértice de grado superior a dos.

David Richerby

Es poco probable que HP esté en

y HC sea

-completo para cualquier clase de gráfico ya que hay una reducción de Cook de HC a HP que hace como máximo llamadas

al oráculo de HP. La verdadera pregunta es si existe una reducción de Karp (

P

$P$

N P

$NP$

O (| E |)

$O(|E|)$

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

$HC<_P^m HP$

Mohammad Al-Turkistany

Respuestas:

El problema del camino hamiltoniano en los gráficos de cuadrícula con un grado máximo 3 es NP-completo. La prueba está en CH Papadimitriou y UV Vazirani, Sobre dos problemas geométricos relacionados con el problema del vendedor ambulante, Journal of Algorithms, Volumen 5, Número 2, junio de 1984, páginas 231–246 (Teorema 2)

Marzio De Biasi
fuente

Gracias Marzio, ¿están utilizando la misma definición utilizada en la base de datos para los gráficos de cuadrícula? (ya que son definiciones diferentes en la literatura)

Mohammad Al-Turkistany

Un gráfico de cuadrícula es un subgrafo finito inducido por nodos de

, el gráfico infinito cuyo conjunto de vértices consta de todos los puntos del plano con coordenadas enteras y en el que dos vértices están conectados si y solo si la distancia euclidiana entre ellos es 1; por lo que un gráfico de cuadrícula puede tener "agujeros" y el teorema se prueba para (restringido a) gráficos de cuadrícula en los que los vértices tienen un grado máximo 3.

G^{\infty}

$G^\infty$

Marzio De Biasi

Gracias Marzio, entonces, para esta clase, HC y HP tienen la misma complejidad.

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: otra nota: los gráficos de cuadrícula (y los gráficos de cuadrícula con un grado máximo 3) también son bipartitos, por lo que HP también debe ser NP-completo para los gráficos bipartitos con grado máximo 3.

Marzio De Biasi

Ha habido una actualización del Sistema de información sobre clases de grafos y sus inclusiones. Ahora, el problema del ciclo hamiltoniano y el problema del camino hamiltoniano se declaran NP completos en gráficos planos cúbicos conectados a 2.

Sin embargo, las complejidades computacionales de los problemas de HC y HP se enumeran como desconocidas para un problema y NP-completo para el otro en gráficos circulares , gráficos de cuadrícula triangular y gráficos de cuadrícula sólida .

Mohammad Al-Turkistany
fuente

Usted dice "... las complejidades de los problemas de HC y HP siguen siendo diferentes ..."; quizás sea mejor decir que "para estas clases de gráficos HC es NPC, pero HP aún tiene una complejidad desconocida"

Marzio De Biasi

@MarzioDeBiasi Gracias por tu valioso comentario. Lo edité para reflejar su sugerencia.

Mohammad Al-Turkistany

¿Echo de menos algo? HC es tiempo polinómico solucionable en gráficos de cuadrícula sólida. ieeexplore.ieee.org/document/646138

Saeed