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 ϵ>0 schwierig ist, χ(G) innerhalb eines Faktors von |V|1ϵ sei denn, [ 1 ]. Was aber, wenn der maximale Grad von G durch d begrenzt ist ? Gibt es in diesem Fall Härteverhältnisse der Form d 1 - ϵ (für einige ϵ )?NP=ZPPGdd1-ϵϵ

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 d 1 - ϵ hoffen ? (sagen wir, für jedes ε > 0 )dd1-ϵϵ>0

Danke für Ihre Aufmerksamkeit!

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 d immer noch polynomial zusammenhängen. OP, das ist eigentlich genau der Punkt. Sie beginnen mit einer Instanz mit d Eckpunkten (also höchstens d ), für die es schwierig ist, χ auf d 1 - ϵ zu approximieren . addiere n - d isolierte Eckpunkte. χ bleibt gleich und max. Grad bleibt d . Dies ist polytime wenn N = d O ( 1 ) . also für jede ganze Zahl kndddχd1ϵndχdN=dO(1)kEs gibt Fälle mit maximalem Grad für die es schwierig ist, χ innerhalb von d 1 zu approximieren - ϵd=n1/kχd1ϵ
Sasho Nikolov

Antworten:

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 2 Ω ( ( log K ) 2 ) Farben für zu färben Graphen mit Grad höchstens 2 2 ( log K ) 2 , für ausreichend große konstante K . Mit anderen Worten, für Graphen des Grades d ist es schwierig, 2 √ einzufärbenK2Ω((logK)2)22(logK)2Kd -Farbgrafik mitlogdFarben.2loglogdlogd

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 durchdbegrenzten Grades, es ist NP-schwer, sie mitdc-Farben für eine Konstante0<c<1einzufärben.2clogdddc0<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 2 2 Ω ( verbessern2Ω(loglogd). Ist das korrekt? 22Ω(loglogd)
afshi7n
@ afshi7n Die Parameter sind hier etwas knifflig. In Grad ausgedrückt ergibt Khots Arbeit logd/2loglogd. My paper gives roughly logd/(loglogd)3. We can improve the degree of the graph in the reduction with Trevisan's approach. I believe that gives you dc. BTW all these require a sufficiently large constant 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. dc
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 3- farbigen Graphen mit maximalem Grad & Dgr ; schwierig ist, ihn mit nur 4 Farben zu färben .Δ3Δ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.

kk2kO(logk), it is NP-hard to find colorings that use exp((logk)2/25) colors. So in terms of the degree d, it is hard to color within an O(logd) 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 logd. 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 klogk/25-colorable graph (not exp((klogk)/25). This has recently been improved by Huang to 2k1/3 in a paper that will appear in the next STOC. (arxiv.org/abs/1301.5216)
Michael Lampis
Why do you think that k(logk)/25 and exp((klogk)/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 Δ has a coloring using k=ΔΔ+1 colors is NP-complete (k3)

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