Abstract: In complexity theory, dominating problem is an important problem, which has important applications in many fields such as resource allocations, electric networks and wireless ad hoc networks. The two most known dominating problems arc Vertex Dominating Set(VDS) and Edge Dominating Set(EDS) problem. People designed and analyzed exact algorithms for the two problems by dynamic programming and measure-and-conquer techniques and proposed many approximation algorithms for EDS problem by reducing the problem to Edge Cover problem. Recently, parameterized dominating problem has attached considerable attention. Planar VDS and General EDS problem has been proved to be Fixed-Parameter Tractable(FPT) problem, and many techniques such as tree decomposition and branch-search have been used in the design of FPT algorithms for them. The paper presented the classification for the two problems respectively, and gave definitions and some relative algorithms for each derivative problem. Furthermore, the Matrix Dominating Set problem and some research directions on dominating problem were also introduced.

Key words: Dominating problem, Vertex dominating set problem, Edge dominating set problem, Exact algorithm, Approximation algorithm, Parameterized algorithm