Abstract
A {\em domination problem} in graph theorem is that in given graph, we choose some vertices or edges, or assign values to vertices such that the graph can accord with the rule of the problem.In this paper, we study the algorithms and hardness for {\em Signed domination (SD) problem} and {\em Minus domination (MD) problem}.The singed domination problem is that we assign value $\{-1,+1\}$ to all vertices,the minus domination problem is that we assign value $\{-1,0,+1\}$ to all vertices,both of two problems ask that for all vertices, the sum value of the vertex and its neighbors is positive,and find the function which contribute the minimum value of total vertices.SD problem and MD problem can apply on social network,let agree comments be positive one,and disagree comments be negative one,for anyone,the sum comments of its neighbor are agree(sum value is positive),it is a simple example of signed domination problem.These two problem are studied widely in resent years,in complexity compute,we usually reduce harder problem to these two problem,to find its time complexity.In this paper, we give results as follows:On signed domination problem:(1) $W$[2]-hardness on general graphs.(2) APX-hardness on maximum degree six graphs.(3) Approximation algorithm on small degree graphs.(4) NP-completeness on split graphs.(5) NP-completeness on subcubic planar bipartite graphs.(6) FPT-algorithm on subcubic graphs.(7) NP-completeness for signed domination on degree-at-most-four-base universal-apex graphs.(8) W[2]-hardness for SD problem on universal-apex graphs.(9) APX-hardness for SD problem on degree-at-most-six-base universal-apex graphs.(10) Exact-algorithm for SD problem on degree-at-most-four-base universal-apex graphs.On minus domination problem:(1) $W$[2]-hardness on general connected graphs.(2) APX-hardness on graphs of max. degree 7.(3) Fixed-parameter algorithm on subcubic graphs.