Domination问题是组合学中最具有代表性的一类判定问题,一般可分为：支配集问题,强支配集问题,独立支配集问题和联通支配集问题等。其中研究最多的是支配集问题。它和集合覆盖问题是等价的,是Karp于1972年提出的21个经典NP-完全问题之一[80]。Domination问题在计算机网络、计算生物学以及社会计算等方面都有实际应用。因此研究Domination问题具有极其重要的意义。本文主要从复杂性和算法两个方面,深入研究Domination问题。在经典复杂性框架下,我们分别证明在界度图、正则图和稀疏图中最小支配集问题、最小强支配集问题和最小独立支配集问题都是NP-完全的。在参数复杂性框架下,我们证明在界度图、正则图中,最小支配集问题、最小强支配集问题和最小独立支配集问题都是属于FPT。此外我们还证明在稀疏图中,这三个问题属于W[2]-hard,与一般图中的性质一样。在近似算法方面,我们主要研究最小强支配集。这里给出最小强支配集问题的一步贪心算法,其近似度是ln(δ？ 0.5) + 1.5。同时还给出近似度保留规约,证明在无向图和有向图中,最小强支配集问题的不可近似性质,表明本文给出近似算法的近似度与下界几乎重合。在精确算法方面,我们主要在子图类上研究支配集问题。首先我们提供了一个精确算法可以在O？(1.3759n)的时间内求解split图上的支配集问题,这个算法基于Liedloff的前期工作和在split图上找最大独立集算法。其次我们证明了对于任意的？ >； 0,当n充分大的时候,4-正则图的路宽不大于(1/3 + ？)n。基于这个组合上界,我们给出最小支配集问题在4-正则图上可以在O？(1.4422n)时间内解决。