Beyond the question of fixed-parameter tractability

Abstract

Multivariate complexity is a prominent field that over the last decades has developed a rich toolbox, not only to tackle seemingly intractable problems, but also to describe the boundaries of tractability in a richer and more fine-grained way. In this thesis we survey the research directions emerging after the question of fixed-parameter tractability has been settled. That is, we define and exemplify structural parameters, polynomial kernelizations, branching techniques, subexponential time algorithms and parameterized approximation algorithms. In addition, we display techniques for proving lower bounds for all of the above mentioned directions. After this, we give new results within this parameterized framework for several classic graph problems. The problems studied in this thesis can naturally be divided into two groups; graph modification problems and structural graph problems. With respect to graph modification problems, we study problems where one is to remove a small set of vertices in order to break the graph into small connected components. We also study problems where, instead of deleting vertices, we are to add and/or remove a small number of edges in order to obtain a graph that adheres to a specific set of properties. We resolve several questions in the literature with respect to modifying a graph to a threshold graph or to a chain graph. We prove that editing to such graphs is NP-hard and, under the widely believed Exponential Time Hypothesis (ETH), not solvable in 2o(√k) · nO(1) time. We also provide polynomial kernels and subexponential time parameterized algorithms running in time 2O(√k log k) + nO(1) for all three edge modification variants into both graph classes. We also consider edge modifications into H-free graphs, where H is any finite set of forbidden induced subgraphs, on bounded degree input graphs. We prove that for a fixed maximum degree Δ, both edge editing and edge deletion to H-free graphs in at most k operations, admit polynomial kernels with kO(Δ log Δ) vertices. Then, via the framework of cross-compositions we prove that there is a finite set H, such that completion to H-free graphs does not admit a polynomial kernelization algorithm on bounded degree graphs, when parameterized by the bound on the number operations k, unless NP ⊆ coNP/poly. With respect to structural graph problems, we first provide several results for bandwidth. We prove that, assuming ETH, there is no significant improvement over the classic dynamic programming algorithm by Saxe [SIAM’80]. In particular, we prove that, assuming ETH, there is no f(b)no(b) time algorithm for deciding whether the bandwidth of a graph is at most b. This result remains true when restricted to trees of pathwidth at most 2. By the same reduction, we prove that deciding whether the bandwidth of a graph is at most b, when parameterized by b, is W[1]-hard when restricted to the same set of trees. Furthermore, we provide the first approximation algorithm for computing the bandwidth of trees, where the approximation factor depends solely on b. We then extend this result to graphs of bounded treelength, a rich graph class containing among others chordal graphs and graphs of bounded hyperbolicity. We also provide a characterization of graphs of small bandwidth for the same graph classes. In particular, the most general of these results states that a graph of bounded treelength can only have high bandwidth if it has high local density or high pathwidth, or if it contains a slight modification of a bandwidth obstruction introduced by Chung and Seymour [Discrete Mathematics’89]. Finally, we provide a constant factor approximation algorithm for computing the treewidth of a graph that runs in O(ckn) time. The algorithm either provides a tree decomposition of width 5k + 4 or concludes that the treewidth of the input graph is larger than k. This algorithm improves several known results, like the one by Robertson and Seymour [JCTB’95] and Reed [STOC’92] and Amir [Algorithmica’10]. We point out that there are many important problems in the literature, for example computing a vertex cover, a dominating set or a steiner tree of a graph, that can be solved in O(ckn) time if provided a tree decomposition of width at most O(k). The algorithm presented, is the first that can provide such algorithms with a tree decomposition of sufficiently small width, without being the bottleneck of the composed algorithm: That is, an algorithm that first computes a decomposition of width O(k) and then solves the problem in O(ckn) time.