Graph Width Parameters. Dependencies, Algorithms and Decompositions

This dissertation will be based on results from structural graph theory, mainly revolving around graph width parameters, dependencies between them, their usages and finding certifying decompositions. Specific parameters that will be of most relevance to this dissertation are treedepth, treewidth, pathwidth and mad (short for maximum average degree). In Chapter 3, based on the article ``Improved bounds for the excluded-minor approximation of treedepth'', we show that there exists a constant C such that for every positive integers a,b and a graph G, if the treedepth of G is at least Cab, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega(k^3) is either of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2^k. This improves the bound of Omega(k^5 log^2 k) of Kawarabayashi and Rossman. We also show an application of our techniques for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width O(kt log^{3/2} t). This improves upon a bound of O(kt^2 \log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d log_3 ((1+sqrt{5})/2). In Chapter 4, based on article ``Efficient fully dynamic elimination forests with applications to detecting long paths and cycles'', we show that every minimal graph of treedepth d has at most d^O(d) vertices, improving upon work of Dvorak et al. In Chapter 5, based on the article ``Computing treedepth in polynomial space and linear fpt time'', we propose an algorithm that given a graph G and an integer d, either finds a treedepth decompositon of G of depth at most d or concludes that no such decomposition exists; thus the algorithm decides whether the treedepth of G is at most d. The running time is 2^O(d^2) n^O(1) and the space usage is polynomial in n. Further, by allowing randomization, the time and space complexities can be improved to 2^O(d^2) n and d^O(1) n, respectively. This improves upon the algorithm of Reidl et al., which also has time complexity 2^O(d^2) n, but uses space exponential in d. In Chapter 6, based on the article ``Approximating Pathwidth for Graphs of Small Treewidth'', we prove that every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Omega(k^c) has treewidth at least k or contains a subdivision of a complete binary tree of height k. These structural insights allowed us to design a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t sqrt{log t}), which is described in the original article, but not in this thesis. This is the first algorithm to achieve an f(t)-approximation for some function f. The maximum average degree mad(G) of a graphis the maximum over all subgraphs of G, of the average degree of the subgraph. In Chapter 7, based on the article ``Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph'', we prove that for every G and positive integer k such that mad(G) <= k there exists S \subseteq V(G) such that mad(G - S) <= mad(G) - k and G[S] is (k-1)-degenerate. Moreover, such $S$ can be computed in polynomial time.