Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest trudne (łatwe)?

Treewith jest ważnym parametrem grafu, który wskazuje, jak blisko wykres jest od drzewa (choć nie w ścisłym sensie topologicznym).

Powszechnie wiadomo, że obliczenie szerokości jest trudne dla NP.

Czy są jakieś naturalne klasy wykresów, w których trudno jest obliczyć szerokość ?

Podobnie:

Czy istnieją ciekawe klasy grafów, w których obliczanie szerokości jest łatwe? Jeśli tak, czy jest jakaś właściwość / test strukturalny, który można wykorzystać? Czyli wykres ma własność obliczeniowe treewidth z . $G$ $X$ $\Rightarrow$ $G \in \mathbf{P}$

— PsySp
źródło

Dla klas wykresów, w których szerokość jest ograniczona lub nieograniczona, możesz zobaczyć graphclasses.org; wyszukaj parametr treewidth, a otrzymasz listę klas wykresów, w których treewidth jest ograniczony (lub nieograniczony): graphclasses.org/classes/par_10.html

— Cyriac Antony

Możesz także użyć ich aplikacji Java, aby zobaczyć klasy, w których rozkład szerokości poprzecznej jest trudny (lub łatwy)

— Cyriac Antony

$9$ $2$ $2$

$\Pi(G)$ $G$ $G$ $O(|\Pi(G)|^2 \cdot n^{O(1)})$ $G$ $k$ $2^{O(k^3)}n$ $O((\log n)^{1/3})$

Niezwykle otwartym problemem jest to, czy obliczenie szerokości wykresów płaskich jest rozwiązaniem wielomianowym rozwiązanym czasowo, czy NP całkowitym. Warto zauważyć, że powiązana szerokość gałęzi parametru wykresu (która zawsze mieści się w współczynniku 1,5 od odległości od linii prostej) jest czasem wielomianowym obliczalnym na wykresach płaskich.

— Daniello
źródło

Dziękuję Ci. Więc jedyną klasą znaną jako twardą są wykresy dwudzielne? Właściwość potencjalnych maksymalnych klik nie wydaje mi się zaskakująca. Czy ta właściwość może być testowana w czasie P?

— PsySp

3^{n / 3}

$3^{n/3}$

Bodlaender i Thilikos [DAM 79 (1997) 45-61] wykazali, że obliczanie szerokości pasma jest trudne dla NP dla wykresów o maksymalnym stopniu 9.

— Yota Otachi

Oprócz twardości dla wykresów dwudzielnych należy również wspomnieć, że obliczanie szerokości grzbietu jest również trudne dla wykresów dwudzielnych, co, jak sądzę, po raz pierwszy zaobserwował Ton Kloks w swojej pracy doktorskiej.

— vb le

Można wspomnieć, że (prawie) nic nie wiadomo na temat złożoności aproksymacji i sparametryzowanych dolnych granic. Zasadniczo może istnieć algorytm PTAS lub algorytm czasu podwykładniczego, choć oba są bardzo mało prawdopodobne. Jedyną twardością aproksymacyjną jest ta oparta na rozszerzeniu małego zestawu (SSE). doi: 10.1613 / jair.4030.

— Yixin Cao