Parameterized Algorithms On Digraph and Constraint Satisfaction Problems

Abstract

While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit $O(c^k \cdot poly(n))$-time algorithms such as {\sc Vertex Cover}, and problems like {\sc Dominating Set} for which essentially brute-force $O(n^k)$-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves ({\sc Directed Maximum Leaf}, {\sc Directed Minimum Leaf} problems). For acyclic digraphs, {\sc Directed Maximum Leaf} is shown to allow a kernel with linear number of vertices. We suggest a kernel for {\sc Directed Minimum Leaf} with quadratic number of vertices. An improved fpt-algorithm for finding {\sc $k$-Out-Tree} is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for {\sc Directed Minimum Leaf}. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization ``above tight lower bound'' for these problems. To deal with this type of parameterization, we present a new method called {\sc SABEM} using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using {\sc SABEM} we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to {\sc Max-2-Sat} and a wide special class of {\sc Max-Lin2}, which lead to a kernel of smaller size than what can be obtained using {\sc SABEM} for respective problems.