dureté d'approximation du nombre chromatique dans les graphiques avec degré borné

12

Je recherche des résultats de dureté sur la coloration des sommets des graphiques à degré borné.

Étant donné un graphique , nous savons que pour tout , il est difficile d'approximer dans un facteur de sauf si [ 1 ]. Mais que se passe-t-il si le degré maximal de est limité par ? Y a-t-il des rapports de dureté de la forme (pour certains ) dans ce cas? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Une question plus simple est: la dureté d'approximation du nombre chromatique d'arêtes des hypergraphes lorsque leur taille d'arête est limitée par . Peut-on espérer un rapport de dureté dans ce cas? (disons, pour tout ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

Merci de votre attention!

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

3

vous pouvez remplir une instance dure avec des sommets isolés

Sasho Nikolov

2

Oui, mais si vous définissez une limite finie sur la taille de l'instance dure à partir de laquelle cela commence, cela cesse d'être difficile.

David Eppstein

1

@Sasho Comment les sommets isolés peuvent-ils aider lorsqu'ils n'augmentent ni le nombre chromatique ni le degré maximum?

afshi7n

2

@DavidEppstein bien sûr, ce remplissage ne prouve quelque chose que si

et

sont toujours liés polynomialement. OP, c'est en fait précisément le point. vous commencez avec une instance avec

sommets (donc degré maximum au plus

) pour laquelle il est difficile d'approximer

à

. ajouter

sommets isolés.

reste le même et le degré maximum reste

. il s'agit de polytemps si

. donc pour tout entier

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$ , il existe des instances avec un degré max

pour lesquelles il est difficile d'approximer

à

près

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Sasho Nikolov

Mise à jour: Il est difficile de NP d'approcher

dans un facteur de

sans hypothèses supplémentaires.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

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

Cyriac Antony

9

Comme l'a souligné David, l'article de Khot, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Colouring", Theorem 1.6, dit qu'il est NP-difficile de colorer le graphique colorable avec couleurs pour graphiques avec degré au plus , pour une constante suffisamment grande . En d'autres termes, pour les graphiques de degré , il est difficile de colorer $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ - graphique colorable aveccouleurs. $2^{\sqrt{\log\log d}}$ $\log d$

Pour obtenir un meilleur degré lié, vous pouvez probablement utiliser les idées de l'article de Trevisan "Résultats de non-approximabilité pour les problèmes d'optimisation sur les instances de degré borné". L'observation clé est que le graphique produit par la réduction FGLSS est une union de sous-graphes bipartites complets, et on peut remplacer chacun d'eux par un disperseur bipartite qui est beaucoup plus clairsemé. Idée similaire utilisée dans de nombreux résultats tels que Chan http://eccc.hpi-web.de/report/2012/110/ , Theorem 1.4 / Annexe D.

Je pense que cela devrait vous donner quelque chose comme pour - graphiques colorables de degré délimités par, il est difficile de le colorier aveccouleurs pour une constante. $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

Le degré lié dans l'article mentionné par Michael est similaire à celui de Khot, à savoir l'exponentielle du cas de solidité. Bien sûr, l'approche de sparsification ci-dessus améliore également cela, mais ne donnera probablement pas de meilleure constante pour votre objectif.

sangxia
la source

Merci pour votre réponse utile, Sangxia. Ainsi, d'après l'article de Khot, nous pourrions impliquer un rapport de dureté de

. Je pense qu'en utilisant l'amélioration de votre papier, nous pouvons améliorer ce rapport de dureté à

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

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

. Est-ce exact?

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

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

afshi7n

@ afshi7n Les paramètres sont un peu délicats ici. En termes de degré, l'article de Khot donne

. Mon article donne approximativement

. Nous pouvons améliorer le degré du graphique dans la réduction avec l'approche de Trevisan. Je crois que cela vous donne

. BTW tout cela nécessite une constante suffisamment 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

d^{c}

$d^c$

8

$3$

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

vb le
la source

8

Il existe un résultat d'inapproximabilité pour la coloration des graphiques à degrés bornés dans l'article FOCS'01 de Khot, "Amélioration des résultats d'inapproximabilité pour MaxClique, le nombre chromatique et la coloration approximative du graphique" - c'est probablement plus faible que vous le souhaitez, mais au moins c'est dans la bonne direction.

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

David Eppstein
la source

\log d

$\log d$

Pourquoi ne pas demander à Khot?

Chandra Chekuri

1

@chandra Je viens d'envoyer un e-mail et lui ai demandé, merci pour la suggestion! Je mettrai à jour ici si j'ai entendu.

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

Ce résultat pourrait être utile:

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

T. Emden-Weinert, S. Hougardy, B. Kreuter, Graphiques à colorier unique et la dureté des graphiques à colorier de grande circonférence, Combin. Probab. Comput. 7 (4) (1998) 375–386

Mohammad Al-Turkistany
la source

dureté d'approximation du nombre chromatique dans les graphiques avec degré borné

Réponses: