dureza da aproximação do número cromático em gráficos com grau delimitado

12

Estou procurando resultados de dureza na coloração de vértices de gráficos com grau delimitado.

Dado um gráfico , sabemos que para qualquer , é difícil aproximar dentro de um fator de menos que [ 1 ]. Mas e se o grau máximo de for delimitado por ? Existem razões de dureza na forma (para alguns ) neste caso? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Uma pergunta mais fácil é: Dureza de aproximar o número cromático da borda dos hipergrafos quando seu tamanho da borda é delimitado por . Podemos esperar uma taxa de dureza neste caso? (digamos, para qualquer ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

Agradecimentos para sua atenção!

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

3

você pode pad um exemplo duro com vértices isolados

Sasho Nikolov

2

Sim, mas se você colocar um limite finito no tamanho da instância difícil da qual você inicia, ela deixa de ser difícil.

precisa

1

@Sasho Como os vértices isolados podem ajudar quando não aumentam o número cromático nem o grau máximo?

afshi7n

2

@ David David Eppstein claro, esse preenchimento só prova alguma coisa se

e

ainda estiverem relacionados polinomialmente. OP, esse é realmente o ponto. você começa com uma instância com vértices

(portanto, grau máximo no máximo

) para o qual é difícil aproximar

de dentro de

. adicione

vértices isolados.

permanece o mesmo e o grau máximo permanece

. isto é polytime se

. assim, para qualquer número inteiro

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$ , Existem casos com o grau máximo

para o qual é difícil aproximar

para dentro

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Sasho Nikolov

Atualização: É NP-difícil aproximar

dentro de um fator de

sem nenhuma premissa extra.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

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

Cyriac Antony

9

Como David apontou, o artigo de Khot, "Resultados de Inaproximação Aprimorados para MaxClique, Número Cromático e Coloração Aproximada de Gráficos", Teorema 1.6, diz que é NP difícil de pintar um gráfico colorido de com cores para gráficos com grau no máximo , para constante suficientemente grande . Em outras palavras, para gráficos de grau , é difícil colorir $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ - gráfico colorido comcores de. $2^{\sqrt{\log\log d}}$ $\log d$

Para obter um melhor grau de limite, você provavelmente pode usar as idéias do artigo de Trevisan "Resultados de não aproximabilidade para problemas de otimização em instâncias de graus limitados". A observação principal é que o gráfico produzido pela redução do FGLSS é uma união de subgráficos bipartidos completos, e pode-se substituir cada um deles por um dispersor bipartido que é muito mais escasso. Idéia semelhante usada em muitos resultados, como Chan http://eccc.hpi-web.de/report/2012/110/ , Teorema 1.4 / Apêndice D.

Eu acho que isso deve lhe dar algo parecido com - gráficos de grau coloridos delimitados por, é NP difícil colori-lo comcores para alguma constante. $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

O grau no artigo mencionado por Michael é semelhante ao de Khot, a saber, exponencial do caso da solidez. É claro que a abordagem de esparsificação acima também melhora isso, mas provavelmente não dará uma constante melhor para o seu propósito.

sangxia
fonte

Obrigado pela sua resposta útil, Sangxia. Assim, no artigo de Khot, poderíamos implicar uma relação de dureza de

. Acho que usando a melhoria em seu artigo, podemos melhorar essa taxa de dureza para

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

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

. Isso está correto?

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

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

afshi7n

@ afshi7n Os parâmetros são um pouco complicados aqui. Declarado em termos de grau, o artigo de Khot fornece

. Meu trabalho fornece aproximadamente

. Podemos melhorar o grau do gráfico na redução com a abordagem de Trevisan. Eu acredito que isso lhe dá

. Aliás, tudo isso exige uma constante suficientemente grande

.

\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$

Sangxia

1

Entendo obrigado! Também perguntei a Khot por e-mail, ele me encaminhou para este artigo siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf, que acredito dar ao

assumir a conjectura 2-1 de Khot.

d^{c}

$d^c$

afshi7n

8

A dureza mais conhecida de aproximar o número cromático de gráficos de cores com grau máximo limitado é devido a Venkatesan Guruswami e Sanjeev Khanna, Sobre a dureza de 4 cores para colorir um gráfico de 3 cores : $3$

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

vb le
fonte

8

Há um resultado de improbabilidade para colorir gráficos de graus delimitados no artigo FOCS'01 de Khot, "Resultados de Inproximabilidade Aprimorados para MaxClique, Número Cromático e Coloração Aproximada de Gráfico" - provavelmente é mais fraco do que você deseja, mas pelo menos está na direção certa.

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

David Eppstein
fonte

\log d

$\log d$

Por que não perguntar a Khot?

Chandra Chekuri

1

@chandra Acabei de enviar um e-mail e perguntou, obrigado pela sugestão! Vou atualizar aqui se tiver resposta.

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 pode ser útil:

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

T. Emden-Weinert, S. Hougardy, B. Kreuter, Gráficos excepcionalmente coloridos e a dureza de gráficos coloridos de grande perímetro, Combin. Probab. Comput. 7 (4) (1998) 375-386

Mohammad Al-Turkistany
fonte

dureza da aproximação do número cromático em gráficos com grau delimitado

Respostas: