Definicje itp.
Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!).
Niech będzie hipergrafatem.
Następnie dla hipergraph i mapowania ,
{ }.
Dodatkowo, niech waga ( ) = .
Wówczas ułamkowy rozkład hipertree jest potrójny , gdzie:
- jest drzewnym rozkładem i
- to rodzina mapowań od do st dla każdego .
Następnie znaczy szerokość z jest {waga (\ gamma_t), T \ w V (T) }.max ( γ t
Wreszcie ułamkową hypertree szerokość , Fhw ( ), jest co najmniej na szerokości ponad możliwych ułamkowe dekompozycji hypertree z .
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:
Czy coś wiadomo o (nie) podatności na CSP na wykresach z nieograniczoną ułamkową szerokością hipertree?
źródło