Algorithm Research On Generalized Problems Of The Minimum Dominating Set Problem On Several Special Graphs

The minimum dominating set problem requires finding a subset of vertices in a given graph with smallest cardinality such that any vertex in the graph either belongs to that subset or is adjacent to a vertex in that subset.This classical combinatorial optimization problem is NP-hard,even when restricting the graph class structure to bipartite graphs or split graphs.At the same time,the problem is of great theoretical and practical importance due to its wide range of applications,the study of this problem and related extensions has been a hot topic and a difficult problem in academia and industry,receiving much attention.In this dissertation,some generalizations of the problem are investigated from the perspective of algorithms and complexity,and useful structural and algorithmic con-clusions are sought.A natural generalization is to require only“partial dominating”.Then,the vertices that are not“dominated”will pay the cost.For this purpose,we assign weights and penalties to each vertex in a given graph.The problem is to find a subset of vertices such that the weight is as small as possible under certain constraints(e.g.,prize-collecting version,or setting an upper bound that allows some vertices to be uncontrolled).In this dissertation,some polynomial-time algorithms and approxi-mation algorithms for the generalization problem on special graphs are obtained and analyzed for complexity.The hat game,a puzzle about three people,has been extended to n people and has had a profound impact on many fields such as mathematics,statistics and computer science.In this dissertation,we discuss several combinatorial properties between dom-inating set and hat game with the help of the concept of dominating sets and around the problem of finding the minimum dominating set in a special bipartite graph struc-ture,the hypercube.In particular,we give a solution for the optimal strategy of the hat game under the special conditions of n,and establish a graph theoretic solution that is different from the coding solution,with the help of the concept of dominating set.Further,in this dissertation,a polynomial-time algorithm on star graphs is ob-tained for the prize-collecting dominating set problem,and it is extended to complete split graphs.The 2-LMP algorithm for the prize-collecting dominating set problem is given by using r as a factor of Lagrange multiplier preserving;and an approximation algorithm with(8/3+4ε)for the partial dominating set problem is given by implying the2-LMP algorithm.For the special structure of the bipartite graph,the relationship be-tween the partial dominating set problem and the prize-collecting dominating set prob-lem is established.In addition,several combinatorial properties between dominating set and hat game are obtained.