Härte der Annäherung der chromatischen Zahl in Diagrammen mit begrenztem Grad

12

Ich suche nach Härteergebnissen für die Scheitelfärbung von Diagrammen mit begrenztem Grad.

Ausgehend von einem Graphen $G(V,E)$ wissen wir, dass es für $\epsilon>0$ schwierig ist, $\chi(G)$ innerhalb eines Faktors von $|V|^{1-\epsilon}$ sei denn, [ 1 ]. Was aber, wenn der maximale Grad von durch ? Gibt es in diesem Fall Härteverhältnisse der Form (für einige )? $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Eine einfachere Frage ist: Härte der Approximation der kantenchromatischen Anzahl von Hypergraphen, wenn ihre Kantengröße durch . Können wir in diesem Fall auf ein Härteverhältnis von hoffen ? (sagen wir, für jedes ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

Danke für Ihre Aufmerksamkeit!

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

3

Sie können eine harte Instanz mit isolierten Eckpunkten

auffüllen

2

Ja, aber wenn Sie der Größe der Hard-Instanz, von der Sie ausgehen, eine endliche Grenze setzen, wird sie nicht mehr hart.

David Eppstein

1

@Sasho Wie können isolierte Eckpunkte helfen, wenn sie weder die chromatische Zahl noch den Maximalgrad erhöhen?

afshi7n

2

@ DavidEppstein sicher, diese Polsterung beweist nur etwas, wenn

und

immer noch polynomial zusammenhängen. OP, das ist eigentlich genau der Punkt. Sie beginnen mit einer Instanz mit

Eckpunkten (also höchstens

), für die es schwierig ist,

auf

zu approximieren . addiere

isolierte Eckpunkte.

bleibt gleich und max. Grad bleibt

. Dies ist polytime wenn

. also für jede ganze Zahl

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$ Es gibt Fälle mit maximalem Grad

für die es schwierig ist,

innerhalb von

zu approximieren

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Sasho Nikolov

9

In Khots Arbeit "Verbesserte Unangemessenheitsergebnisse für MaxClique, Chromatische Zahl und ungefähre Graphenfärbung", Satz 1.6, heißt es, dass es NP-schwer ist, färbbare Graphen mit Farben für zu färben Graphen mit Grad höchstens , für ausreichend große konstante . Mit anderen Worten, für Graphen des Grades ist es schwierig, $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ -Farbgrafik mitFarben. $2^{\sqrt{\log\log d}}$ $\log d$

Um eine bessere Gradbindung zu erzielen, können Sie wahrscheinlich Ideen aus Trevisans Artikel "Nicht-Approximierbarkeitsergebnisse für Optimierungsprobleme bei Instanzen mit begrenztem Grad" verwenden. Die wichtigste Beobachtung ist, dass der Graph, der durch die FGLSS-Reduktion erzeugt wird, eine Vereinigung von vollständigen zweiteiligen Teilgraphen ist, und man kann jeden von ihnen durch einen zweiteiligen Dispergierer ersetzen, der viel spärlicher ist. Eine ähnliche Idee wird in vielen Ergebnissen verwendet, wie beispielsweise in Chan http://eccc.hpi-web.de/report/2012/110/ , Theorem 1.4 / Appendix D.

Ich denke das sollte dir sowas für -färbbare Graphen des durchbegrenzten Grades, es ist NP-schwer, sie mit-Farben für eine Konstanteeinzufärben. $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

Der Grad, an den Michael in der Arbeit gebunden ist, ähnelt dem von Khot, nämlich dem Exponential des Falles der Solidität. Natürlich verbessert der obige Sparsifizierungsansatz dies auch, wird aber wahrscheinlich keine bessere Konstante für Ihren Zweck geben.

Sangxia
quelle

Vielen Dank für Ihre hilfreiche Antwort, Sangxia. Aus Khots Papier könnten wir also ein Härteverhältnis von

annehmen. Ich denke, mit der Verbesserung Ihres Papiers können wir dieses Härteverhältnis auf

verbessern

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

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

. Ist das korrekt?

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

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

afshi7n

@ afshi7n Die Parameter sind hier etwas knifflig. In Grad ausgedrückt ergibt Khots Arbeit

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

$\log d / 2^{\sqrt{\log \log d}}$ . My paper gives roughly

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

$\log d / (\log\log d)^3$ . We can improve the degree of the graph in the reduction with Trevisan's approach. I believe that gives you

d^{c}

$d^c$ . BTW all these require a sufficiently large constant

d

$d$ .

sangxia

1

Ich verstehe, danke! Ich fragte auch Khot per E - Mail, er verwies mich auf diesem Papier siam.org/proceedings/soda/2011/SODA11_124_guruswamiv.pdf die ich glaube , das gibt

unter der Annahme , 2-1 Vermutung des Khot.

d^{c}

$d^c$

afshi7n

8

Die bekannteste Härte zur Annäherung der chromatischen Zahl von farbigen Graphen mit begrenztem Maximalgrad geht auf Venkatesan Guruswami und Sanjeev Khanna zurück. Zur Härte von 4- farbigen Graphen mit 3-farbigen Graphen : $3$

Es gibt eine Konstante Dgr ;, so dass es bei einem farbigen Graphen mit maximalem Grad Dgr ; schwierig ist, ihn mit nur Farben zu färben . $\Delta$ $3$ $\Delta$ $4$

vb le
quelle

8

In Khots FOCS'01-Papier "Verbesserte Ergebnisse für die Inapproximierbarkeit von MaxClique-, Farbzahl- und ungefähre Grafikfärbung" ist ein Ergebnis für die Unangemessenheit der Färbung von Diagrammen mit begrenzten Graden zu finden - wahrscheinlich schwächer als gewünscht, aber zumindest in die richtige Richtung.

$k$ $k$ $2^{k^{O(\log k)}}$ , it is NP-hard to find colorings that use $\exp((\log k)^2/25)$ colors. So in terms of the degree $d$ , it is hard to color within an $O(\log d)$ factor, but the same inapproximability ratio is also a superpolynomial function of the chromatic number.

David Eppstein
quelle

David, thanks for your reply. Yes I had seen their result, but I'm hoping to get a hardness ratio better than

\log d

$\log d$ . I think this might be easier to achieve in the second problem, i.e. approximating the edge chromatic number of hypergraphs..

afshi7n

Why not ask Khot?

Chandra Chekuri

1

@chandra Just sent an email and asked him, thanks for the suggestion! I will update here if I heard back.

afshi7n

Actually, the cited paper by Khot proves a gap between k-colorable and

k^{\log k / 25}

$k^{\log k/25}$ -colorable graph (not

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

$\exp((k\log k)/25)$ . This has recently been improved by Huang to

2^{k^{1 / 3}}

$2^{k^{1/3}}$ in a paper that will appear in the next STOC. (arxiv.org/abs/1301.5216)

Michael Lampis

Why do you think that

k^{(\log k) / 25}

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

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

$\exp((k\log k)/25)$ represent different quantities? Or am I misinterpreting the ambiguous operator precedence of Khot's formula?

David Eppstein

4

This result might be helpful:

Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree $\Delta$ has a coloring using $k=$ $\Delta - \sqrt\Delta +1$ colors is NP-complete ( $k\ge 3$ )

T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput. 7 (4) (1998) 375–386

Mohammad Al-Turkistany
quelle

Härte der Annäherung der chromatischen Zahl in Diagrammen mit begrenztem Grad

Antworten: