Computational complexity of combinatorial problems in hereditary graph classes

Niniejsza praca doktorska zawiera wyniki ze strukturalnej i algorytmicznej teorii grafów, ze szczególnym uwzględnieniem złożoności wybranych problemów NP-zupełnych dla grafów, gdy graf wejściowy jest ograniczona do pewnej dziedzicznej klasy grafów. Mówimy, że klasa grafów jest dziedziczna, jeśli ma naturalną własność bycia zamkniętą na operację usuwania wierzchołków, co jest równoważne byciu charakteryzowaną przez zbiór zakazanych indukowanych podgrafów. Praca koncentruje się głównie na klasach grafów zdefiniowanych przez jeden lub dwa zakazane podgrafy indukowane, określane odpowiednio jako grafy „bez H” lub „bez (H1, H2)”. Typowe podejście do problemów opisanych w pracy polega na wykorzystaniu właściwości strukturalnych danej klasy grafów, w szczególności braku określonych indukowanych podgrafów, w celu zaprojektowania bardziej efektywnych algorytmów. Pierwsza część pracy koncentruje się na indywidualnych problemach grafowych, rozważając klasy grafów, które przyczyniają się do lepszego zrozumienia danego problemu. Zaczynamy od problemu maksymalnego zbioru niezależnego (w wariancie ważonym) i jedynej możliwej kandydatury na istnienie algorytmu działającego w czasie wielomianowym wśród klas grafów bez H: gdy H jest grafem, którego każda spójna składowa jest drzewem mającym co najwyżej trzy liście. Wynik strukturalny dla grafów bez St,t,t jest przedstawiony z wykorzystaniem rozkładu zwanego tzw. extended strip decomposition, który jest dobrze przystosowany do rozwiązywania problemu maksymalnego zbioru niezależnego w tych klasach grafów. Jako zastosowanie, zaprezentowany zostaje algorytm podwykładniczy o czasie działania 2 O( √ n log n) oraz quasi-wielomianowy schemat aproksymacji o czasie działania 2 O(ε−1 log5 n) , co poprawia i upraszcza istniejące wcześniej algorytmy. Drugim problemem rozważanym w pracy jest problem 3-kolorowania. Przedstawiony zostaje algorytm wielomianowy dla grafów bez (2P4, C5). Jest to pierwsza próba rozwiązania problemu 3-kolorowania w grafach bez 2P4; oprócz trudnego przypadku grafów bez P8, grafy bez 2P4 są jedyną inną klasą grafów bez H, gdzie H ma osiem wierzchołków, dla której nie jest jeszcze znany algorytm wielomianowy. Następnie praca skupia się na problemach usuwania wierzchołków, szczególnie analizując problem redukcji grafu do dwudzielnego grafu permutacji poprzez usuwanie wierzchołków. Zasadniczym pytaniem jest, czy możliwe jest usunięcie k wierzchołków z dowolnego grafu, aby uzyskać dwudzielny graf permutacji. Ten NP-zupełny problem okazuje się mieć algorytm parametryzowany, działający w czasie O(9k · |V (G)| 9 ). Druga część pracy koncentruje się na wyznaczeniu tych klas grafów, wśród grafów bez (H1, H2), które posiadają silne właściwości strukturalne. Właściwości te mogą dawać efektywne algorytmy dla szerokiego zakresu problemów bez konieczności dostosowywania algorytmów do specyficznej klasy lub problemu. Praca skupia się na ograniczoności parametru szerokości klikowej w atomach — grafach bez separatora będącego kliką. Wiele problemów dotyczących grafów, w tym problem kolorowania oraz znajdowania maksymalnego zbioru niezależnego, mają następującą właściwość: jeśli, dla pewnej dziedzicznej klasy grafów, są one rozwiązywalne w czasie wielomianowym na atomach w tej klasie, to są one również rozwiązywalne w całej klasie. Prezentujemy przekrojowe badanie szerokości klikowej w atomach grafów bez (H1, H2) dla wszystkich możliwych par zakazanych grafów H1, H2, z wyjątkiem 18 przypadków. W szczególności, dla jednej nowej pary, (2P2, P2 + P3), pokazujemy, że szerokość klikowa w atomach jest ograniczona, podczas gdy szerokość klikowa w całej klasie jest nieograniczona. Na koniec przenosimy się do zagadnień pakowania i pokrywania. W 1981 roku Tuza wysunął hipotezę, że w grafie bez k + 1 trójkątów rozłącznych krawędziowo wystarczy usunąć co najwyżej 2k krawędzi, aby uzyskać graf bez trójkąta. Potwierdzamy tę hipotezę dla grafów progowych, a także dla grafów ko-łańcuchowych, gdzie strony mają tę samą liczbę wierzchołków podzielną przez cztery.

This dissertation thesis is based on a collection of results from structural graph theory and algorithms focusing on the complexity of certain NP-complete graph problems when the input is restricted to a hereditary graph class. A graph class is hereditary if it has the natural property of being closed under the vertex deletion operation, consequently, being characterized by a set of forbidden induced subgraphs. The thesis mainly examines graph classes defined by one or two forbidden induced subgraphs, referred to as H-free or (H1, H2)-free graphs, respectively. The common approach to problems described in the thesis involves exploiting the structural properties of a given graph class via the absence of particular induced subgraphs to design more efficient algorithms. The first part of the thesis focuses on specific graph problems, considering the graph classes that advance the overall understanding of the particular problem. It begins with the Maximum Weight Independent Set problem and the only possible candidate for polynomial time algorithm among H-free graphs: H being a graph whose each connected component is a tree with at most three leaves. A structural result for St,t,t-free graphs is presented utilizing so-called extended strip decomposition, which is well-designed for solving the Maximum Weight Independent Set problem within these graphs. As an application, a subexponential-time algorithm with running time 2 O( √ n log n) and a quasi-polynomial time approximation scheme with running time 2 O(ε−1 log5 n) are presented, improving and simplifying existing algorithms. The second problem considered in the thesis is the 3-Coloring problem. A polynomial-time algorithm for (2P4, C5)-free graphs is presented. This marks the first attempt to tackle the 3-Coloring problem in 2P4-free graphs, besides the challenging case of P8-free graphs, 2P4-free graphs are the only other H-free class, where H has eight vertices, for which a polynomial algorithm is not yet known. Next, the thesis explores vertex deletion problems, specifically focusing on the problem of vertex deletion into bipartite permutation graphs asking whether we can delete k vertices from a general graph to obtain a bipartite permutation graph. This NP-complete problem is shown to be fixed-parameter tractable with an algorithm that runs in O(9k · |V (G)| 9 ). The second part is tailored to identifying graph classes among (H1, H2)-free graphs that possess strong common structural properties. These properties can simplify a broad range of problems without the need for algorithms to be tailored to a specific class or problem. Namely, the thesis focuses on the boundedness of the clique-width in atoms—graphs without a clique cut-set. Multiple graph problems, including Coloring and Maximum Independent Set, that are polynomial-time solvable on atoms of hereditary graph class are so on the entire class. A comprehensive study of the clique-width of atoms of (H1, H2)-free graphs for all possible pairs of forbidden graphs H1, H2 is initiated, with all but 18 cases classified. A new pair, (2P2, P2 + P3), is identified where the clique-width of atoms is bounded, while the clique-width of the entire class is unbounded. Finally, the focus is shifted from algorithms to packings and hittings. In 1981, Tuza conjectured that in a graph without k + 1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The thesis confirms the conjecture for threshold graphs and additionally for co-chain graphs with sides of the same size divisible by four.