CLIQUE natural a la reducción de k-Color

Claramente, hay una reducción de CLIQUE a k-Color porque ambos son NP-Complete. De hecho, puedo construir uno componiendo una reducción de CLIQUE a 3-SAT con una reducción de 3-SAT a k-Color. Lo que me pregunto es si existe una reducción directa razonable entre estos problemas. Digamos, una reducción que podría explicar a un amigo bastante brevemente sin necesidad de describir un idioma intermedio como el SAT.

Como ejemplo de lo que estoy buscando, aquí hay una reducción directa en la dirección inversa: dado G con y algo de (el número de colores), haga un gráfico G 'con vértices (uno por color por vértice). Los vértices , correspondientes a los vértices y los colores respectivamente son adyacentes si y solo si y ( o ). Una -clique en tiene solo un vértice por vértice en , y los colores correspondientes son un -coloring adecuado de $n$ $k$ $kn$ $v'$ $u'$ $v, u$ $c, d$ $v \neq u$ $c \neq d$ $vu \not \in G$ $n$ $G'$ $G$ $k$ $G$ . De manera similar, cualquier color apropiado de tiene una camarilla correspondiente en . $k$ $G$ $G'$

Editar : para agregar una breve motivación, los 21 problemas originales de Karp se prueban NP-Completo por un árbol de reducciones donde CLIQUE y Chromatic Number forman las raíces de los principales subárboles. Hay algunas reducciones naturales entre los problemas en el subárbol CLIQUE y el subárbol Número cromático, pero muchos de ellos son tan difíciles de encontrar como el que estoy preguntando. Estoy tratando de profundizar en si la estructura de este árbol muestra alguna estructura subyacente en los otros problemas o si es completamente una consecuencia de las reducciones que se encontraron primero, ya que hay menos motivación para buscar reducciones entre dos problemas cuando se sabe que están en la misma clase de complejidad. Ciertamente, el orden tuvo cierta influencia, y partes del árbol se pueden reorganizar, pero ¿se puede reorganizar arbitrariamente?

Edición 2 : Continúo buscando una reducción directa, pero aquí hay un bosquejo de lo más cercano que he llegado (debería ser una reducción válida, pero tiene CIRCUIT SAT como un intermediario claro; es algo subjetivo si esto es mejor que componer dos reducciones como se menciona en el primer párrafo).

Dado , sabemos que puede ser -colorido con vértices todos coloreados Verdadero si tiene una -clique. los vértices originales de y luego agregamos a vértices adicionales: con , . La clave invariante será que puede ser coloreado Verdadero si y solo si entre vértices hay al menos vértices coloreados Verdadero. Entonces, cada puede ser Verdadero. Luego, $G, k$ $\overline{G}$ $n-k+1$ $k$ $G$ $k$ $G$ $v_1, \ldots, v_n$ $\overline G$ $C_{ij}$ $1 \le i \le n$ $0 \le j \le k$ $C_{ij}$ $\{v_1,\ldots, v_i\}$ $j$ $C_{i0}$ $C_{ij}$ para obtiene el color donde todos los colores no verdaderos se tratan como falsos. Hay una -clique en si puede ser coloreado Verdadero, así que si forzamos esa coloración, la nueva gráfica es coloreable si hubiera una clique en la gráfica original. $j > 0$ $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ $k$ $G$ $C_{nk}$ $k$

Los gadgets AND y OR para imponer las relaciones son muy parecidos a la reducción de CIRCUIT SAT a 3-COLOR, pero aquí incluimos una en nuestro gráfico, seleccionamos los vértices T, F y Ground, y luego conecta a todos los demás a todo menos a los s; esto asegura que los sy los otros gadgets reciban solo 3 colores. $K_{n-k+1}$ $v_i$ $C_{ij}$

De todos modos, la parte de esta reducción se siente directa, pero el uso de compuertas AND / OR es mucho menos directo. La pregunta sigue siendo, ¿hay una reducción más elegante? $\overline G$

Edición 3 : Ha habido algunos comentarios sobre por qué esta reducción sería difícil de encontrar. CLIQUE y k-Color son realmente problemas muy diferentes. Sin embargo, incluso sin una reducción, una respuesta que detalle por qué la reducción es difícil en una dirección pero posible en la otra sería muy útil y contribuiría mucho al problema.

cc.complexity-theory graph-theory np-hardness reductions William Macrae
fuente

El tipo de reducción directa que está buscando puede ser difícil de encontrar ya que Clique y colouring son algo opuestos en el sentido de que un clique 1 es tan fácil de encontrar como un n-colouring. Entonces, tal vez la reducción debería ser de la forma: tiene un color si y solo si tiene una -clique

