CSPs mit unbegrenzter gebrochener Hyperbaumbreite

10

a´H P T I M E.HHPTIME

Definitionen usw.

Eine großartige Übersicht über Standard-Baumzersetzungen und Baumbreite finden Sie hier (Vielen Dank im Voraus, JeffE!).

Sei ein Hypergraph.H

Dann für einen Hypergraphen und eine Abbildung ,Hγ:E(H)[0,)

B(γ)= { vV(H):eV(H),veγ(e)1 }.

Zusätzlich sei weight ( γ ) = eEγ(e) .

Dann ist eine gebrochene Hyperbaumzerlegung von H ein Tripel (T,(Bt)tV(T),(γt)tV(T)) , wobei:

  • (T,(Bt)tV(T)) ist eine Baumzerlegung von H und
  • (γt)tV(T) ist eine Familie von Abbildungen von E(H) bis [0,) st für jedes tV(T),BtB(γt) .

Dann sagen wir , die Breite von ist {Gewicht }.(T,(Bt)tV(T),(γt)tV(T))max(γt),tV(T)

Schließlich ist die fraktionierte Hypertree Breite , fhw ( ), ist die Mindestbreiten der über alle möglichen Zerlegungen fraktionierte Hypertree von .HHH

Frage

Wie oben angegeben, gibt es einen Polynomzeitalgorithmus, um den CSP zu lösen, wenn die gebrochene Hyperbaumbreite des zugrunde liegenden Graphen eines CSP durch eine Konstante begrenzt ist. Am Ende des verlinkten Papiers wurde jedoch als offenes Problem offen gelassen, ob es polynomzeitlösbare Familien von CSP-Instanzen mit unbegrenzter Hypertree-Breite gab. (Ich sollte auch darauf hinweisen, dass diese Frage im Fall einer begrenzten oder unbegrenzten Baumbreite ( ACM-Zitat ) unter der Annahme, dass vollständig gelöst ist .) Da seit dem ersten verknüpften Artikel einige Zeit vergangen ist , Außerdem ist mir der allgemeine Zustand dieses Teilbereichs relativ unbekannt. Meine Frage lautet:FPTW[1]

Ist etwas über die (In-) Traktierbarkeit von CSPs über Graphen mit unbegrenzter gebrochener Hyperbaumbreite bekannt?
Daniel Apon
quelle

Antworten:

8

Sie haben zwei Artikel verlinkt, beide mit Vermutungen. Ich nehme an, Sie meinen Grohes Vermutung von 2007.

Diese Frage wurde 2008 beantwortet:

Satz 5. CSP (C , _) ist in NP, aber weder in P noch NP-vollständig (es sei denn, P = NP). Darüber hinaus kann die Menge in deterministischer Polynomzeit bestimmt werden.000

Die Idee ist, Löcher in den Instanzgrößen von CLIQUE durch dieselbe verzögerte Diagonalisierungstechnik zu blasen, die Ladner für seinen Satz eingeführt hat. Beachten Sie, dass der Satz C beliebig große Seilschaften enthält, und die fraktionierte Hypertree Breite eines -clique ist . Es ist also möglich, CSPs der Form CSP (A, _) von mittlerer Komplexität zu haben, wobei A eine unbegrenzte gebrochene Hyperbaumbreite hat. Dies verneint Grohes Vermutung. n n / 20nn/2

Auf derselben Konferenz hatten Chen, Thurley und Weyer ein Papier mit einem ähnlichen Ergebnis, das jedoch starke Einbettungen erforderte, so dass es technisch nicht die richtige Form für die Vermutung hatte.

Schließlich kann jede Klasse von CSP-Instanzen in eine Darstellung mit einer Bruchteil-Hyperbaumbreite im ungünstigsten Fall umgewandelt werden. In vielen Fällen ist diese Transformation in ihrer Größe polynomiell begrenzt und kann in Polynomzeit durchgeführt werden. Dies bedeutet, dass es einfach ist, CSPs mit unbegrenzter fraktionierter Hyperbaumbreite und sogar modulohomomorpher Äquivalenz zu erzeugen. Diese CSPs werden nicht die Form CSP (A, _) haben, da die Zielstrukturen speziell sind, aber sie liefern einen guten Grund, warum die CSPs, die nur durch Beschränkung der Quellstrukturen definiert werden, nicht allzu interessant sind: Es ist oft gerecht Es ist zu einfach, die baumartige Struktur einer CSP-Instanz auszublenden, indem die Darstellung so geändert wird, dass die Quellstruktur eine große Breite hat. (Dies wird in Kapitel 7 meiner Arbeit besprochen .)

András Salamon
quelle
danke für die tolle antwort. Eine kurze Folgefrage: Meine Lektüre von "Die Komplexität von Homomorphismus und Constraint-Zufriedenheitsproblemen von der anderen Seite gesehen" ist, dass es eine P vs. NP-c-Dichotomie für CSPs der Form CSP (C, _) für gibt Nicht-Hypergraphen von begrenzter Arität, bin ich richtig, wenn ich das glaube? Oder mehr auf den Punkt gebracht - es gibt keine versteckte Annahme / Vermutung in Korollar 6.1 dieses Papiers, von der ich nichts weiß, oder? Oder ist die Dichotomie dort einfach P gegen Nicht-P? (Entschuldigung, wenn dies offensichtlich ist.)
Daniel Apon
2
@ Daniel: In diesem Artikel ging es nicht so sehr um Dichotomien, sondern darum, die Fälle mit beschränkter Strukturbeschränkung genau zu charakterisieren, als solche mit begrenzter Breite. Es war bekannt, dass die begrenzte Breite nachvollziehbar ist, aber der Hauptteil von Grohes Papier ist in die andere Richtung. Unbegrenzte Breite impliziert das Einbetten von Raster-Minderjährigen beliebig großer Größe, mit denen ein NP-hartes Problem wie CLIQUE codiert werden kann. Die Feder / Vardi-Dichotomie-Vermutung für CSPs bezieht sich auf Einschränkungen vom Typ CSP (_, B), von denen angenommen wird, dass sie entweder in P oder NP-vollständig sind.
András Salamon
@ Daniel: Übrigens war mir dieses Zeug beim ersten Lesen nicht klar. Die bissige Zusammenfassung von Grohes Artikel in meinem vorherigen Kommentar hat Dave Cohen viel zu verdanken.
András Salamon