Finalización mínima del gráfico de ciclo impar sin acordes: ¿es NP-hard?

El siguiente problema interesante surgió en mi investigación recientemente:

INSTANCIA: Gráfico . $G(V, E)$

SOLUCIÓN: Una finalización de ciclo impar sin acordes, definida como un superconjunto del conjunto de bordes modo que el gráfico completado tiene la propiedad de que cada borde en está contenido en un ciclo impar sin acordes. $E'$ $E$ $G'(V, E')$ $G'$

MEDIDA: El tamaño de la finalización, es decir, . $|E' - E|$

Hasta ahora, pudimos demostrar que una versión modificada de este problema es NP-complete, donde en lugar de requerir que "cada borde en esté contenido en un ciclo impar sin acordes", requerimos la propiedad más fuerte de que "cada borde está contenido en un triángulo (ciclo de longitud 3) ". (Tenga en cuenta que esto no es equivalente con el problema MINIMO CHORDAL GRAPH COMPLETION ). $G'$

Se ve fácilmente que lo primero es una generalización de lo segundo, pero hasta aquí todos mis esfuerzos por demostrarlo fracasaron. ¿Alguien podría tener un puntero / referencia / etc.?

cc.complexity-theory reference-request graph-theory np-hardness Gabor Retvari
fuente

El problema parece estar muy relacionado con los gráficos perfectos que son perfectos si hay un agujero impar (anti) (ciclo impar sin acordes de al menos 5) [más en wikipedia]. por lo tanto, sugiera que quizás intente reformular la pregunta en términos de una pregunta sobre gráficos perfectos.

vzn

@vzn: No estoy seguro de que este fuerte teorema pueda ser de alguna ayuda aquí.

domotorp

¿Podemos decidir en P si cada borde de G está contenido en un ciclo extraño sin acordes? Supongo que esto es posible, pero no veo cómo.

domotorp

Bueno, tenemos dos problemas ahora. Fácilmente, tendríamos una decisión en P si pudiéramos decidir para cada borde si está en un ciclo impar sin acordes. Encontré una referencia , afirmando que las preguntas "¿Un gráfico contiene un ciclo impar inducido de longitud mayor que tres, que pasa por un vértice prescrito?" y "¿Un gráfico contiene un camino impar inducido entre dos vértices prescritos?" son NP completos, pero estos no resuelven nuestro caso completamente. Puede resultar que el problema original no está en NP, pero aún puede ser NP-hard.

Gabor Retvari

¿puede indicar a qué sección de su documento define el problema anterior y a qué se refiere la especificación? a ("versión modificada probada NP completa")

vzn

Respuestas:

Demostramos que el problema es NP-difícil incluso en su forma de decisión, es decir, "¿El gráfico de entrada ya es una finalización de ciclo impar sin acordes?" Por reducción del siguiente problema: $G$

Problema P : Dado un gráfico y una arista , ¿hay un ciclo impar sin cuerda de longitud mayor que 3 que pasa por ? $G$ $e\in E(G)$ $e$

Este problema es conocido por ser NP-duro por reducción a partir de '' la detección de ciclos incluso chordless pasan a través de un nodo dado '' en la referencia dada en una de sus comentarios que aparece en el párrafo antes de la sección 3 por dejar que y : $p=0$ $q=2$

$q>1$ $p\ge 0$ $G$ $u$ $p$ $q$

(Puede haber una reducción de Karp, pero si permitimos una reducción de Cook, considere la siguiente reducción: Reemplazar el nodo de grado d dado en una subgrafía completa de tamaño d con bordes salientes adecuados. Luego, para cada borde en el gráfico completo podemos consultar el oráculo que resuelve el problema P. Tenga en cuenta que un ciclo par sin acordes que pasa a través del nodo dado corresponde a un ciclo impar sin acordes de longitud mayor que 3 que pasa a través de uno de los bordes en el gráfico completo).

$e$ $e$ $e$ $e$

$f$ $e=(u,v)$ $v_f$ $(v_f,u)$ $(v_f,v)$ $G'$

$G$ $e$ $G'$

$G'$ $e$ $e$ $G′$ $e$ $G$

$e$ $e$ $e$ $G'$ $G'$ $G'$ $G$

Hsien-Chih Chang 張顯之
fuente

Tengo problemas para seguir cualquiera de las reducciones. En la primera reducción, si el nodo dado v tiene un grado, digamos, 5, luego de la reducción se convierte en K_5, y este K_5 contiene un ciclo de longitud impar, pero no corresponde a un ciclo de longitud par que contenga v. la reducción principal, suponga que G = (V, E) donde V = {1,2,3,4,5}, E = {12,23,34,45,15,35}, y e = 34. G tiene un ciclo de longitud 5 que pasa por e, pero en G ', el borde 34 es un puente y no pertenece a ningún ciclo extraño, si entiendo la definición de su reducción correctamente.

Tsuyoshi Ito

e

$e$

e

$e$

e

$e$

G^{'}

$G'$

@ Hsien-ChihChang 張顯之: de todos modos: dado que la recompensa expira pronto y estaré lejos de mi computadora, ahora te recomiendo el precio. Muchas gracias por su respuesta, realmente me ayudó a pensar en el problema de nuevas maneras. Si puede volver más tarde y solucionar los problemas anteriores, estaría muy agradecido.

Gabor Retvari

e

$e$

e

$e$

G^{'}

$G'$

G^{'}

$G'$

e

$e$

e

$e$

G^{'}

$G'$

e

$e$

G

$G$

Hsien-Chih Chang 張顯之