Complejidad del homomorfismo digrafo a un ciclo orientado

9

Dado un grafo dirigido fijo (dígrafo) , la problema de decisión -Coloreado pregunta si un dígrafo entrada tiene un homomorfismo a . (Un homomorfismo de a es un mapeo de a que conserva los arcos, es decir, si es un arco de , entonces es un arco de )D G D G D f V ( G ) V ( D ) u v G f ( u ) f ( v ) DreresolresolreFV(sol)V(re)tuvsolF(tu)F(v)re

La clase de problemas de COLORING está fuertemente relacionada con la Conjetura de dicotomía para CSP establecida por Feder y Vardi (accesible en citeseer ).re

En este artículo de 2001 (accesible en la página del autor, aquí ), Feder demuestra un teorema de dicotomía cuando es un ciclo orientado (por ciclo orientado me refiero a un ciclo no dirigido donde cada borde se reemplaza por un solo arco, que puede orientarse arbitrariamente) , en otras palabras, muestra que para cualquier ciclo orientado , COLORING es polinomial en tiempo solucionable o NP-completo.reDrere

Desafortunadamente, la clasificación de Feder es altamente no trivial y no explícita, ya que la complejidad de muchos casos está relacionada con la complejidad de ciertas variantes restringidas de SAT que dependen de la orientación. Al mirar el documento, no he podido determinar la respuesta a mi pregunta:

Pregunta: ¿Cuál es el tamaño más pequeño de un ciclo orientado re tal que re COLORACIÓN es NP-completo?

La respuesta podría estar en algún lugar de la literatura, pero no pude encontrarla.


Editar:Permítanme dar más detalles sobre la clasificación de Feder. Feder muestra que cualquier ciclo orientado NP-completo debe estar equilibrado, es decir, tener el mismo número de arcos en ambas direcciones (por lo tanto, tiene un orden uniforme). Luego, considere los "niveles" inducidos por la orientación (comience a dar la vuelta al ciclo en un vértice arbitrario; si un arco va hacia la derecha, sube por 1, si un arco va hacia la izquierda, baja por 1). Entonces, si hay como máximo una "carrera de arriba a abajo", es polinomial. Si hay al menos 3 de esas "ejecuciones" y el ciclo es un núcleo, es NP-complete. (En el ejemplo de András de los comentarios, hay tres "ejecuciones" de este tipo, pero el ciclo no es un núcleo). Los casos más difíciles son aquellos con dos "ejecuciones de arriba a abajo". Algunos son difíciles, otros polinomiales, y Feder los relaciona con problemas especiales de SAT para obtener una dicotomía.

Como una pregunta intermedia: ¿Cuál es el ciclo orientado más pequeño que tiene tres carreras "de arriba a abajo" y es un núcleo? Tal ejemplo sería NP-completo por la discusión anterior.

Florent Foucaud
fuente
No recuerdo una respuesta rápida en la literatura (quizás Barnaby Martin o Florent Madelaine lo sabrían). Sin embargo, el tamaño es como máximo 6 vértices y 6 aristas dirigidas, ya que se puede reducir -Coloring a D -Colouring para un dígrafo de seis vértices D reemplazando cada borde no dirigido en los gráficos por dos arcos que apuntan a un nuevo vértice entre sus puntos finales K3rere
András Salamon
Gracias András Sin embargo, creo que la respuesta debe ser mayor porque el núcleo de este ejemplo es simplemente un dígrafo con un arco único, que puede resolverse en tiempo polinómico ...
Florent Foucaud
Tienes razón, la construcción que propuse es demasiado simple.
András Salamon
Le pregunté a Florent Madelaine y Barnaby Martin, pero no saben la respuesta directamente, aunque parecen estar interesados ​​:-) Mi colega le preguntó a Feder por correo electrónico la semana pasada, pero no respondió (todavía).
Florent Foucaud
Mi segundo impulso fue usar una versión rígida del triángulo. Sin embargo, con el dispositivo de rigidez de Chvátal et al. (JCT 1971) el triángulo rigidizado parece requerir una cantidad de vértices que es al menos 9v + 36, si el gráfico de entrada tiene v vértices, y no está claro cómo modificar estos gadgets en las rutas. Tal vez se podría utilizar una ruta rígida dirigida para reemplazar cada borde, pero no tengo claro cómo hacerlo mientras se conserva la capacidad de asignar cualquier borde del gráfico a cualquier borde del triángulo (pero en ningún otro lugar), ya que Una forma obvia de hacerlo es requerir simetría.
András Salamon

