Problemas NP-duros en los coógrafos

12

Esta pregunta es similar a los problemas NP-hard en los árboles :

Hay una gran cantidad de problemas NP-completos que son manejables en los coógrafos . ¿Hay algún problema conocido que permanezca NP-completo cuando se restrinja a los coógrafos?

Para ser más precisos, estoy interesado en ejemplos en los que la entrada consiste únicamente en un cograma no dirigido y no ponderado .

Dos observaciones:

Para los cográficos ponderados se menciona este problema aquí : TSP con dos viajeros
Los cográficos son la "clase base" del ancho de la camarilla, como los árboles son la clase base del ancho del árbol.

ACTUALIZAR

Algunas reflexiones adicionales (no estoy muy seguro): si la entrada es realmente solo un cograph, la pregunta tiene que ser del tipo "¿Tiene el cograph la propiedad X?". Sería suficiente si existiera un problema de este tipo para los árboles, ya que la pregunta podría ser "¿El árbol del cograph tiene la propiedad X?".

cc.complexity-theory np-hardness graph-algorithms Martin Lackner
fuente

Entonces, evitando que sea una pregunta (no tan) duplicada, ¿tal vez también requerimos que estos problemas de NP completo sean polinómicos para que se puedan resolver en los árboles?

Hsien-Chih Chang 張顯之

Sería bueno por supuesto. Sin embargo, estaría contento incluso si este no fuera el caso. Especialmente porque todos los ejemplos dados en el hilo original no responden mi pregunta (a mi entender).

Martin Lackner

11

Quizás mi problema abierto favorito es de interés: el problema de la cubierta de camarilla de borde en los coógrafos. En el problema de cubierta de camarilla de borde, desea cubrir los bordes de la cografía con un número mínimo de camarillas. Se desconoce si este problema es NP-completo.

Para ilustrar que el problema es probablemente difícil, dejemos que sea el gráfico multipartito completo con conjuntos conjuntos de tamaño . Esto es un cograph. Existen cuadrados latinos ortogonales por pares de orden si y solo si la cubierta de camarilla de borde de es . Esto fue demostrado por Park, Kim y Sano . Esta es una fórmula para el "gráfico de cóctel", es decir, el caso donde . $K_n^m$ $m$ $n$ $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Ton Kloks
fuente

10

Varios problemas siguen siendo NP completos cuando se restringen a los coógrafos. La coloración de la lista, el número acromático y el isomorfismo inducido del subgrafo siguen siendo NP completos.

[1] Hans L. Bodlaender. El número acromático es NP-completo para cografías y gráficas de intervalos. Inf. Proceso. Lett., 31 (3): 135–138, 1989

[2] Klaus Jansen y Petra Scheffler. Coloración generalizada para gráficos en forma de árbol. Aplicación discreta Math., 75 (2): 135–155, 1997

[3] Peter Damaschke. El isomorfismo inducido del subgrafo para los cografos es NP-completo. Lecture Notes in Computer Science, 1991, Volumen 484/1991, 72-78,

Mohammad Al-Turkistany
fuente

1

Muchas gracias por tu respuesta. Estos son problemas realmente interesantes, pero creo que no cumplen con el requisito de que la entrada sea solo un gráfico: la entrada en [1] es un gráfico y un entero, [2] un gráfico y un conjunto de colores para cada vértice, [ 3] dos gráficos.

Martin Lackner

3

Aquí hay variaciones triviales de dos de los mismos problemas que siguen siendo NP completos pero solo tienen un cograma como entrada: ¿el cograma dado consta de dos componentes conectados, uno de los cuales es un subgrafo inducido del otro? ¿El cograma dado tiene un color completo que le da a cada uno de sus vértices aislados un color distinto?

David Eppstein

10

Aquí hay un problema de NP completo para dos cografías dadas en lugar de uno que está muy cerrado a la pregunta formulada. El artículo publicado recientemente muestra que decidir, para los cográficos dados y , si es una retracción de , es NP-completo. ( es una retracción de si existen mapas de preservación de bordes y modo que es la identidad.) $G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

vb le
fuente

2

Nuevamente, esto se puede reinterpretar como un problema en un solo cograph (que tiene dos componentes conectados).

David Eppstein

1

Veo. Por supuesto, uno puede solicitar problemas de NP completo cuando la entrada consiste únicamente en un cograma conectado , no dirigido y no ponderado. Creo que la pregunta es bastante interesante.

vb le

1

Pero los coógrafos conectados son solo el complemento de los cogramas desconectados, por lo que requerir conectividad hace muy poca diferencia en las formulaciones de estos problemas. Por ejemplo, aquí hay una versión para los cogramas conectados: para un cograma conectado cuyo complemento tiene dos componentes, que y sean los subgramas inducidos en por los vértices de estos componentes, ordenados de modo que. ¿Es un retracto de ?

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

David Eppstein

Ah, eso está bien!

vb le

Problemas NP-duros en los coógrafos

Respuestas: