Computing Width Parameters of Graphs

Abstract

Trebredden til en graf beskriver dens likhet med trær ved hvor godt den kan dekomponeres ved hjelp av små separatorer. Den er definert som minimumsbredden av en tre-dekomponering av grafen. Når en graf er gitt sammen med en tre-dekomponering av liten bredde, kan mange problemer som generelt er NP-harde løses effektivt. Dette gir grunn for å granske problemet hvor vi er gitt en graf G, og vår oppgave er å enten beregne en tredekomponering av G med liten bredde eller å avgjøre at trebredden til G er stor. En lignende situasjon gjelder også for andre breddeparametre av grafer, spesielt rangbredden.

I denne avhandlingen introduserer vi en ny algoritmisk teknikk for å beregne breddeparametre av grafer og dekomponeringene assosiert med dem. Metoden vår er inspirert av bevis fra grafteorilitteraturen om eksistensen av slanke tredekomponeringer. Den nye teknikken gjør oss i stand til å takle flere åpne spørsmål fra litteraturen om trebredde og rangbredde. Især gir vi to nye algoritmer for å beregne trebredde, en dynamisk datastruktur for å vedlikeholde tre-dekomponeringer, og en ny algoritme for å beregne rangbredde.

Vårt første bidrag, der vi introduserer teknikken, er en 2-tilnærmingsalgoritme for trebredde med kjøretid 2^O(k) n, der k er trebredden og n er antall noder. Dette er en forbedring over tidligere arbeid, som gir en 5-tilnærming av trebredde innen samme kjøretid.

I vårt andre bidrag utvider vi teknikken vår for å eksakt beregne trebredde i 2^O(k^2) n^4 tid. Dette gir svar på et gammelt åpent spørsmål i litteraturen om hvorvidt det eksisterer en 2^o(k^3) n^O(1)-tid eksakt algoritme for trebredde.

Vårt tredje bidrag er en datastruktur for å vedlikeholde en tredekomponering av en dynamisk graf G som oppdateres ved innsetting og sletting av kanter. Datastrukturen vedlikeholder en tredekomponering med bredde på maks 6k+5, gitt et løfte om at trebredden til G er maks k. Den amortiserte oppdateringstiden er 2^(k^O(1) sqrt(\log n \log\log n)), som er subpolynomisk i n for fastliggende k. Dette gir delvis svar på et åpent spørsmål fra litteraturen.

I det fjerde bidraget av denne avhandlingen, utvider vi teknikken vår fra trebredde til rangbredde, og gir en 2-tilnærmingsalgoritme for rangbredde med kjøretid 2^(2^O(k)) n^2. Spørsmålet om hvorvidt rangbredde kunne tilnærmes i subkubisk tid i n for fastliggende k, var et annet åpent spørsmål i litteraturen.

The treewidth of a graph describes its tree-likeness by how well it can be decomposed by small separators. It is defined as the minimum width of a tree decomposition of the graph. When a graph is given together with a tree decomposition of small width, many problems that are NP-hard in general can be solved efficiently. This motivates the problem where we are given a graph G, and our task is to either compute a tree decomposition of G of small width or to determine that the treewidth of G is large. A similar situation holds also for other width parameters of graphs, in particular, the rankwidth.

In this thesis, we introduce a new algorithmic technique for computing width parameters of graphs and the decompositions associated with them. Our method is inspired by proofs about the existence of lean tree decompositions from the graph theory literature. The new technique allows us to address several open questions from the literature on treewidth and rankwidth. Specifically, we give two new algorithms for computing treewidth, a dynamic data structure for maintaining tree decompositions, and a new algorithm for computing rankwidth.

Our first contribution, where we introduce the technique, is a 2-approximation algorithm for treewidth running in time 2^O(k) n, where k is the treewidth and n the number of vertices. This improves upon a previous work about 5-approximating treewidth within the same running time.

As our second contribution, we extend our technique to compute treewidth exactly in 2^O(k^2) n^4 time. This answers a long-standing open question in the literature about whether there exists a 2^o(k^3) n^O(1) time exact algorithm for treewidth.

Our third contribution is a data structure for maintaining a tree decomposition of a dynamic graph G that is updated by edge insertions and deletions. Our data structure maintains a tree decomposition of width at most 6k+5, given a promise that the treewidth of G is at most k. The amortized update time is 2^(k^O(1) sqrt(\log n \log \log n)), which is subpolynomial in n for a fixed k. This partially answers an open question from the literature.

As the fourth contribution of this thesis, we extend our technique from treewidth to rankwidth, giving a 2^(2^O(k)) n^2 time 2-approximation algorithm for rankwidth. The question of whether rankwidth could be approximated in subcubic time in n, for a fixed k, was another open question in the literature.