Praca doktorska
Licencja
Korzystanie z tego materiału możliwe jest zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa. Korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.Efficient data structures and graph width parameters
| dc.abstract.en | This dissertation presents several contributions in structural graph theory: the study of combinatorial properties of various classes of graphs and algorithmic applications of these properties. We focus on families of graphs characterized by graph width parameters: integer values measuring how efficiently a graph can be decomposed into simpler pieces following a set of prescribed rules. We present research related to three such width parameters – treewidth, rankwidth, and twin-width. We show evidence that it is possible to construct efficient data structures for classes of graphs with bounded values of these parameters, enabling us to answer a variety of queries about the input graphs, as well as apply certain types of updates to the graphs. First, we show the results of the article “Dynamic treewidth” [Korhonen, Majewski, Nadara, Pilipczuk, Sokołowski; FOCS 2023]. We prove that given a dynamic n-vertex graph of small treewidth k undergoing edge insertions and removals in the fully dynamic model, we can main tain a tree decomposition of the graph witnessing at each point of time that the graph has treewidth at most 6k + 5. A single update is processed by our data structure in subpolynomial amortized time Ok(2 √ log n log log n ); here, the Ok(·) notation hides factors depending only on k. Next, we show that most dynamic programming schemes applicable to tree decompositions in the usual static setting can also be maintained dynamically within the same time bounds. As an application, we show a dynamic variant of the classic Courcelle’s theorem [Inf Comput.; 1990]: The satisfaction of a fixed property of graphs expressible in the monadic second-order logic with edge subset quantification (CMSO2) can be tracked in dynamic graphs of treewidth at most k, also within the same time complexity bounds. In the next chapter, based on the work “Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth” [Korhonen, Sokołowski; 2024], we generalize the dynamic treewidth data structure to a much more general graph parameter, rankwidth. For a dynamic n-vertex graph updated by edge deletions and additions whose rankwidth is at most k at all times, we maintain a rank decomposition of the graph of width at most 4k, again in amortized time Ok(2 √ log n log log n ). Since rankwidth generalizes the notion of treewidth to the setting of dense graphs, we also introduce a framework of dense updates to the graph, allowing us to redefine the adjacencies using a formula of monadic second-order logic within any chosen t-vertex subgraph of the maintained graph in time almost linear in t rather than t 2 . As a consequence, we give an algorithm that for an n-vertex, m-edge graph and an integer k, in time Ok(n 1+o(1)) + O(m) either produces a rank decomposition of the graph of width at most k, or correctly determines that the rankwidth of the graph exceeds k. In the positive case, our algorithm can also return a graph expression witnessing that the cliquewidth of the graph is at most 2k+1 − 1. This improves upon a previous result of Fomin and Korhonen, who achieved Ok(n 2 ) time algorithm for the problem. Moreover, given a fixed property of graphs encoded in the monadic second-order logic without edge subset quantification (CMSO1), we can verify whether the property holds in a graph of rankwidth at most k within the same time bounds. The following chapter is based on the results from the work “Fully dynamic approximation schemes on planar and apex-minor-free graphs” [Korhonen, Nadara, Pilipczuk, Sokołowski; SODA 2024] and presents dynamic counterparts of the classic approximation schemes for Maximum Weighted Independent Set and Minimum Weighted Dominating Set in planar graphs, described in the static setting by Baker [J. ACM; 1994]. For a fully dynamic vertex-weighted planar graph G, updated by edge insertions and removals, as well as weight modifications, and a fixed real value ε > 0, we maintain the following summaries of the graph: • a (1−ε)-approximation of the maximum weight of an independent set in time Oε(n o(1)), and • a (1 + ε)-approximation of the minimum weight of a dominating set in time Oε,∆(n o(1)) under the additional assumption that at all times, all vertices of the graph have degrees bounded by ∆. The techniques heavily rely on the structural properties of graphs of bounded treewidth. The same techniques are also applicable to arbitrary classes of graphs excluding a fixed apex graph as a minor – such as the class of toroidal graphs or any class of graphs embeddable in a fixed surface – so the algorithmic results above lift also to these classes. Next, we display the findings from our work “Compact representation for matrices of bounded twin-width” [Pilipczuk, Sokołowski, Zych Pawlewicz; STACS 2022]. Namely, we pro pose a data structure that stores a static binary d-twin-ordered n × n matrix and can be queried for its entries. The data structure requires Od(n) bits of space – which is asymptoti cally optimal due to a result of Bonnet et al. [STOC 2022] – and can answer every query in worst-case O(log log n) time. Finally we present our work “Graphs of bounded twin-width are quasi-polynomially χ bounded” [Pilipczuk, Sokołowski; J. Comb. Theory, Ser. B; 2023], where we prove that, for every integer d, there exists a quasi-polynomial function fd(ω) ∈ 2 O(log4d+3 ω) such that every graph of twin-width at most d and maximum clique size ω can be properly colored using at most fd(ω) colors. This comes close to a positive resolution of a conjecture of Bonnet et al. [ICALP 2021], claiming that graphs of bounded twin-width are polynomially χ-bounded. |
| dc.abstract.pl | W niniejszej rozprawie prezentujemy wyniki badań nad strukturalną teorią grafów: dzie dziną nauki analizującą właściwości różnych klas grafów oraz algorytmiczne zastosowania tych własności. Skupiamy się na klasach grafów, które scharakteryzowane są parametrami szero kości grafów: całkowitoliczbowymi wartościami mierzącymi, jak efektywnie dany graf można rozłożyć na prostsze części zgodnie z zadanym zbiorem reguł. Prezentujemy wyniki badań do tyczących trzech parametrów tego typu: szerokości drzewiastej (treewidth), szerokości rzędowej (rankwidth) oraz szerokości bliźniaczej (twin-width). Pokazujemy, że jesteśmy w stanie tworzyć wydajne struktury danych dla klas grafów o ograniczonych wartościach tych parametrów. Takie struktury danych pozwalają na efektywne odpowiadanie na zapytania dotyczące zróżnicowa nych własności grafów wejściowych, jak również na aplikowanie różnych typów przekształceń tych grafów. Najpierw prezentujemy wyniki pochodzące z artykułu „Dynamic treewidth” [Korhonen, Majewski, Nadara, Pilipczuk, Sokołowski; FOCS 2023]. Wykazujemy, że dla dowolnego n wierzchołkowego grafu o małej szerokości drzewiastej k, aktualizowanego w pełni dynamicznie poprzez dodawanie i usuwanie krawędzi, możemy utrzymywać dekompozycję drzewiastą grafu świadczącą o tym, że szerokość drzewiasta grafu nie przekracza 6k + 5. Pojedyncza aktualizacja grafu jest przetwarzana przez naszą strukturę danych w podwielomianowym czasie zamortyzo wanym Ok(2 √ log n log log n ); notacja Ok(·) ukrywa czynniki zależne jedynie od k. Pokazujemy również, że większość schematów programowania dynamicznego na dekompozycjach drzewia stych, zaprojektowanych dla statycznych grafów, można utrzymywać również w dynamicznych grafach – w tej samej, podwielomianowej złożoności czasowej. Zastosowaniem tego wyniku jest dynamiczna wersja klasycznego twierdzenia Courcelle’a [Inf Comput.; 1990]: w tej samej złożo ności czasowej, nasza struktura danych może utrzymywać w dynamicznym grafie o szerokości drzewiastej nieprzekraczającej k informację o tym, czy graf spełnia dowolną ustaloną własność grafów wyrażoną w języku monadycznej logiki drugiego rzędu z kwantyfikacją po podzbiorach wierzchołków (CMSO2). W następnym rozdziale, bazującym na pracy „Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth” [Korhonen, Sokołowski; 2024], opisujemy podobną struk turę danych dla znacznie ogólniejszego parametru grafowego – szerokości rzędowej. Dla dyna micznego n-wierzchołkowego grafu o szerokości rzędowej co najwyżej k, aktualizowanego poprzez usuwanie i dodawanie krawędzi, utrzymujemy dekompozycję rzędową o szerokości co najwyżej 4k, ponownie w zamortyzowanym czasie Ok(2 √ log n log log n ). Ponieważ szerokość rzędowa jest uogólnieniem szerokości drzewiastej do grafów gęstych, wprowadzamy model gęstych aktualiza cji grafu, pozwalający na przedefiniowanie sąsiedztw w dowolnym wybranym t-wierzchołkowym podgrafie utrzymywanego grafu za pomocą formuł monadycznej logiki drugiego rzędu w czasie zależnym prawie liniowo od t zamiast t 2 . Wykorzystując powyższe wyniki, prezentujemy algorytm, który wczytuje graf mający n wierz chołków i m krawędzi oraz liczbę naturalną k i który w złożoności czasowej Ok(n 1+o(1))+O(m) konstruuje dekompozycję rzędową grafu o szerokości co najwyżej k lub poprawnie stwierdza, że szerokość rzędowa grafu jest ściśle większa niż k. W pozytywnym przypadku nasz algorytm zwraca również wyrażenie grafowe poświadczające, że szerokość klikowa grafu jest ograniczona z góry przez 2k+1 −1. Algorytm ten poprawia poprzedni wynik Fomina oraz Korhonena, którzy zaprojektowali dla tego samego problemu algorytm w złożoności Ok(n 2 ). Ponadto, w tej samej złożoności czasowej możemy sprawdzić, czy graf spełnia ustaloną własność grafów zapisaną w monadycznej logice drugiego rzędu bez kwantyfikacji po podzbiorach krawędzi (CMSO1). Kolejny rozdział bazuje na pracy „Fully dynamic approximation schemes on planar and apex-minor-free graphs” [Korhonen, Nadara, Pilipczuk, Sokołowski; SODA 2024]. W tym roz dziale pokazujemy dynamiczne warianty klasycznych schematów aproksymacyjnych dla proble mów maksymalnego ważonego zbioru niezależnego oraz minimalnego ważonego zbioru dominu jącego w grafach planarnych, rozważanych w modelu statycznych grafów przez Baker [J. ACM; 1994]. Dokładniej, dla dowolnej ustalonej rzeczywistej wartości ε > 0, tworzymy strukturę da nych utrzymującą następujące zbiorcze informacje na temat dynamicznego grafu planarnego G z rzeczywistymi wagami wierzchołków: • (1 − ε)-aproksymację maksymalnej wagi zbioru niezależnego w G w złożoności czasowej Oε(n o(1)); oraz • (1 + ε)-aproksymację minimalnej wagi zbioru dominującego w G w złożoności czasowej Oε,∆(n o(1)) przy dodatkowym założeniu, że stopnie wszystkich wierzchołków grafu G są w każdym momencie ograniczone przez ∆. Metody używane przez nas w projektowaniu tej struktury danych wykorzystują wielorakie wła sności grafów o ograniczonej szerokości drzewiastej. Te same metody działają nie tylko dla klasy grafów planarnych, lecz również dla dowolnych klas grafów niezawierających ustalonego grafu szczytowego (apex graph) jako minora – na przykład dla klasy grafów toroidalnych czy dla do wolnej klasy grafów zanurzalnych w ustalonej powierzchni. Tak więc wymienione wyżej wyniki działają również dla tych klas grafów. Dalej pokazujemy wyniki pochodzące z pracy „Compact representation for matrices of bo unded twin-width” [Pilipczuk, Sokołowski, Zych-Pawlewicz; STACS 2022]. Dokładniej, pokazu jemy zwięzłą strukturę danych, która utrzymuje statyczną zero-jedynkową macierz n×n, która jest d-uporządkowana bliźniaczo (d-twin-ordered) i którą można odpytywać o poszczególne ele menty macierzy. Struktura danych zajmuje Od(n) bitów pamięci – asymptotycznie optymalną liczbę bitów zgodnie z wynikiem Bonneta i in. [STOC 2022] – i zwraca odpowiedź na dowolne zapytanie w czasie O(log log n). Wreszcie prezentujemy pracę „Graphs of bounded twin-width are quasi-polynomially χ bounded” [Pilipczuk, Sokołowski; J. Comb Theory, Ser. B; 2023], gdzie pokazujemy, że dla każdej liczby naturalnej d istnieje quasi-wielomianowa funkcja fd(ω) ∈ 2 O(log4d+3 ω) o następu jącej własności: każdy graf o szerokości bliźniaczej nieprzekraczającej d i rozmiarze maksymalnej kliki równej ω ma liczbę chromatyczną ograniczoną z góry poprzez fd(ω). Wynik ten jest bli ski pozytywnemu rozstrzygnięciu hipotezy Bonneta i in. [ICALP 2021] twierdzącej, że grafy o ograniczonej szerokości bliźniaczej są wielomianowo χ-ograniczone – to znaczy, funkcja fd(ω) w opisie powyżej jest wielomianowa względem ω. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.affiliation.department | Wydział Matematyki, Informatyki i Mechaniki |
| dc.affiliation.institute | Instytut Informatyki |
| dc.affiliation.other | Szkoła Doktorska Nauk Ścisłych i Przyrodniczych |
| dc.contributor.author | Sokołowski, Marek |
| dc.date.accessioned | 2025-01-30T12:57:43Z |
| dc.date.available | 2025-01-30T12:57:43Z |
| dc.date.defence | 2025-02-25 |
| dc.date.issued | 2025-01-30 |
| dc.date.submitted | 2024-05-06 |
| dc.description.promoter | Pilipczuk, Michał |
| dc.description.reviewer | Bonnet, Édouard |
| dc.description.reviewer | Byrka, Jarosław |
| dc.description.reviewer | Lokshtanov, Daniel |
| dc.description.version | final_author |
| dc.identifier.orcid | 0000-0001-8309-0141 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/166121 |
| dc.language | en |
| dc.language.other | pl |
| dc.rights | FairUse |
| dc.subject.en | data structures |
| dc.subject.en | graph width parameters |
| dc.subject.en | structural graph theory |
| dc.subject.en | parameterized complexity |
| dc.subject.en | treewidth |
| dc.subject.en | rankwidth |
| dc.subject.en | twin-width |
| dc.subject.en | chi-boundedness |
| dc.subject.pl | struktury danych |
| dc.subject.pl | parametry szerokości grafów |
| dc.subject.pl | strukturalna teoria grafów |
| dc.subject.pl | złożoność parametryzowana |
| dc.subject.pl | szerokość drzewiasta |
| dc.subject.pl | szerokość rzędowa |
| dc.subject.pl | szerokość bliźniacza |
| dc.subject.pl | chi-ograniczoność |
| dc.title | Efficient data structures and graph width parameters |
| dc.title.alternative | Wydajne struktury danych i parametry szerokości grafów |
| dc.type | DoctoralThesis |
| dspace.entity.type | Publication |