Algorithm And Complexity For Domination

Domination problem is one of the most representative decision problem, generally hassome variants: dominating set problem, total dominating set problem, independent dominat-ing set problem, connected dominating set problem and so on. In addition, dominating setproblem is equivalent to set cover problem, which is one of 21 classic NP-complete problemsproved by Karp in 1972 [80]. Moreover, lots of domination problems are applied in computernetwork, computational biology and social computing. In this thesis, we mainly study thedomination problem in the complexity and algorithm aspects.In the framework of classical complexity, we prove minimum dominating set problem,minimum total dominating set problem and minimum independent dominating set problemare NP-complete in bounded degree graph, regular graph and sparse graph. In the frameworkof the parameterized complexity, we prove the minimum dominating set problem, minimumtotal dominating set problem and minimum total dominating set problem belong to FPT inbounded degree graph and regular graph. Moreover, above three problems belong to W[2]-hard in sparse graph, as in general graph.In the aspect of approximation algorithm, we mainly study the minimum total domi-nating set problem. Here we provide one step greedy algorithm for this problem, with itsapproximation ratio ln(δ? 0.5) + 1.5. At the same time, we give gap preserve reduction,prove the approximation's lower bound for minimum total dominating set problem in theundirected graph and directed graph, which show that the approximation ratio of this greedyalgorithm is almost coincidence with its lower bound.In the aspect of exact algorithm, we mainly study minimum dominating set problem insome graph classes. First, we provide an exact algorithm to solve minimum dominating setproblem on split graphs in time O?(1.3759n). This algorithm is based on the result of findinga maximum independent set on split graphs and Liedloff's previous work. Second, we provethat for any ? > 0, the pathwidth of 4-regular graph on n vertices is at most (1/3 + ?)n,when n is sufficiently large. Based on this bound we show that the minimum dominating setproblem on 4-regular graph is solvable in time O?(1.4422n).