Parameterized Algorithms For Hard Problems With Tree Decomposition

NP-hard problems are the main area in theoretical computer science. Work on the fixed parameter tractable algorithms for them has become a new research topic in theoretical computer science in recent years. Parameterized computation technique is a new effective method to solve hard problems, which has been successfully applied to many actual fields till now. In this thesis, we study several classical NP-hard problems in sociology and bioinformatics, such as Signed Domination, Minus Domination, Alliance and Sequence Alignment. By abstracting and for-mulating these problems in parameterized way, we start a series of studies based on tree decomposition and employing the techniques in parameter-ized computation, such as kernelization, branch-and-search, dynamic programming, and so on.In this thesis, we firstly prove that the parameterized version of signed domination problem in sociology is NP-Complete, even the graph is restricted to bipartite or chordal. Then we derive the kernels for signed dominating set problem on general graphs, planar graphs, bipartite graphs, bounded degree graphs, regular graphs and grid graphs. The kernelization is based on the observation that either the vertex is in the signed dominating set, or is adjacent to at least two vertices of the signed dominating set. Kernels of those graphs yield the lower bounds of the minimum weight of signed dominating function on these graphs quickly because of the linear equation between the size of signed dominating set and the weight of the signed dominating function. The lower bounds we derived are tight. On the basis of the vertex state analysis, we also pre-sent a fixed parameter algorithm of running time O((4k)2t mn) for the pa-rameterized signed dominating set problem on bounded treewidth graphs, where t is the treewidth of the graph, this result also implies the subex-ponential-time algorithm of running time O(2°(?)klogk)n2) on planar graphs.In this thesis, we parameterize minus domination problem from two perspectives and study its parameterized complexity, respectively. If we take the weight of minus dominating function as the parameter, we prove that this parameterized problem is NP-Complete but not fixed parameter tractable. Moreover, if we parameterize the problem by the size of the minus dominating set, it can be proved that this parameterized problem is W[2]-hard through parameterized reduction from Red-Blue Dominat-ing Set problem. The subexponential-time algorithm on planar graphs is based on the bounded treewidth algorithms and bidimensionality theory. In this thesis, we also give a linear time algorithm for minus domination on interval graphs through state analysis and state transformation on the finite state automaton.We also give the parameterized algorithms and kernels for the alli-ance problem, which includes defensive alliance, offensive alliance, global defensive alliance and global offensive alliance. We propose, based on the discovery that each vertex in the defensive alliance has de-gree at most2k-1and at least half of its neighbors are in the defensive alliance, a parameterized algorithm for the defensive alliance problem of running time O(kkn) by branch-and-search technique. We also prove that defensive alliance and offensive alliance problem do not admit polyno-mial kernels by the meta theory of kernelization lower bounds. At last, we develop a parameterized algorithm for global defensive alliance and global offensive alliance problem on bounded treewidth graphs. The kernels of these two problems on general graphs and planar graphs are also presented.Sequence-structure alignment problem is a classical NP-hard prob-lem in bioinformatics. We propose a parameterized algorithm of the problem by catching the property of the biopolymers, that is many bio-polymers have small treewidth and the statistical cutoff for the corre-spondence between the residues of the sequences is also small. We show that parameterized structure-sequence alliance problem is fixed parame-ter tractable by the reduction from the maximum clique problem on bounded treewidth graphs. On the basis of the study above, we develop a parameterized algorithm of running time O(k’N2) with dynamic pro-gramming, where N is the length of the target sequence, k is the width of residue mapping and t is the treewidth of the structure sequence.The results in this thesis provide a reference for solving NP-hard problems in sociology and bioinformatics, and also give an effective way of the application of the tree decomposition technique.