G^{'}

$G'$

n - k

$n-k$

G

$G$

k

$k$

Martin Vatshelle

Estoy de acuerdo en que es difícil; esta es la razón de mi interés; Daré detalles sobre la motivación en la pregunta. La idea coloring me ha acercado más. Si hay una -clique en entonces puede tener todos los vértices en la camarilla monocromática porque son un conjunto independiente. El problema es que el número cromático del resto puede variar. Al vincular dos vértices a un se les obliga a tener el mismo color, pero no tengo idea de qué conjunto de vértices se deben forzar. Un aparato que obliga a algunos fuera de vértices sea monocromática lo haría.

n - k

$n-k$

k

$k$

G

$G$

\bar{G}

$\overline{G}$

K_{n - k - 1}

$K_{n-k-1}$

i

$i$

j

$j$

William Macrae

Estoy de acuerdo con Martin aquí en que esto podría no ser factible (sin pasar, digamos 3SAT). La camarilla y la coloración tienen muy poco en común. Por lo tanto, quiero recordar el teorema de Erdős, dados los naturales g y k, hay un gráfico con circunferencia al menos gy número cromático al menos k (piense en eso por un tiempo si no está familiarizado con él). Finalmente, su reducción también debe ser consciente de que mientras Clique (y conjunto independiente) está en parametrizado por el conjunto de solución, no hay una parametrización equivalente para el número cromático de un gráfico.

W [1]

$W[1]$

Pål GD

No entiendo el comentario de @ MartinVatshelle. Hasta donde sé, todos los modelos 1-clique, 1-coloring, n-clique y n-coloring son triviales en el mismo nivel. (no piense que siempre puede responder a la 1-camarilla SÍ: ¡el gráfico de entrada podría estar vacío!)

Yixin Cao

Creo que el punto de Martin es que es show y , pero es más difícil encontrar un que un . Entonces hay un poco de dualidad en los dos conceptos. El punto de @PålGD sobre el teorema de Erdős es excelente (y me encanta ese teorema), ya que los gráficos con gran circunferencia tienen un gran número de independencia, por lo que sus inversas tendrán grandes camarillas. En general, se siente como que hay una trampa aquí, sin embargo, que es relacionar Cliques y colorantes en las mismas o similares gráficos, pero como con la dirección inversa a la reducción podría construir un gráfico muy diferente de .

χ (G) = 4

$\chi(G)=4$

χ (G) = 3

$\chi(G)=3$

K_{4}

$K_4$

K_{3}

$K_3$

G

$G$

William Macrae

Respuestas:

Dado un grafo y un número , de tal manera que usted quiere saber si contiene un -clique, Sea n el número de vértices en . Construimos otro gráfico , de modo que sea -colorable si y solo si tiene una -clique, de la siguiente manera: $G$ $k$ $G$ $k$ $G$ $H$ $H$ $n$ $G$ $k$

(1) Para cada vértice en , haga una camarilla de vértices en , donde varía de a . $v$ $G$ $n$ $(v,i)$ $H$ $i$ $1$ $n$

(2) Añadir un vértice adicionales a . $x$ $H$

(3) Para cada triple de vértices en , donde y , compruebe si una de las siguientes condiciones cumple: u e , y son vértices no adyacentes en con . Si cualquiera de estas dos cosas es cierta, añadir otro -clique a . Dentro de esta camarilla, seleccione tres vértices , y . Conecte a cada vértice de la camarilla, excepto para y $\{x,y,z\}$ $H$ $y=(v,i)$ $z=(u,j)$ $u\ne v$ $i=j$ $u$ $v$ $G$ $\max(i,j)\le k$ $n$ $H$ $x'$ $y'$ $z'$ $x$ $y'$ $z'$ ; conecta a cada vértice de la camarilla, excepto y ; y conecte a cada vértice de la camarilla, excepto e . $y$ $x'$ $z'$ $z$ $x'$ $y'$

Los aparatos añadido en la etapa (3) impedir la triple de vértices , , y de todos los que se da el mismo color que el uno al otro en una coloración válida de . La camarilla en se puede recuperar de una coloración de como el conjunto de vértices que están en la misma clase de color que y que tienen . $x$ $y$ $z$ $H$ $G$ $H$ $(v,i)$ $x$ $i\le k$

David Eppstein
fuente

Esto es maravilloso.

William Macrae

Por alguna razón, mi edición fue rechazada, pero la última oración debería describir los vértices de G en lugar de H (ya que está destinado a describir una camarilla en G). Algo así como "La camarilla en puede recuperarse de una coloración de H como " Además, olvidé di gracias por la respuesta, ha sido muy útil!

G

$G$

{v : \exists i \leq k χ ((v, i)) = χ (x)} .

$\{v : \exists i \le k \chi((v,i)) = \chi(x) \}.$

William Macrae

Claro, podrías poner otra cláusula a esa oración sobre quitar la de cada par, pero pensé que ese paso era bastante fácil de omitir, y mi sensación general es que (cuando puede ser lo suficientemente corto) la prosa tiende a ser más legible que una fórmula.

i

$i$

David Eppstein el

Estoy de acuerdo en que la prosa es más preferible. Tal vez solo agregar una frase como "la primera coordenada de cada (v, i) ..." es una idea. La razón de mi preocupación por el tecnicismo es que cuando se leen las reducciones en la primera lectura, puede ser difícil mantener claras las definiciones exactas de los elementos en el primer idioma y el segundo, y cuál es cuál. En el momento en que algo parece romper una definición, me puede dar un vuelco. Si tuviera problemas para comprender oraciones anteriores y llegué a la última, determinaría que G y H tienen vértices de la forma (v, i).

William Macrae

También debería decir que creo que has hecho un trabajo mucho mejor hablando de esta reducción que casi cualquier otro que haya leído. Hay un problema en la literatura de que muchas reducciones se establecen formalmente sin motivación o intuición, y lo has evitado muy bien.

William Macrae

-7

?? Se sabe que la coloración y el hallazgo de camarillas están estrechamente vinculados durante décadas a través de la teoría de gráficos (¿posiblemente incluso en los años 60?) Incluso no a través del SAT como intermediario (que se convirtió en típico después de la prueba de Cook en 1971). cree que hay algoritmos basados en la siguiente propiedad básica :

Si G contiene una camarilla de tamaño k, entonces se necesitan al menos k colores para colorear esa camarilla; en otras palabras, el número cromático es al menos el número de camarilla: $\chi(G) \ge \omega(G).\,$

no estoy seguro de referencias exactas pero [1,2] son buenos lugares para comenzar, un algoritmo exacto o referencia es al menos probablemente citado en estos libros.

[1] Camarillas, coloración y satisfacción, segundo desafío DIMACS

[2] Dimacs vol 26: camarillas, coloración y satisfacción

vzn
fuente

Usando la propiedad , puede invocar un algoritmo para en : si el algoritmo devuelve , entonces no contiene ninguna camarilla de tamaño al menos . Sin embargo, la implicación opuesta no se cumple: si el algoritmo devuelve , entonces puede o no tener una camarilla de tamaño al menos (como contraejemplo, considere una pirámide cuya base poligonal tiene un número impar de vértices: es no -colorable, sin embargo no tiene ninguna clique de tamaño al menos ).

χ (G) \geq ω (G)

$\chi(G) \geq \omega(G)$

k - C O L O R A B I L I T Y

$k-COLORABILITY$

G

$G$

Y E S

$YES$

G

$G$

k + 1

$k+1$

N O

$NO$

G

$G$

k + 1

$k+1$

3

$3$

4

$4$

Giorgio Camerani

sí, estoy de acuerdo; Tal como lo interpreto, la publicación original no insistía en la dirección de la reducción, pero enfatizaba más evitar el SAT como intermediario y pedía una "explicación bastante breve". También visiblemente nadie mencionó el hecho real por encima de lo que va .... la pregunta y los comentarios también parecen indicar erróneamente en diversas formas los dos problemas no están estrechamente unidas ....

VZN

Disculpas si la dirección era ambigua. Estoy interesado en una reducción correcta (YES YES), y estoy interesado en una reducción de Clique a k-Color. Tengo la otra dirección y se explica en mi publicación. Ciertamente, hay muchas cosas que relacionan las camarillas en los gráficos con los colores en los gráficos y viceversa, y de hecho he visto muchas de ellas (y supongo que muchas otras aquí han visto muchas de ellas), pero estoy realmente interesado exclusivamente en un directo reducción o una explicación convincente de por qué podría no existir.

⟺

$\iff$

William Macrae

@vzn: Mi comentario no pretendía criticar tu respuesta. A decir verdad, inicialmente hice un razonamiento similar al suyo, pero luego me di cuenta de que, si la implicación opuesta se hubiera mantenido, entonces en gráficos generales, que se sabe que es NP-completo, habría sido solucionado trivialmente por solo verificando si el gráfico de entrada tenía una camarilla de nodos: cualquier habría sido -colorable si y solo si no contiene ninguna camarilla de tamaño (eso es completamente falso, por supuesto, como muestra el contraejemplo de la pirámide). Por cierto: no soy yo quien votó en contra.

3 - C O L O R I N G

$3-COLORING$

4

$4$

G

$G$

3

$3$

4

$4$

Giorgio Camerani

@WilliamMacrae: ¡Estaba perfectamente claro que querías una reducción de , de lo contrario no habría sido una reducción! Además, era perfectamente claro que quería una reducción de la a y no a la inversa.

⟺

$\Longleftrightarrow$

C L I Q U E

$CLIQUE$

C O L O R I N G

$COLORING$

Giorgio Camerani