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

10

za´H P T I M EH.H.P.T.jaM.mi

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 γ:mi(H.)[0,) ,

b(γ)= { vV.(H.):miV.(H.),vmiγ(mi)1 }.

Dodatkowo, niech waga ( γ ) = eEγ(e) .

Wówczas ułamkowy rozkład hipertree H jest potrójny (T,(Bt)tV(T),(γt)tV(T)) , gdzie:

  • (T,(Bt)tV(T)) jest drzewnym rozkładem H i
  • (γt)tV(T) to rodzina mapowań od E(H) do [0,) st dla każdego tV(T),BtB(γt) .

Następnie znaczy szerokość z jest {waga (\ gamma_t), T \ w V (T) }.max ( γ t(T,(bt)tV.(T.),(γt)tV.(T.))max(γt),tV.(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:faP.T.W.[1]

Czy coś wiadomo o (nie) podatności na CSP na wykresach z nieograniczoną ułamkową szerokością hipertree?
Daniel Apon
źródło

Odpowiedzi:

8

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

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.0nn/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.

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

András Salamon
źródło
dzięki za świetną odpowiedź. Szybkie pytanie uzupełniające: moje czytanie „Złożoności homomorfizmu i problemów satysfakcji z ograniczeń widziane z drugiej strony” jest takie, że istnieje dychotomia P vs. NP-c dla CSP w postaci CSP (C, _) dla bez hipergrrafów ograniczonej arii, czy mam rację, że tak wierzę? Lub bardziej konkretnie - nie ma ukrytego założenia / przypuszczenia w następstwie 6.1 tego dokumentu, którego nie jestem świadomy, prawda? Czy też dychotomia jest po prostu P vs. not-P? (Przepraszam, jeśli to oczywiste.)
Daniel Apon
2
@Daniel: W tym artykule nie tyle chodziło o dychotomie, ile o precyzyjne scharakteryzowanie przypadków ograniczonych strukturą, jak przypadki o ograniczonej szerokości. Ograniczona szerokość była znana z tego, że można ją traktować, ale kluczowa część papieru Grohe jest w innym kierunku. Nieograniczona szerokość oznacza osadzenie nieletnich siatki o dowolnie dużych rozmiarach, których można następnie użyć do zakodowania trudnego NP problemu, takiego jak CLIQUE. Hipoteza dychotomii Feder / Vardi dla CSP dotyczy ograniczeń typu CSP (_, B), które uważa się za w P lub NP-kompletne.
András Salamon,
@Daniel: Nawiasem mówiąc, te rzeczy z pewnością nie były dla mnie oczywiste, kiedy pierwszy raz je przeczytałem. Szybkie podsumowanie pracy Grohe w poprzednim komentarzu wiele zawdzięcza Dave'owi Cohenowi.
András Salamon,