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 ϵ > 0 , é difícil aproximar χ ( G ) dentro de um fator de | V | 1 - ϵ a menos que NP = ZPP [ 1 ]. Mas e se o grau máximo de G for delimitado por d ? Existem razões de dureza na forma d 1 - ϵ (para alguns ϵ ) neste caso?G(V,E)ϵ>0χ(G)|V|1ϵNP=ZPPGdd1ϵϵ

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 d 1 - ϵ neste caso? (digamos, para qualquer ϵ > 0 )dd1ϵϵ>0

Agradecimentos para sua atenção!

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 d ainda estiverem relacionados polinomialmente. OP, esse é realmente o ponto. você começa com uma instância com vértices d (portanto, grau máximo no máximo d ) para o qual é difícil aproximar χ de dentro de d 1 - ϵ . adicione n - d vértices isolados. χ permanece o mesmo e o grau máximo permanece d . isto é polytime se N = d O ( 1 ) . assim, para qualquer número inteiro kndddχd1ϵndχdN=dO(1)k, Existem casos com o grau máximo para o qual é difícil aproximar χ para dentro d 1 - εd=n1/kχd1ϵ
Sasho Nikolov
Atualização: É NP-difícil aproximar dentro de um fator de | V | 1 - ϵ sem nenhuma premissa extra. χ(G)|V|1ϵ
Cyriac Antony

Respostas:

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 2 Ω ( ( log K ) 2 ) de cores para gráficos com grau no máximo 2 2 ( log K ) 2 , para K constante suficientemente grande . Em outras palavras, para gráficos de grau d , é difícil colorir 2 K2Ω((logK)2)22(logK)2Kd - gráfico colorido comcores delogd.2loglogdlogd

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 pord, é NP difícil colori-lo comdccores para alguma constante0<c<1.2clogdddc0<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 2 Ω ( 2Ω(loglogd). Isso está correto? 22Ω(loglogd)
afshi7n
@ afshi7n Os parâmetros são um pouco complicados aqui. Declarado em termos de grau, o artigo de Khot fornece . Meu trabalho fornece aproximadamentelogd/(loglogd)3. Podemos melhorar o grau do gráfico na redução com a abordagem de Trevisan. Eu acredito que isso lhe dádc. Aliás, tudo isso exige uma constante suficientemente granded. logd/2loglogdlogd/(loglogd)3dcd
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. dc
afshi7n
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.

kk2kO(logk)exp((logk)2/25)dO(logd)

David Eppstein
fonte
logd
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
klogk/25exp((klogk)/25)2k1/3
k(logk)/25exp((klogk)/25)
4

Este resultado pode ser útil:

Δk=ΔΔ+1k3

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