参数复杂性在算法图论上的一些应用

参数复杂性是算法复杂性理论的一个较新的分支。相对于经典理论，它主要处理二维计算问题，即问题的输入中有一部分较小的参数。参数复杂性理论的核心是固定参数算法，它允许算法的运行时间超过多项式，只要非多项式时间的行为是被局限在小参数上的。由于许多NP难的算法图论问题都是二维问题，即问题实例中包含较小的参数，因此固定参数算法为解决这些困难的计算问题提供了一个新的手段。近些年来，结构图论的重大突破和逻辑方法的广泛应用也使得固定参数算法和复杂性有了长足的发展。基于已有的工作我们的研究将集中于以下几个方面：1.通过发展有向图的结构理论和对应的逻辑理论，研究有向图上模型验证问题的参数复杂性和固定参数算法。2.子图同构问题的复杂性，尝试给出其完备的可解性刻画。同时研究其各变种的复杂性。3.各种图论问题的内核算法及其复杂性下界，以及其一般的逻辑刻画。

参数复杂性是算法复杂性理论的一个较新的分支。相对于经典理论，它主要处理二维计算问题，即问题的输入中有一部分较小的参数。参数复杂性理论的核心是固定参数算法，它允许算法的运行时间超过多项式，只要非多项式时间的行为是被局限在小参数上的。由于许多NP难的算法图论问题都是二维问题，因此固定参数算法为解决这些困难的计算问题提供了一个新的手段。本项目主要研究参数算法在图论问题上的应用及其相关的复杂性理论。经过三年的工作，我们在以下一些方面取得重要结果：1. 我们给出了k-边导出子图问题的参数算法，解决了蔡雷震于2004年提出的一个公开问题。我们的算法使用了许多深刻的数学工具，包括数论、组合和逻辑。2. 我们研究了团问题的参数可近似性。在著名的指数时间复杂性假设(ETH)下，我们证明了参数团问题不存在一类特定的参数近似算法。3. 作为相应的复杂性理论，我们发现了一个有限模型论、参数复杂性和证明复杂性间的一个令人吃惊的联系。