FPT Aglorithms for NP-complete Graph Problems Parameterized by Treewidth and Tree-depth
Open Access
- Author:
- Belbasi, Mahdi
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- March 21, 2022
- Committee Members:
- Chitaranjan Das, Program Head/Chair
Martin Fürer, Chair & Dissertation Advisor
Antonio Blanca, Major Field Member
Jan Reimann, Outside Unit & Field Member
Paul Medvedev, Major Field Member - Keywords:
- Computer Science
Graph Theory
Tree Decomposition
Algorithm Design
Approximation Algorithms
Hamiltonian Cycle
Dominating Set
Algebraization - Abstract:
- % Place abstract below. \vspace{-0.3in} Many important graph problems are NP-complete. The complexity analysis relies on the worst-case scenario. However, most of the times the input has a nice ``structure'' so that we can solve the problem much faster, compared to the other inputs of the same size. In parameterized complexity, we classify the problems finer than the traditional setting. In order to do so, we define the complexity as a function of the set of the (input or output) parameters and the size of the input itself rather than as a function of the size of the input alone. Fixed-parameter tractable problems are the problems that can be solved in time $\mathcal{O}(f(k)poly(n))$, where $f(\cdot)$ is a computable function, $k$ is the parameter, and $n$ is the input size. If the parameter is fixed, then the problem becomes tractable since the dependence on $n$ is only polynomial. Many NP-complete problems are known to be FPT. This means, if the parameter is bounded, then we can solve them relatively fast, which is the case in many applications. Courcelle's metatheorem states that any graph property which can be described in the monadic second-order logic of the graphs can be decided in linear time if the treewidth (the parameter in this case) is bounded. There are three concerns that we address. First, we need to prove that the treewidth is bounded. The bad news is that the treewidth problem itself is NP-complete but FPT. Then, we have to find a tree decomposition with bounded treewidth to be able to apply dynamic programming. Finally, when we apply dynamic programming, most of the time we end up using exponential space. In this work, we solve all the above issues and start by presenting a 5-approximation algorithm solving the treewidth problem in time $\mathcal{O}(2^{8.765k}n\log n)$, which can be used in application\footnote{The current fast FPT algorithms have huge coefficient for $k$ in the exponent that makes them not applicable in practice.}. Later on we further improve this result by introducing new notion called ``leftmost separator''. The improved algorithm runs in time $\mathcal{O}(2^{6.755k}(\log k)\sqrt{k}n\log n)$. Both of our algorithms check if the treewidth is at most $k$. If not, they output the subgraph that has higher treewidth. Otherwise, they generate a tree decomposition with width at most $5k$. In the last paper on this problem, we provide an algorithm that is a 2-approximation of treewidth with the time complexity of $\mathcal{O}^*(2^{8k})n$, which is state of the art. This method is based on a method employed by Korhonen\cite{korhonen2021single}. Then, we present FPT algorithms to count the number of solutions to Minimum Dominating Set, Hamiltonian Cycle, and Travelling Salesperson which use only polynomial space rather than exponential by an approach called ``dynamic algebraization''.