Czy nadal jest możliwe określenie złożoności obliczania szerokości wykresów płaskich?

Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy , czy jego szerokość wynosi . Jednakże, gdy zarówno jak i są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ). $k \in \mathbb{N}$ $G$ $\leq k$ $k$ $G$

Jednak gdy wykres wejściowy jest płaski , wydaje się, że o złożoności wiadomo znacznie mniej. Problem był najwyraźniej otwarty w 2010 r., Twierdzenie to pojawiło się również w tej ankiecie w 2007 r . Oraz na stronie Wikipedii dotyczącej dekompozycji branżowych . I odwrotnie, problem występuje w NP-hard (bez dowodu odniesienia) we wcześniejszej wersji wspomnianej wcześniej ankiety, ale zakładam, że jest to błąd.

Czy nadal jest możliwe określenie złożoności problemu, biorąc pod uwagę i płaski wykres , oznaczenia ma szerokość ? Jeśli tak, to czy zostało to zgłoszone w ostatnim artykule? Czy znane są jakieś wyniki częściowe? Jeśli nie, kto to rozwiązał? $k \in \mathbb{N}$ $G$ $G$ $\leq k$

— a3nm
źródło

Interesujące pytanie, okrzyki za ponowne uruchomienie ankiety. Uważam, że w przypadku moich 2 centów pierwotnym źródłem liniowego dowodu czasu jest Bodlaender, ale stały czynnik ukryty przez asymptotyczną notację złożoności jest ogromny. Być może interesującym efektem ubocznym / rozszerzeniem twojego pytania byłoby to, czy ograniczenie płaskie pozwala na bardziej praktyczny stały czynnik w tym kontekście?

— Fasermaler,

Myślę, że jest to „znany i stary problem”, więc jeśli nie znajdziesz papieru, prawdopodobnie nadal jest to problem otwarty. Inne „dowody”: wykład z kursu Algorytmy grafowe, zastosowania i wdrożenia (2015), wykład z kursu Wykresy i algorytmy: zaawansowane tematy (2014), encyklopedia algorytmów (2008).

— Marzio De Biasi,

@ Sariel: Można go aproksymować w ramach stałego współczynnika (3/2), wykorzystując fakt, że jego szerokość i szerokość gałęzi mieszczą się w stałej między sobą, a płaską szerokość gałęzi można obliczyć w czasie wielomianowym. Można go także aproksymować w dzienniku dla wszystkich wykresów za pomocą Leightona – Rao; patrz kintali.wordpress.com/2010/01/28/approximating-treewidth

— David Eppstein

@Fasermaler pierwszym krokiem w algorytmie Bodlaendera (i poprzednich algorytmach, które były FPT, ale nie liniowe) jest obliczenie przybliżonego rozkładu drzewa, na którym można zastosować programowanie dynamiczne w celu znalezienia optymalnego rozkładu. Im ściślejsze zbliżenie, tym szybszy drugi krok. Zatem fakt, że ściślejsze przybliżenia do płaskiej szerokości można znaleźć za pomocą szerokości gałęzi, prawdopodobnie prowadzi do lepszej zależności od parametru (kosztem powrotu do wielomianu z liniowego). Ale nie znam artykułów analizujących to dokładnie.

— David Eppstein,

Odnośnie problemu przybliżenia szerokości.

-approximation znalezienia rzadki / symetryczne Node-separatory dadzą

-approximation do treewidth. Zatem na ogólnych wykresach otrzymamy

α

$\alpha$

O (α)

$O(\alpha)$

przez ARV / Feige-Lee-Hajiaghayi i

w płaskich i właściwych małoletnich zamkniętych rodzinach. Dla ogólnych wykresów można uzyskać

O (\sqrt{\log n})

$O(\sqrt{\log n})$

O (1)

$O(1)$

gdzie

to szerokość.

O (\sqrt{\log k})

$O(\sqrt{\log k})$

k

$k$

— Chandra Chekuri,

O ile mi wiadomo, kompletność NP obliczania szerokości wykresu płaskiego jest nadal otwarta. Najnowsze referencje, jakie znam, to ankieta przeprowadzona przez Bodlaendera z 2012 r. Zatytułowana „Fixed-Parameter Tractability of Treewidth and Pathwidth”, która pojawiła się podczas festschrift na 65. urodziny Mike'a Fellowsa. Problem wymieniono w podsumowaniu ankiety.

— Bart Jansen
źródło

Dzięki! (I dzięki również @MarzioDeBiasi za sugestie innych referencji.) Czy z ciekawości ktoś zdarza się również wiedzieć, kiedy problem został po raz pierwszy postawiony?

— a3nm