Harte Erweiterbarkeitsprobleme

13

Beim Erweiterbarkeitsproblem erhalten wir einen Teil der Lösung und wir möchten entscheiden, ob wir es zu einer vollständigen Lösung erweitern können. Einige Erweiterbarkeitsprobleme sind effizient lösbar, während andere Erweiterbarkeitsprobleme ein einfaches Problem in ein schweres verwandeln.

Zum Beispiel besagt das Konig-Hall-Theorem, dass alle kubischen zweigeteilten Graphen dreikantig färbbar sind, die Erweiterbarkeitsversion jedoch -vollständig wird,NP wenn wir die Farben einiger Kanten erhalten.

Ich bin auf der Suche nach einem Übersichtsartikel über schwierige Erweiterbarkeitsprobleme, bei dem das Grundproblem einfach (oder trivial wie im obigen Beispiel) ist.

cc.complexity-theory reference-request graph-theory np-hardness Mohammad Al-Turkistany
quelle
1
Ich weiß nicht, ob es eine Übersicht über Erweiterbarkeitsprobleme gibt, aber mindestens ein sehr gut untersuchtes Problem ist das Vorfärben von Erweiterungen . Sie werden viele Treffer finden, die nach dem Problemnamen suchen.
Juho
Zwei Anmerkungen: 1) Gibt es NPC-Probleme, die nicht in ein hartes Erweiterbarkeitsproblem umgewandelt werden können? 2) Ich denke, dass es auch eine Umfrage sehr interessant wäre, die sich nur auf Erweiterbarkeitsprobleme konzentriert, für die das "Basis" -Problem eine unbekannte Komplexität aufweist (z. B. das einfarbige Problem ohne Rechtecke oder einige Puzzlespiele)
Marzio De Biasi,
@ MarzioDeBiasi Sehr interessanter Kommentar. 1) Ich kenne kein solches Beispiel. 2) GI ist ein guter Kandidat und ich vermute, dass sein Erweiterungsproblem NP-vollständig ist.
Mohammad Al-Turkistany
1
Die Erweiterungsversion von NP-hard-Problemen ist NP-hard (suchen Sie gierig mit dem Oracle nach Zertifikaten).
Kaveh
2
@MarzioDeBiasi: GI-Erweiterbarkeit ist in der Tat GI-vollständig (nicht nur GI-schwer, was ich glaube, was Sie damit sagen wollten) und daher nicht NP-vollständig, wenn PH nicht zusammenbricht. Die GI-Erweiterbarkeit kann umformuliert werden als vertex-farbige GI (wobei Vertices einer bestimmten Farbe nur Vertices derselben Farbe zuordnen können), was sich auf verschiedene Weise auf GI reduziert (eine davon besteht darin, Gadgets an Vertices anzuhängen, ähnlich) auf Ihre idea). Kn
Joshua Grochow

Antworten:

10

Das nxn-Sudoku-Diagramm zu färben ist trivial, aber wenn Ihnen einige der Farben gegeben werden (die erweiterbare Version), wird es NP-vollständig.

n=k2n2(r1,r2;c1,c2)r1,r2,c1,c2∈[k]=[n](r1,r2)(r1,r2;∗,∗)n(c1,c2)(∗,∗;c1,c2)n(r1,c1)(r1,∗;c1,∗)n

Joshua Grochow
quelle