dureza de aproximar el número cromático en gráficos con grado acotado

12

Estoy buscando resultados de dureza en la coloración de vértices de gráficos con grado acotado.

Dado un gráfico , sabemos que para cualquier , es difícil aproximar dentro de un factor de menos que [ 1 ]. Pero, ¿qué pasa si el grado máximo de está limitado por ? ¿Hay alguna relación de dureza de la forma (para algunos ) en este caso? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Una pregunta más fácil es: la dureza de aproximar el número cromático de borde de las hipergrafías cuando su tamaño de borde está limitado por . ¿Podemos esperar una relación de dureza en este caso? (por ejemplo, para cualquier ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

¡Gracias por tu atención!

cc.complexity-theory approximation-hardness graph-colouring hypergraphs bounded-degree afshi7n
fuente

3

puedes rellenar una instancia difícil con vértices aislados

Sasho Nikolov

2

Sí, pero si pone un límite finito en el tamaño de la instancia difícil desde la que comienza, deja de ser difícil.

David Eppstein

1

@Sasho ¿Cómo pueden ayudar los vértices aislados cuando no aumentan el número cromático ni el grado máximo?

afshi7n

2

@DavidEppstein seguro, este relleno sólo demuestra algo si

y

son todavía polinómicamente relacionados. OP, ese es precisamente el punto. comienzas con una instancia con

vértices (por lo tanto, un grado máximo como máximo

) para la cual es difícil aproximar

dentro de

. agregue

vértices aislados.

permanece igual y el grado máximo permanece

. esto es polytime si

. así que para cualquier número entero

n

$n$

d

$d$

d

$d$

d

$d$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

n - d

$n - d$

χ

$\chi$

d

$d$

N = d^{O (1)}

$N = d^{O(1)}$

k

$k$ , existen instancias con un grado máximo

para el cual es difícil aproximar

dentro de

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Sasho Nikolov

Actualización: NP-difícil de aproximar

dentro de un factor de

sin suposiciones adicionales.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

$|V|^{1-\epsilon}$

Cyriac Antony

9

Como señaló David, el artículo de Khot, "Resultados de inaproximabilidad mejorados para MaxClique, número cromático y coloración de gráfico aproximada", Teorema 1.6, dice que es NP-difícil de colorear gráfico colorable con colores para gráficos con grado como máximo , para una constante suficientemente grande . En otras palabras, para gráficos de grado , es difícil colorear $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ : gráfico coloreable concolores. $2^{\sqrt{\log\log d}}$ $\log d$

Para obtener un mejor límite de grado, probablemente pueda usar ideas del documento de Trevisan "Resultados de no aproximabilidad para problemas de optimización en instancias de grado limitado". La observación clave es que el gráfico producido por la reducción FGLSS es una unión de subgrafos bipartitos completos, y uno puede reemplazar cada uno de ellos con un dispersor bipartito que es mucho más escaso. Idea similar utilizada en muchos resultados, como Chan http://eccc.hpi-web.de/report/2012/110/ , Teorema 1.4 / Apéndice D.

Creo que esto debería darte algo así como $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

El grado encuadernado en el artículo que Michael mencionó es similar al de Khot, es decir, exponencial del caso de solidez. Por supuesto, el enfoque de dispersión anterior también mejora esto, pero probablemente no dará mejores constantes para su propósito.

sangxia
fuente

2^{Ω (\log \log d)}

$2^{\Omega(\log \log d)}$

2^{2^{Ω (\sqrt{\log \log d})}}

$2^{2^{\Omega(\sqrt{\log \log d})}}$

\log d / 2^{\sqrt{\log \log d}}

$\log d / 2^{\sqrt{\log \log d}}$

\log d / (\log \log d)^{3}

$\log d / (\log\log d)^3$

d^{c}

$d^c$

d

$d$

1

d^{c}

$d^c$

8

$3$

$\Delta$ $3$ $\Delta$ $4$

vb le
fuente

8

En el documento FOCS'01 de Khot, "Resultados de inaproximidad mejorados para MaxClique, número cromático y coloración aproximada de gráficos", hay un resultado de aproximación para colorear gráficos de grados limitados: probablemente sea más débil de lo que desea, pero al menos está en la dirección correcta.

$k$ $k$ $2^{k^{O(\log k)}}$ $\exp((\log k)^2/25)$ $d$ $O(\log d)$

David Eppstein
fuente

\log d

$\log d$

¿Por qué no le preguntas a Khot?

Chandra Chekuri

1

@chandra Acaba de enviar un correo electrónico y le preguntó, ¡gracias por la sugerencia! Actualizaré aquí si recibí respuesta.

afshi7n

k^{\log k / 25}

$k^{\log k/25}$

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

2^{k^{1 / 3}}

$2^{k^{1/3}}$

k^{(\log k) / 25}

$k^{(\log k)/25}$

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

4

Este resultado puede ser útil:

$\Delta$ $k=$ $\Delta - \sqrt\Delta +1$ $k\ge 3$

T. Emden-Weinert, S. Hougardy, B. Kreuter, Gráficos de colores únicos y la dureza de los gráficos para colorear de gran circunferencia, Combin. Probab Comput 7 (4) (1998) 375–386

Mohammad Al-Turkistany
fuente

dureza de aproximar el número cromático en gráficos con grado acotado

Respuestas: