k-Färbung ist schneller als die Berechnung der chromatischen Zahl
k-Coloring is Faster than Computing the Chromatic Number
Or Zamir beweist, dass die k-Färbung von Graphen mit n Knoten einen randomisierten Algorithmus mit Laufzeit (2−ε_k)^n für jedes feste k besitzt, wobei ε_k > 0. Zuvor waren nur für k ≤ 6 schnellere Lösungen bekannt als der allgemeine O*(2^n)-Algorithmus von Björklund, Husfeldt und Koivisto (SICOMP 2009) zur Berechnung der chromatischen Zahl. Durch die Verallgemeinerung und Kombination von Werkzeugen aus der Reduktion von (k+2)-Färbung auf k-Listenfärbung (Zamir, ICALP 2021) und dem auf Hypergraph-Containern basierenden Ansatz (Zamir, STOC 2023) sowie neuen Algorithmen für Listenfärbungs-Instanzen mit gemischten langen und kurzen Farblisten erhält er eine iterierbare Reduktion von (k+1)-Listenfärbung auf k-Listenfärbung über festen Paletten.
Wir beweisen, dass die k-Färbung auf Graphen mit n Knoten einen randomisierten Algorithmus hat, der in der Zeit (2−ε_k)^n läuft, wobei ε_k > 0 für jedes feste k ist.
- emil-lp
Für diejenigen, die es nicht kennen:
K-Färbung ist die Eigenschaft, dass ein Graph mit k Farben gefärbt werden kann, sodass keine zwei benachbarten Knoten dieselbe Farbe erhalten. Das K-Färbungs-Problem ist ein Entscheidungsproblem, also eine Ja/Nein-Frage.
Die chromatische Zahl eines Graphen ist das kleinste k, für das er eine k-Färbung besitzt.
Offensichtlich gilt: Wenn man einen Algorithmus für das eine hat, hat man auch einen für das andere.
Die Frage war: Ist es schneller, die k-Färbung zu berechnen als die tatsächliche (kleinste) k, also die chromatische Zahl?
Wälder, Bäume und bipartite Graphen sind 2-färbbar. Planare Graphen sind 4-färbbar. Es ist NP-vollständig zu überprüfen, ob die chromatische Zahl eines planaren Graphen 3 ist.
Es gibt ein sehr interessantes offenes Problem, die Hadwiger-Vermutung, die im Wesentlichen besagt, dass die chromatische Zahl die Clique-(Minor-)Zahl ist (was auch immer das bedeutet).
- black_knight
Am Ende des Papiers von brev gibt es einen Abschnitt über die LLM-Nutzung.
Nun wird dieses Papier ein Peer-Review durchlaufen. Und wenn es veröffentlicht wird, werden wir dem Ergebnis genauso vertrauen wie jedem anderen veröffentlichten Ergebnis in der Mathematik. Aber während Menschen nicht unfehlbar sind, neigen LLMs dazu, selbstbewusstes Zeug auszuspucken, das korrekt aussieht. Daher mache ich mir Sorgen, wenn es auf diese Weise zur Erstellung von Beweisen verwendet wird. Peer-Review ist nicht perfekt und möglicherweise nicht darauf ausgelegt, die Fehlerart von LLMs zu erkennen.
Es gibt eine Lösung dafür, nämlich das Ergebnis zu formalisieren und maschinell verifizieren zu lassen. Und mit LLMs, wage ich zu behaupten, wird dies in Zukunft die beste Praxis sein.
- drivebyhooting
Nicht viel schneller.
Jeder k-Färbungs-Algorithmus mit Komplexität F(n) kann verwendet werden, um einen Algorithmus für die chromatische Zahl mit Komplexität lg(N)F(N) zu erstellen, indem man einfach auf N bisektiert.