论文摘要
HITTING SET问题是组合学中的一个经典计算问题,它和集合覆盖（Set Cover）问题等价,其任务是计算有限集合S的一个基数较小的子集D使之满足和集合C的每一个元素相交非空,其中集合C是集合S的幂集的一个子集（即C（?）P（S））,集合D称为C的一个hitting set。从超图理论的角度来看HITTING SET问题,S和C分别是超图H=（S,C）的节点集合和超边集合,D是超图H的节点覆盖。如果超图H的每条超边大小都等于某个自然数d,则称H为d-一致超图,其对应的节点覆盖问题就等价于d-HITTING SET问题。在经典复杂性理论框架下,无论HITTING SET问题还是任意的d-HITTINGSET问题都是NP-完全的,其中d≥2。这意味着不存在多项式时间的确定性算法计算它们除非P=NP。然而在参数复杂性框架下,d-HITTING SET问题是固定参数易求解的,而HITTING SET问题却是W[2]-完全的。参数复杂性理论是复杂性理论中的一个新兴分支。近些年来,参数复杂性的发展非常迅速并且已经渗透到计算机科学的许多领域,它从参数化的角度研究可计算问题的复杂性：除把输入长度n作为计算耗费的考察对象外,还引入一个新的参数k,并提出了固定参数易求解的概念,从而拓宽了易求解的传统概念——多项式时间可解性。因此,这也使得复杂类的层次结构划分更加细致,问题的归约更加复杂。HITTING SET问题尤其是d-HITTING SET问题的研究在计算机理论和应用两方面都具有相当重要的意义和价值。本文在参数复杂性理论框架下系统研究了d-HITTING SET问题的固定参数化算法,并做出了如下几方面的贡献：·本文系统研究了d-HITTING SET问题的多种核化算法。文章以一般图的节点覆盖问题作为切入点,详细研究了基于约减规则、皇冠约减、线性规划和网络流技术在内的多种不同主流核化算法,并且探索了基于这些技术计算d-HITTINGSET问题的核化算法的可能性,其中d≥2。·本文分别研究了度数受限于l的、平面的和拟正则的d-一致超图上的节点覆盖问题,其中l≥3和d≥2。一方面,文章证明了这些特殊d-一致超图上的节点覆盖问题都是NP-完全的。另一方面,文章基于两个不同的规模函数,分别提出了核大小为l·k和（（d-1）·l+1）·k的核化算法计算度数受限于l的d-一致超图的节点覆盖问题。随后,文章基于计算平面图支配集问题的核化算法,提出了计算平面的3-一致超图节点覆盖问题核大小为67k的核化算法。同时,文章也证明了平面的d-一致超图节点覆盖问题无法基于类似平面的3-一致超图的技术获得核大小为O（k）的核化算法,其中d≥4。最后,文章基于线性规划技术,提出了计算拟正则的d-一致超图节点覆盖问题核大小为d·k的核化算法,其中d≥2。·本文分别研究了度数受限于l的、平面的和拟正则的d-一致超图上的节点覆盖问题的对偶问题——独立集问题,其中l≥3和d≥2。一方面,文章基于两个不同的规模函数提出了核大小分别为和的核化算法计算度数受限于l的d-一致超图的独立集问题。随后,文章借助平面的3-一致超图的强独立集问题和平面图的导出匹配问题,提出了核大小为12k的核化算法计算平面的3-一致超图的独立集问题。另一方面,文章证明了拟正则的d-一致超图的独立集问题是W[1]-完全的。·本文基于参数化对偶技术并结合计算结构特殊的d-一致超图上节点覆盖问题、独立集问题和支配集问题等若干相关问题的核化算法,分别给出了这些核化算法核大小的下界,其中d≥2。·本文全面研究了d-HITTING SET问题的搜索树算法。一方面,文章通过更加细致的算法分析进一步改进了节点覆盖问题的搜索树算法的时间复杂度。另一方面,文章在新的度量方式下重新刻了3-一致超图的节点覆盖问题,并且结合已有的启发式规则,运用拟凸规划技术系统分析了的搜索树算法,改进了前人的结果。本文从参数复杂性理论的角度系统全面地研究了d-HITTING SET问题的固定参数化算法,特别是核化算法和搜索树算法,以一般图和3-一致超图的节点覆盖问题作为研究切入点,探索且提出了相关问题核大小为O（k）的核化算法,进而结合参数化对偶理论和技术,获得了计算相关问题的核化算法下界。总而言之,本文为以后该方向上的研究发展做出了一定贡献。