Złożoność dominującego problemu w określonych podklasach wykresów akordowych

Interesuje mnie złożoność problemu dominującego zestawu (DSP) w niektórych określonych klasach grafów, które są podklasami grafów akordowych .

Wykres jest nieukierowanym wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ścieżek w jakimś niekierowanym drzewie. Niech UP będzie klasą niekierowanych grafów ścieżek.

Wykres jest grafem EPT, jeśli jest to wykres przecięcia krawędzi rodziny ścieżek w jakimś niekierowanym drzewie. Wykres EPT może nie być akordowy, ale niech CEPT będzie klasą grafów akordowych EPT.

Wykres jest (zrootowanym) wykresem ścieżki, jeśli jest to wykres przecięcia wierzchołków rodziny ukierunkowanych ścieżek w jakimś zrootowanym ukierunkowanym drzewie (tj. Wszystkie łuki skierowane z dala od korzenia). Niech RDP będzie klasą (zrootowanych) ukierunkowanych wykresów ścieżek.

Mamy $RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Wiadomo, że DSP można rozwiązać w czasie liniowym dla wykresów w RDP, ale NP-kompletny dla wykresów UP [ Booth i Johnson, 1981 ]

Interesują mnie specjalne wykresy, które odpowiadają wykresom przecięcia wierzchołków rodzin nieukierowanych ścieżek w drzewach gąsienicowych o maksymalnym stopniu 3. Dokładniej, te „gąsienice” są zbudowane ze ścieżki, w której każdy drugi wierzchołek ma wiszący stopień - jeden wierzchołek przymocowany do. Nazwijmy tę klasę cat-UP.

Co więcej, moje specjalne wykresy można również konstruować jako wykresy przecięcia krawędzi niektórych rodzin ścieżek bezkierunkowych w określonych drzewach o maksymalnym stopniu 3.

Więc moje pytania to:

1) Czy złożoność DSP dla wykresów cat-UP jest znana? (zauważ, że redukcja [ Booth i Johnson, 1981 ] powoduje powstanie drzewa żywicielskiego, które ma maksymalny stopień 3, ale dość daleko od gąsienicy)

2) Jaka jest złożoność DSP dla wykresów CEPT? A czy dla wykresów CEPT powstających z drzewa gospodarza o maksymalnym stopniu 3? ( nie jest to znane ISGCI )

3) Czy jest jakikolwiek wynik złożoności DSP w blisko spokrewnionej rodzinie grafów?

Szkoda, że ​​tak długo czekałeś bez odpowiedzi. Nie znam klas, o które prosiłeś, ale znam niektóre powiązane klasy grafów i nowe techniki, które możesz wypróbować.

Najpierw wspomnę, że Steven Chaplick wykonał prace nad pokrewnymi klasami graficznymi, zakończył pracę na początku tego roku, być może jego badania były interesujące.

Wiem, że niektóre wyniki w tym kierunku wynikają z mojej własnej pracy. Klasy grafów ze strukturalnymi otoczeniami i aplikacjami algorytmicznymi. Daje to ogólną technikę rozwiązywania różnych problemów, w tym DSP w niektórych klasach grafów. Robimy to poprzez wprowadzenie nowych rozkładów grafów (patrz moja praca magisterska ).

$(d-1)^{3(s-1)}poly(n)$

$0$$k \times n$

Ta sama technika może zadziałać dla CEPT powstającego z drzewa gospodarza o maksymalnym stopniu 3, ale potrzebuję więcej czasu, aby zrozumieć tę klasę. Jeśli masz link do niektórych charakterystyk tej klasy, które by pomogły.