2008

Ph.D

HBNI

The class of NP-hard combinatorial optimization problems, need to be solved exactly for various applications in theory and practice, brings the need for exact algorithms. Parameterized complexity is an exact algorithmic approach to deal with intractable computational problems having some small parameters. This thesis considers various problems from the exact algorithm paradigm for both parameterized and optimization versions of the problems. The first part of the thesis consists of FPT algorithms for various graph problems and the other part consists of exact algorithms for optimization versions of a few graph problems. It is shown that several problems like dominating set, independent set that are hard for various 'parameterized complexity classes', on general graphs, become fixed parameter tractable on graphs with no small cycles. An FPT algorithm is given for the Directed Maximum Leaf out-Tree problem, which is the problem of finding a directed out-tree, with at least k leaves in directed graphs. Finally W[1]-hardness results is given for variations of coloring problems like LIST coloring and Equitable coloring when parameterized by the treewidth of the input graph. Three techniques are introduced in the second part of the thesis, to design non-trivial exact algorithms and are illustrated with several examples. The first technique obtains a non-trivial exact algorithm for optimization versions of various problems using parameterized algorithms for the same problems. The second technique illustrates the idea of designing exact algorithms by enumerating maximal independent sets (MIS) in a graph. This technique is exemplified by designing the currently fastest polynomial space exact algorithms for ODD Cycle transversal, Minimum maximal matching, Minimum edge dominating Set and Matrix Dominating Set. The last technique is based on different combinations of Branch & Reduce and dynamic programming on graphs of bounded treewidth. It is illustrated by giving the fastest known algorithms for a number of NP hard problems including minimal maximal matching and its variations and counting the number of 3-colorings of a graph. The exact algorithms given for optimization versions of Maximum r-Regular induced subgraph problems. An O(c^n) time algorithms for these problems for any fixed constant r, where c is a positive constant, strictly less than 2, depending on r alone.