Trudne problemy NP na kartografach

12

To pytanie jest podobne do trudnych NP problemów na drzewach :

Istnieje duża liczba problemów z NP, które można rozwiązać na kartografach . Czy są jakieś znane problemy, które pozostają NP-kompletne, gdy są ograniczone do kartografów?

Mówiąc ściślej, interesują mnie przykłady, w których dane wejściowe składają się wyłącznie z niekierowanego, nieważonego kografu .

Dwie uwagi:

W przypadku ważonych kartografów wspomniano o takim problemie - TSP z dwoma podróżnikami
Cografy są „klasą podstawową” szerokości kliki, tak jak drzewa są klasą podstawową dla szerokości drzewa.

AKTUALIZACJA

Kilka dalszych przemyśleń (nie jestem do końca pewien): Jeśli dane wejściowe to tak naprawdę tylko cograf, pytanie musi brzmieć: „Czy cograf ma właściwość X?”. Wystarczyłoby, gdyby taki problem istniał w przypadku drzew, ponieważ odtąd można by zadać pytanie „Czy krąg cografu ma właściwość X?”.

cc.complexity-theory np-hardness graph-algorithms Martin Lackner
źródło

Tak więc, zapobiegając byciu (nie tak) zduplikowanym pytaniem, być może wymagamy również, aby te problemy z NP-zupełnością były wielomianowe w czasie, które można rozwiązać na drzewach?

Hsien-Chih Chang 張顯之

Oczywiście byłoby miło. Byłbym jednak przekonany, nawet gdyby tak nie było. Zwłaszcza, że wszystkie przykłady podane w oryginalnym wątku nie odpowiadają na moje pytanie (o ile rozumiem).

Martin Lackner,

11

Być może mój ulubiony otwarty problem jest interesujący: problem klikowania krawędzi na kartografach. W przypadku problemu kliki krawędziowej chcesz zakryć krawędzie cografu minimalną liczbą klików. Nie wiadomo, czy ten problem jest NP-zupełny.

$K_n^m$ $m$ $n$ $m - 2$ $n$ $K_n^m$ $n^2$ $n = 2$

Ton Kloks
źródło

10

Kilka problemów pozostaje NP-kompletnych, gdy są ograniczone do kartografów. Kolorowanie listy, liczba achromatyczna i indukowany izomorfizm subgrafu pozostają NP-kompletne.

[1] Hans L. Bodlaender. Liczba achromatyczna jest NP-pełna dla grafów i wykresów interwałowych. Inf. Proces. Lett., 31 (3): 135–138, 1989

[2] Klaus Jansen i Petra Scheffler. Uogólnione kolorowanie wykresów przypominających drzewa. Dyskretna Appl. Math., 75 (2): 135–155, 1997

[3] Peter Damaschke. Indukowany izomorfizm subgrafu dla kartografów jest NP-kompletny. Wykład Notatki z informatyki, 1991, Tom 484/1991, 72-78,

Mohammad Al-Turkistany
źródło

1

Wielkie dzięki za odpowiedź. To naprawdę interesujące problemy, ale myślę, że nie spełniają wymogu, aby dane wejściowe były tylko wykresami: dane wejściowe w [1] to wykres i liczba całkowita, [2] wykres i zestaw kolorów dla każdego wierzchołka, [ 3] dwa wykresy.

Martin Lackner,

3

Oto trywialne odmiany dwóch tych samych problemów, które pozostają NP-kompletne, ale mają jedynie dane wejściowe: czy dany danograf składa się z dwóch połączonych elementów, z których jeden jest indukowanym podzgrafem drugiego? Czy dany cograph ma kompletną kolorystykę, która nadaje każdemu z jego izolowanych wierzchołków wyraźny kolor?

David Eppstein

10

$G$ $H$ $H$ $G$ $H$ $G$ $\rho: V(G)\to V(H)$ $\gamma: V(H)\to V(G)$ $\rho\circ \gamma : V(H)\to V(H)$

vb le
źródło

2

Ponownie można to zinterpretować jako problem na pojedynczym cografie (który zdarza się, że ma dwa połączone komponenty).

David Eppstein

1

Widzę. Oczywiście można poprosić o problemy z NP-zupełnym, gdy dane wejściowe składają się wyłącznie z podłączonego , nieukierowanego, nieważonego kografu. Myślę, że pytanie jest dość interesujące.

wb.

1

G

$G$

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

| V (G_{1}) | \leq | V (G_{2}) |

$|V(G_1)|\le|V(G_2)|$

G_{1}

$G_1$

G_{2}

$G_2$

David Eppstein

Ach, w porządku!

vb le

Trudne problemy NP na kartografach

Odpowiedzi: