¿Hay algún problema que sea fácil para el gráfico cúbico pero difícil para los gráficos con un grado máximo 3?

Los gráficos cúbicos son gráficos en los que cada vértice tiene grado 3. Se han estudiado ampliamente y soy consciente de que varios problemas NP-hard siguen siendo NP-hard incluso restringidos a subclases de gráficos cúbicos, pero otros se vuelven más fáciles. Una superclase de gráficos cúbicos es la clase de gráficos con un grado máximo . $\Delta \leq 3$

¿Hay algún problema que pueda resolverse en tiempo polinómico para gráficos cúbicos pero eso es NP-difícil para gráficos con un grado máximo ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness Vinicius dos Santos
fuente

Respuesta degenerada que muestra que puede haber diferentes complejidades (aunque ninguna es NP-Hard): Encontrar

es tiempo constante en gráficos cúbicos pero lineal en gráficos con

. :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

William Macrae

Buen punto. :-)

Vinicius dos Santos

Para malas elecciones de codificaciones, incluso puede ser

-duro cuando

, pero será mucho más valioso encontrar un problema que no dependa de una codificación pobre, y aún mejor si ese problema está bien estudiado uno.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

William Macrae

Para ampliar el comentario de William, aquí hay un problema artificial. Dado un gráfico , ¿la secuencia de grados de , interpretada como la codificación de una instancia de 3-SAT, representa una instancia satisfactoria? $G$ $G$ (Suponiendo que la codificación es tal que la secuencia de 3 grados representa una asignación satisfactoria para cada

.) :-)

n

$n$

Neal Young

Consulte también cstheory.stackexchange.com/questions/1215/… para obtener más inspiración (p. Ej., Problemas que son difíciles para los árboles de grado máximo 3, pero triviales si no hay nodos foliares).

Jukka Suomela

Respuestas:

Aquí hay una razonablemente natural: en una entrada , determine si tiene una subgrafía regular conectada con al menos aristas. Para gráficos de 3 regulares, esto es trivial, pero si el grado máximo es 3 y la entrada está conectada, no es un árbol y no es regular, entonces el subgrafo más grande es el ciclo más largo, por lo que el problema es NP-completo. $(G,k)$ $G$ $k$

David Eppstein
fuente

"... entonces la solución es el ciclo más largo o una coincidencia máxima ...". ¿Cómo depende su reclamo de k? No es cierto para todos los k.

Tyson Williams

@Tyson, solo necesita ser difícil para que una

sea difícil, ¿verdad? Por ejemplo, tome

. David, ¿necesitas estipular que el subgrafo debe estar conectado? (De lo contrario, cualquier cubierta de ciclo (no solo un ciclo de Hamilton) tendrá

aristas, y determinar la existencia de una cubierta de ciclo está en

)

k

$k$

k = n

$k=n$

n

$n$

P

$P$

Neal Young

David, una coincidencia máxima (de tamaño mayor que 1) en G no es un subgrafo conectado de G. ¿Quieres decir "... el ciclo más largo o un solo borde, ..."?

Tyson Williams

Bien bien. Hoy no parece ser un buen día para ser riguroso, probablemente demasiado pavo. Agregué un lenguaje para descartar este caso especial.

David Eppstein el

@YininCao Dado que el gráfico está conectado pero no es regular, no hay forma de elegir un subgrafo de 3 regulares. Supongamos que lo fuera. Luego existe un vértice que no fue seleccionado ya que el gráfico no es regular. Dado que el gráfico está conectado, este vértice está conectado a un vértice 3-regular que fue seleccionado. Pero eso significa que existe un vértice de grado 4, una contradicción.

Tyson Williams