CSP z nieograniczoną ułamkową szerokością hipertree

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

Definicje itp.

Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!).

Niech $H$ będzie hipergrafatem.

Następnie dla hipergraph $H$ i mapowania $\gamma : E(H) \rightarrow [0,\infty)$ ,

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

Dodatkowo, niech waga ( $\gamma$ ) = $\sum_{e \in E}\gamma(e)$ .

Wówczas ułamkowy rozkład hipertree $H$ jest potrójny $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ , gdzie:

• $(T, (B_t)_{t \in V(T)})$ jest drzewnym rozkładem $H$ i
• $(\gamma_t)_{t \in V(T)}$ to rodzina mapowań od $E(H)$ do $[0, \infty)$ st dla każdego $t \in V(T), B_t \subseteq B(\gamma_t)$ .

Następnie znaczy szerokość z jest {waga (\ gamma_t), T \ w V (T) }.max ( γ $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$$\max$$(\gamma_t), t \in V(T)$

Wreszcie ułamkową hypertree szerokość $H$ , Fhw ( $H$ ), jest co najmniej na szerokości ponad możliwych ułamkowe dekompozycji hypertree z $H$ .

Pytanie

Jak stwierdzono powyżej, jeśli ułamkowa szerokość hipertree podstawowego wykresu CSP jest ograniczona stałą, wówczas istnieje algorytm wielomianu czasowego do rozwiązania CSP. Jednak pozostawiono jako otwarty problem na końcu połączonego dokumentu, czy istnieją jakieś rozwiązywalne rodziny instancji CSP w czasie wielomianowym o nieograniczonej szerokości hipertree. (Powinienem również zauważyć, że pytanie to zostało całkowicie rozwiązane w przypadku ograniczonej vs. nieograniczonej szerokości poprzecznej ( cytat z ACM ) przy założeniu, że .) Ponieważ minęło trochę czasu od pierwszego powiązanego artykułu, a ponadto jestem stosunkowo nieświadomy ogólnego stanu tego subpola, moje pytanie brzmi:$FPT \ne W[1]$

Czy coś wiadomo o (nie) podatności na CSP na wykresach z nieograniczoną ułamkową szerokością hipertree?

Powiązałeś dwa artykuły, oba z przypuszczeniami. Zakładam, że masz na myśli przypuszczenie Grohe z 2007 roku.

Odpowiedzi na to pytanie udzielono w 2008 r .:

Twierdzenie 5. CSP (C , _) występuje w NP, ale ani w P, ani w NP-zupełnym (chyba że P = NP). Ponadto zbiór C można ustalić w deterministycznym czasie wielomianowym.$_0$$_0$

• Manuel Bodirsky i Martin Grohe, Non-dychotomies in Constraint Satisfaction Complexity , ICALP 2008. doi: 10.1007 / 978-3-540-70583-3_16 ( PDF )

Chodzi o to, aby wysadzić dziury w rozmiarach instancji CLIQUE, przy użyciu tej samej techniki opóźnionej diagonalizacji, którą wprowadził Ladner w swoim twierdzeniu. Zauważ, że zbiór C zawiera dowolnie duże kliki, a ułamkowa szerokość hipertree drzewa kliki wynosi . Możliwe jest więc posiadanie CSP w postaci CSP (A, _) o pośredniej złożoności, w których A ma nieograniczoną ułamkową szerokość nadciśnienia. To odpowiada hipotezie Grohe'a przecząco.$_0$$n$$n/2$

Na tej samej konferencji Chen, Thurley i Weyer mieli artykuł z podobnym rezultatem, ale wymagało to silnego osadzenia, więc technicznie nie było odpowiedniej formy do przypuszczenia.

• Yijia Chen, Marc Thurley i Mark Weyer, Zrozumienie złożoności indukowanych izomorfizmów subgrafu, ICALP 2008. doi: 10.1007 / 978-3-540-70575-8_48 ( PDF )

Wreszcie dowolna klasa instancji CSP może zostać przekształcona w reprezentację o najgorszym przypadku ułamkowej szerokości hipertree. W wielu przypadkach transformacja ma wielomianowy rozmiar i może być wykonana w czasie wielomianowym. Oznacza to, że łatwo jest generować CSP o nieograniczonej frakcyjnej szerokości hipertree, nawet modulo homomorficznej równoważności. Te CSP nie będą miały formy CSP (A, _), ponieważ struktury docelowe są wyjątkowe, ale stanowią dobry powód, dla którego CSP zdefiniowane przez ograniczenie tylko struktur źródłowych nie są aż tak interesujące: często jest to po prostu zbyt łatwe do ukrycia drzewiastej struktury instancji CSP poprzez zmianę reprezentacji, aby struktura źródłowa miała dużą szerokość. (Omówiono to w rozdziale 7 mojej pracy ).