Menu

12 czerwca 2018 10:15

Tytuł: Losing Treewidth by Separating Subsets
Autorzy: Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk
Prelegent: Michał Włodarczyk
Czas i miejsce: wtorek, 12-go czerwca 2018, 10:15, sala 310.

Streszczenie:

W problemie H-Vertex Deletion staramy się usunąć z wejściowego grafu G jak najmniejszy podzbiór wierzchołków X, taki że G \ X należy do klasy H. Analogicznie definiujemy problem H-Edge Deletion. Tematem referatu będą algorytmy aproksymacyjne dla przypadku, gdy klasa H ma ograniczoną szerokość drzewiastą. Ich istotnym budulcem są niedawne wyniki dla problemu k-Subset Separator.

Zastosowanie nowej maszynerii do problemów takich jak k-Treewidth Deletion czy Planar-F-Deletion implikuje istotną poprawę współczynników aproksymacji, zaś dla kilku innych poprawia złożoność obliczeniową. W przeciwieństwie do wcześniejszych rezultatów w tej dziedzinie, nowe techniki są konstruktywne i prowadzą do jednostajnych algorytmów względem naturalnej parametryzacji.

(praca zgłoszona)