Trudne problemy dla wykresów wyższego rodzaju

17

Wykresy planarne mają rodzaj zero. Wykresy osadzane na torusie mają co najwyżej rodzaj 1. Moje pytanie jest proste:

Czy są jakieś problemy, które można rozwiązać wielomianowo na wykresach planarnych, ale trudne NP na wykresach rodzaju 1?
Bardziej ogólnie, czy są jakieś problemy, które można rozwiązać wielomianowo na wykresach rodzaju g, ale NP-trudne na wykresach rodzaju> g?

— Shiva Kintali
źródło

W przypadku drugiego pytania, czy chcesz, aby problem był trudny NP dla wykresów rodzaju> = k, gdzie k jest stałą większą niż g? LUB czy po prostu chcesz, aby problem był trudny do NP w przypadku grafów, których rodzaj nie jest mniejszy niż g (co jest równoważne z trudnością w NP dla ogólnych wykresów)?

— Robin Kothari,

1

Szukam problemów NP-trudnych dla wykresów rodzaju> = k, gdzie k jest stałą większą niż g.

— Shiva Kintali,

16

To jest rozgłos mojej własnej pracy, ale przecinanie liczby i 1-planarności są trywialnie rozwiązywalne na grafach płaskich, ale trudne dla grafów pierwszego rodzaju. Zobacz http://arxiv.org/abs/1203.5944

— ktoś
źródło

3

„Wykres jest prawie płaski, jeśli można go uzyskać z wykresu płaskiego przez dodanie krawędzi. Wykres jest 1-płaski, jeśli ma rysunek, w którym każda krawędź jest przecięta co najwyżej jedną inną krawędzią. Pokazujemy, że jest NP -stabilna decyzja, czy dany wykres bliski planarny jest 1-planarny. ” Coś mi brakuje. Dlaczego każdy wykres zbliżony do płaskiego nie jest również jednopłaszczyznowy?

— Tyson Williams,

4

Wydaje mi się, że mówisz, że możesz po prostu osadzić

na płaskiej powierzchni i ponownie dodać krawędź. Jednak ta dodatkowa krawędź może przekroczyć więcej niż jedną krawędź, naruszając 1-płaskość.

G - e

$G-e$

— Timothy Sun,

@TimothySun Tak. Każda krawędź inna niż

zostanie przekroczona najwyżej raz (przez

), ale

może zostać przekroczona przez więcej niż jedną inną krawędź, co jest niedozwolone. Dzięki.

e

$e$

e

$e$

e

$e$

— Tyson Williams,

4

Jeśli problemy z zabawkami są w porządku:

Niech i niech będzie jakimś wykresem rodzaju . Dla w CNF formuły, niech być pewne kodowania postaci wykresu płaskiego wraz z kopią rozłącznego z . $g\in\mathbb{N}$ $H$ $g+1$ $\phi$ $G_\phi$ $\phi$ $H$

Biorąc pod uwagę , który jest wykresem rodzaju , trudno jest stwierdzić, czy jest zadowalające. Problem ten staje się jednak trywialny, gdy ogranicza się do wykresów rodzaju . $G_\phi$ $g+1$ $\phi$ $\leq g$

— Radu Curticapean
źródło

2

co to za problem na wykresach rodzaju

\leq g

$\leq g$

— Sasho Nikolov

1

Wszystkie wykresy

mają rodzaj

. Tak więc, jeśli ograniczysz problem do wykresów rodzaju

, zawsze możesz odrzucić.

G_{ϕ}

$G_\phi$

g + 1

$g+1$

g

$g$

— Radu Curticapean

ach, to staje się naprawdę trywialne, rozumiem

— Sasho Nikolov

2

EDYCJA (2012-09-05): Komentarze Jeffa i Radu są słuszne. Cytowany wynik nie odpowiada na pytanie. Aby rozwinąć komentarz Radu, oto pokrewny algorytm Bravyi, który daje algorytm do kurczenia się tensorów zapałki na wykresie z rodzajem z czasem pracy gdzie jest minimalną liczbą krawędzi, które należy usunąć z , aby był płaski. $G$ $g$ $T=poly(n) + 2^{2g} O(m^3)$ $m$ $G$

Cai, Lu i Xia niedawno udowodnili następującą dychotomię dla problemów z liczeniem #CSP:

Dowodzimy twierdzeń dychotomii złożoności w ramach liczenia problemów CSP. Lokalne funkcje ograniczeń pobierają dane logiczne i mogą być dowolnymi funkcjami symetrycznymi o wartości rzeczywistej. Udowadniamy, że każdy problem w tej klasie należy do dokładnie trzech kategorii:

(1) te, które są możliwe do obliczenia (tj. Wielomianowy czas obliczalny) na grafach ogólnych, lub
(2) te, które są # P-twarde na grafach ogólnych, ale są możliwe do opracowania na płaskich wykresach , lub
(3) te, które są # P-twarde nawet na wykresach płaskich.

Kryteria klasyfikacji są jednoznaczne.

— Martin Schwarz
źródło

2

To nie odpowiada na pytanie. Czy kategoria (2) może być podzielona na (2a) podatne na wykresy płaskie, ale # P-twarde dla wykresów toroidalnych i (2b) podatne na wykresy rodzaju ograniczonego, ale # P-twarde dla wykresów rodzaju niezwiązanego?

— Jeffε

3

Przypadek (2) składa się z problemów, które można sprowadzić do liczenia idealnych dopasowań na wykresach płaskich poprzez wprowadzenie lokalnych gadżetów płaskich. Wiadomo również, że idealne dopasowania można policzyć w czasie wielomianowym na grafach z ograniczonym rodzajem. Zatem wszystkie problemy w przypadku (2) są faktycznie możliwe do rozwiązania na grafach z ograniczonym rodzajem.

— Radu Curticapean

2

Dla każdego ustalonego istnieje algorytm czasu wielomianowego do określania, czy wykres ma rodzaj (co najwyżej) . Niech będzie dowolnym problemem, który jest NP-kompletny na wykresach rodzaju większych niż (np. 3-kolorowalność). Dla każdej stałej problem „Czy wykres wejściowy ma rodzaj co najwyżej czy jest w (lub w obu)?” jest NP-kompletny dla ogólnych danych wejściowych, ale ma algorytm czasu wielomianowego, gdy dane wejściowe są ograniczone do wykresów rodzaju co najwyżej . $g$ $g$ $X_g$ $g$ $g$ $g$ $X_g$ $g$

Pomysł ten może być dość ogólnie stosowany do tworzenia problemów, które są „twarde” na grafach ogólnych, ale „łatwe” na niektórych grafach klasy , o ile określenie „członkostwa” w „ ” jest „łatwe” . $\mathcal C$ $\mathcal C$

— David Richerby
źródło