Respuestas:

5

Para la pregunta intermedia (un núcleo con tres carreras de arriba a abajo), ¿qué tal esto?

Alguna notación: describiré corridas por palabras en , con p. Ej. L l r l correspondiente a un subgrafo . El nivel aumenta en arcos r y disminuye en arcos l , y supongo que su mínimo es 0 . Algunas restricciones directas son:{l,r}llrlrl0 0

  • No puede haber una ejecución que consista solo en s o solo en r s, porque de lo contrario existe un homomorfismo obvio de D a esta ejecución (asignando cada nodo de D al que tiene el mismo nivel). Esto también implica que el nivel máximo debe ser al menos 3 .lrrere3
  • Si el nivel máximo fuera , entonces todas las corridas de arriba abajo (resp abajo-arriba) tendrían la forma l l r ( l r ) i l l (resp. R r l ( r l ) i r r ) ; De nuevo, no es muy difícil encontrar un homomorfismo de D a la carrera que minimice i .3llr(lr)yollrrl(rl)yorr)reyo

Sin embargo, para el nivel máximo hay una solución, de longitud 36 : considere D dado por ( r r r l r r l l l r l l ) 3 . Esto tiene las ejecuciones requeridas de arriba a abajo y es un núcleo (ver más abajo). Por las restricciones anteriores, es necesariamente mínimo, ya que cada ejecución solo tiene un único borde "hacia atrás".4 436re(rrrlrrlllrll)3

Para convencernos de que este es un núcleo, primero nombremos los vértices ( ). Los vértices inferiores (es decir, nivel 0 ) son v 1 , v 13 , v 25 . Cualquier homomorfismo φ de D a un subgrafo debe preservar los niveles, y en particular φ ( v 1 ) { v 1 , v 13 , v 25 } ; módulo el automorfismo obvio v ivv1,...,v360v1,v13,v25φDφ(v1){v1,v13,v25} , es suficiente considerar el casoφ( v 1 )= v 1 . Considere la vecindad de v 1 enD(anotada con niveles):vivi+12φ(v1)=v1v1D

v34(1)v35(2)v36(1)v1(0 0)v2(1)v3(2)v4 4(3)v5 5(2)v6 6(3)v7 7(4 4)

Comenzando con , tenemos φ ( v 2 ) { v 36 , v 2 } . Pero si φ ( v 2 ) = v 36 , entonces φ ( v 3 ) = v 35 , y no tenemos un valor posible para φ ( v 4 ) . Obtenemos φ ( v 2 ) = vφ(v1)=v1φ(v2){v36,v2}φ(v2)=v36φ(v3)=v35φ(v4) . Siguiente φ ( v 5 ) { v 3 , v 5 } , pero para φ ( v 5 ) = v 3 obtenemos φ ( v 6 ) = v 4 , sin valor posible para φ ( v 7 )φ(v2)=v2,φ(v3)=v3,φ(v4)=v4φ(v5){v3,v5}φ(v5)=v3φ(v6)=v4φ(v7). Así debe ser la identidad de toda la tirada v 1... v 7 , y repitiendo el mismo argumento para las carreras restantes, lo mismo es cierto en todos D . En particular, φ no asigna D a un subgrafo apropiado.φv1v7DφD

Klaus Draeger
fuente
3
Este mismo análisis muestra que todos los ciclos orientados equilibrados con dos carreras que son núcleos tienen una longitud de al menos 24, ¿verdad? Eso da un límite inferior en la respuesta al problema principal.
David Eppstein
Si, buen punto.
Klaus Draeger
1
Genial, gracias, ¡esto es muy útil! ¿Podemos convencernos a mano de que este es un núcleo? (tenga en cuenta que existe un algoritmo de tiempo polinomial para verificar si un ciclo orientado es un núcleo: cree el conjunto de subrutas orientadas | V ( D ) | { D - a tal que a sea ​​un arco de D } , y luego verifique si D se asigna a cualquiera de estos caminos; esto se puede hacer en polytime, vea Gutjahr et al: sciencedirect.com/science/article/pii/0166218X9290294K )D|V(D)|{DaaD}D
Florent Foucaud
1
@FlorentFoucaud He agregado un poco que muestra que es un núcleo. D
Klaus Draeger