众所周知，许多NP-完全问题可以通过简单的穷举算法来解决。然而，到目前为止，一些NP-完全问题的最佳算法仍是这种简单的穷举搜索算法，即使尝试各种精巧的算法设计技术，它们的运行时间仍未能得到改进。例如，布尔可满足性问题 (Boolean satisfiability problem，SAT)，目前最好的算法仍是穷举搜索算法，其运行时间为2^n l^O(1)时间内解决，其中n是变量的数量，l是输入的大小。在强指数时间假设 (strong exponential time hypothesis，SETH) 假设下，对任意常数ɛ> 0，SAT问题不能在O((2 - ɛ̝)^n)时间内求解。另一个例子是旅行商问题 (travelling salesman problem，TSP)，在20世纪60年代已经提出了运行时间为O(2^n n^2)的动态规划算法 (其中n为图中的顶点数)，但过去50多年内的大量研究一直未能打破2^n的时间复杂度瓶颈。求解此类问题的时间复杂度能否打破2^n是一个具有挑战性的问题。
另外一些基础的NP-完全问题精确算法的运行时间长期以来也不断地得到改进，如最小支配集问题 (dominating set problem) 、最小多路割问题 (multiway cut problem) 、最小反馈集问题 (feedback vertex set problem) 、最小子集反馈集问题 (subset feedback vertex set problem) 等等。特别是最大独立集问题 (maximum independent set problem) ，它是精确算法领域中最为重要的图算法问题之一，其运行时间上界被大量学者深入研究，在经过30多年的积累下该运行时间上界成功打破了O(1.2^n)，目前最好的运行时间上界为O(1.1996^n)。在这个时间复杂度下，许多不太大的实例已经能够在短时间内进行求解。这些运行时间上界是否能继续改进的意义不仅在于解决该问题本身，更在于更好地认识NP-完全问题的计算复杂性。
本文聚焦于两类超图上独立集问题的精确算法，它们分别是超图上最大独立集问题（maximum independent set problem on hypergraphs，MISH）和超图上带惩罚的最大独立集问题（prize-collecting maximum independent set problem on hypergraphs，PC-MISH）。
在图论中，超图 (hypergraph) 是图的一种推广，其中的超边可以包含任意数量的顶点。相比之下，一般的无向图中的一条边恰好包含两个顶点。在超图上，超边数量m可以是顶点数n的指数量级，因此参数l = n + m更多地被用于表征超图的规模。下图为一个超图的示例图，其中的顶点为v1, v2,…,v7，超边为e1, e2, e3, e4。
给定一个超图，MISH问题旨在寻找图中最大的独立集，其中，超图中的独立集是一些两两不包含在同一超边的顶点构成的点子集。下图红色顶点构成了一个最大独立集。
在MISH问题中，所求的集合必需为独立集 (即满足所有超边上独立性的约束)，这一要求在许多场合过于严格。一个自然的松弛方式是: 可以通过花费一定的惩罚代价获得一个违背少量超边上独立性约束但是更大的点集。因此, PC-MISH问题应运而生。PC-MISH问题是MISH问题的松弛化推广。PC-MISH问题的目标仍然寻找一个点集X，但是它允许突破“独立”的性质，也就是说，允许超边包含X中的多个顶点。这个集合X的价值定义为X的大小减去包含至少两个X中的顶点的超边数量。而PC-MISH问题旨在找到一个价值最大的点集。下图红色顶点构成了一个价值最大顶点集。
本文分别对MISH问题和PC-MISH问题的精确算法进行研究, 主要考虑以n和l为参数的精确算法, 其中l = n + m为超图的点数与超边数之和。值得强调的是，PC-MISH问题尚未存在比穷举搜索要好的算法。
本文为MISH问题设计了多项式空间且时间复杂度为1.1996^n l^O(1)和O(1.1520^l)的精确算法，改进了前人指数空间且运行时间上界为O(1.1550^l)的算法结果。此外，本文为PC-MISH问题设计了多项式空间且时间复杂度为1.9484^n l^O(1)和O(1.3960^l)的精确算法，改进了前人运行时间上界为O(1.5^l)的算法结果。值得强调的是，本文提出的以顶点数n为参数的精确算法成功突破了2^n的时间复杂度上界。
