Treewidth i pakowanie

9

Moje pytanie jest trochę niejasne. Zastanawiam się, czy (i jak) możemy zastosować pojęcie szerokości do problemów z upakowaniem na wykresach.

Byłbym zadowolony z wszelkich spostrzeżeń lub odniesień do wcześniejszych prac badawczych na ten temat (zakładając, że jest to jakaś relacja). Dzięki.

ds.algorithms reference-request graph-theory graph-algorithms approximation-algorithms Nikhil
źródło

11

Mogę zinterpretować to pytanie na dwa różne sposoby:

1) Jeśli chodzi o właściwości algorytmiczne problemów upakowania na wykresach ograniczonej szerokości, twierdzenie Courcelle'a pokazuje, że dla każdego ustalonego $k$ możemy optymalnie rozwiązywać problemy wyrażalne w logice Monadic drugiego rzędu w czasie liniowym na wykresach szerokości co najwyżej $k$ (patrz na przykład http://dx.doi.org/10.1093/comjnl/bxm037, aby uzyskać ankietę na temat właściwości algorytmicznych wykresów ograniczonej szerokości grzbietu). Ponieważ w MSOL można sformułować wiele problemów z pakowaniem, dowodzi to wykonalności wielu takich problemów na wykresach ograniczonej szerokości, w tym Niezależny zestaw, Pakowanie trójkątów, Pakowanie cykliczne, Pakowanie rozłącznych kopii dowolnych stałych wykresów, Pakowanie mniejszych modeli z rozłączaniem wierzchołków niektórych stałych wykresów H i tak dalej. Ale ponieważ ta łatwość obsługi obejmuje wszystkie problemy definiowane przez MSOL, nie jest ona specyficzna dla pakowania.

2) Jeśli chodzi o zależności graficzno-strukturalne między wypełnieniami a szerokością, interesujące mogą być następujące elementy. Dzięki pracy Robertsona i Seymour wiadomo, że istnieje funkcja $f \colon \mathbb{N} \to \mathbb{N}$ tak, że co najmniej każdy wykres szerokości $f(r)$ zawiera $r \times r$ siatka jako niewielka (pierwotnie związany z $f$ podany przez Seymour i Robertson został później ulepszony we współpracy z Thomasem; patrz http://www.sciencedirect.com/science/article/pii/S0095895684710732, aby zapoznać się z aktualną najlepszą wersją). Dlatego jeśli masz strukturę $S$ takie, że wiele kopii $S$ można zapakować w $r \times r$ grid minor, to wiesz, że każdy wykres dużej szerokości zawiera duże opakowanie kopii $S$ . Na przykład jako $r \times r$ grid (nawet $r$ ) zawiera $(r/2)^2$ cykle rozłączne wierzchołków, wynika z tego wykresu szerokości $f(r)$ zawiera co najmniej $(r/2)^2$ rozłączne cykle.

Bart Jansen
źródło

Bart Być może nie ma to znaczenia, ale czy widzisz związek między rekonstrukcją wykresu a ich szerokością drzewa? Czy masz również link do darmowej wersji swojego artykułu prof? (Optymalizacja kombinatoryczna na wykresach ograniczonej szerokości boku)

Saeed

Treewidth papier jest dostępny w CiteSeer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2561 . Jeśli chodzi o rekonstrukcję wykresu: masz na myśli proces, w którym, biorąc pod uwagę multiset wszystkich podsgrafów uzyskanych przez usunięcie pojedynczego wierzchołka, chcesz zrekonstruować oryginalny wykres? Wygląda na to, że Shiva Kintali zastanawiał się niedawno nad tym, czy hipoteza rekonstrukcji grafu jest prawdziwa dla drugiej linii: cstheory.stackexchange.com/questions/5155/… .

Bart Jansen,

Dzięki bart, tak, widzę pytanie Shivy, ale, To było rok temu, może być jakiś nowy wynik, dzięki wszystkim.

Saeed

Witryna Shivy zawiera dwa manuskrypty na ten temat: „O rekonstrukcji k-drzew i drzew regularnych grafów” oraz „Nowe właściwości wykresów odtwarzalnych” z dopiskiem „pdf wkrótce” ( cs.princeton.edu/~kintali/#proprecon ). Możesz skontaktować się z nim bezpośrednio, aby zapytać o aktualny stan wiedzy.

Bart Jansen

Po tej odpowiedzi najlepsza granica szerokości jest wymagana do zapewnienia

r \times r

$r \times r$ drobne siatki zostały poprawione przez Kawarabayashi i Kobayashi do

2^{O (r^{2} \log r)}

$2^{O(r^2\log r)}$ w dx.doi.org/10.4230/LIPIcs.STACS.2012.278 , a Seymour zgłosił poprawkę do

2^{O (r \log r)}

$2^{O(r \log r)}$ w sierpniu 2012 r.

András Salamon

7

Problemem maksymalnego zestawu niezależnego jest problem upakowania (można go traktować jako upakowanie rozłącznych gwiazd) i ma on dobrze znany algorytm z czasem działania $2^k \operatorname{poly(n)}$ na wykresach o szerokości co najwyżej $k$ .

Janne H. Korhonen
źródło

Dziękuję Janne za twoją odpowiedź. Znam algorytm MIS. Czy oprócz MIS zastosowano pojęcie poprzeczek do pakowania innych konstrukcji? Ponadto, nie jestem do końca przekonany, aby myśleć o MIS jako o pakowaniu rozłącznych gwiazd. Czy mógłbyś wyjaśnić swój punkt widzenia na ten temat? (jaką strukturę gwiazd próbujesz spakować, jakie jest pojęcie „rozłącznych gwiazd”)?

Nikhil

1

Nie jest to tak proste, jak myślałem, publikując odpowiedź. Bardziej odpowiednie byłoby „pakowanie gwiazd rozłącznych”, a następnie musisz wymagać, aby każda umieszczona gwiazda miała możliwie największy stopień. Nie pamiętam, aby widzieć szerokość pasma zastosowaną w bardziej skomplikowanych problemach z pakowaniem.

Janne H. Korhonen

1

Maksymalny niezależny zestaw jest z pewnością „problemem pakowania” w zwykłej terminologii; innym przykładem problemu pakowania jest maksymalne dopasowanie. (

Pakują

6

Wspaniałym odniesieniem na ten temat jest poniższy artykuł ankiety Bruce'a Reeda.

Reed, B. (1997). Szerokość drzewa i sploty: Nowa miara łączności i niektóre aplikacje. Ankiety w kombinatoryce, 241, 87-162.

Jeden z moich ostatnich artykułów pozwala na ominięcie twierdzenia o pomniejszeniu siatki w niektórych przypadkach za pomocą twierdzeń o rozkładzie poprzecznym. Zobacz papier poniżej.

Dekompozycje i zastosowania wykresu dużej-Treewidth http://arxiv.org/abs/1304.1577

Chandra Chekuri
źródło

5

To jest również niejasna odpowiedź. Istnieje dualność podobna do twierdzenia Erdosa-Posy dla wykresów ograniczonej szerokości. Zobacz na przykład Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Wzmocnienie właściwości Erdösa-Pósy dla mniejszych zamkniętych klas grafów. Journal of Graph Theory 66 (3): 235-240 (2011)

R2-D2
źródło

Treewidth i pakowanie

Odpowiedzi: