Abstract
While polynomialtime 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 bruteforce $O(n^k)$algorithms are best possible until now. Problems of the former type is said to be fixedparameter 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 fixedparameter 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 fptalgorthms are presented for finding an outbranching 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 fptalgorithm for finding {\sc $k$OutTree} 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 pseudoboolean functions. Using {\sc SABEM} we show that a number of CSPs admit polynomial kernels, thus being fixedparameter tractable. Moreover, we suggest some problemspecific combinatorial approaches to {\sc Max2Sat} and a wide special class of {\sc MaxLin2}, which lead to a kernel of smaller size than what can be obtained using {\sc SABEM} for respective problems.
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 bruteforce $O(n^k)$algorithms are best possible until now. Problems of the former type is said to be fixedparameter 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 fixedparameter 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 fptalgorthms are presented for finding an outbranching 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 fptalgorithm for finding {\sc $k$OutTree} 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 pseudoboolean functions. Using {\sc SABEM} we show that a number of CSPs admit polynomial kernels, thus being fixedparameter tractable. Moreover, we suggest some problemspecific combinatorial approaches to {\sc Max2Sat} and a wide special class of {\sc MaxLin2}, which lead to a kernel of smaller size than what can be obtained using {\sc SABEM} for respective problems.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Award date  1 Aug 2013 
Publication status  Unpublished  2010 
Keywords
 FixedParameter Tractability
 Algorithm
 Graph Theory
 Constraint Satisfaction Problems
 Computational complexity