CSPs mit unbegrenzter gebrochener Hyperbaumbreite

$\acute{\rm a}$H ∈ P T I M $H$$H$$\in PTIME$

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$$\gamma : E(H) \rightarrow [0,\infty)$

$B(\gamma) =$ { $v \in V(H) : \sum_{e \in V(H), v \in e} \gamma(e) \ge 1$ }.

Zusätzlich sei weight ( $\gamma$ ) = $\sum_{e \in E}\gamma(e)$ .

Dann ist eine gebrochene Hyperbaumzerlegung von $H$ ein Tripel $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ , wobei:

• $(T, (B_t)_{t \in V(T)})$ ist eine Baumzerlegung von $H$ und
• $(\gamma_t)_{t \in V(T)}$ ist eine Familie von Abbildungen von $E(H)$ bis $[0, \infty)$ st für jedes $t \in V(T), B_t \subseteq B(\gamma_t)$ .

Dann sagen wir , die Breite von ist {Gewicht }.$(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$$\max$$(\gamma_t), t \in V(T)$

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

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:$FPT \ne W[1]$

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

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.$_0$$_0$

• Manuel Bodirsky und Martin Grohe, Nicht-Dichotomien in der Komplexität der Zwangszufriedenheit, ICALP 2008. doi: 10.1007 / 978-3-540-70583-3_16 ( PDF )

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 /$_0$$n$$n/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.

• Yijia Chen, Marc Thurley und Mark Weyer, Verständnis der Komplexität induzierter Subgraph-Isomorphismen , ICALP 2008. doi: 10.1007 / 978-3-540-70575-8_48 ( PDF )

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 .)