并行化和空间高效的参数算法

Parameterized algorithms provide a practical approach to solving many NP-hard problems, and their time complexity has been the major focus for the theory and application of parameterized complexity. In contrast, there are many deep results concerning parallel and space complexity in classical complexity. Well-known examples include the logspace algorithm for the connectivity problem [Reingold, 2004]; the k-clique problem can be solved by AC^0 circuits of size O(n^{k/4+O(1)}) [Amano, 2010]-AC^0 can be viewed as constant-time parallel algorithms. These results give better algorithms for polynomial-time solvable problems as far as parallelism or space-efficiency is concerned. But for parameterized algorithms, similar research is still very much in its early stage. Based on some existing work, there are two main topics of this project: 1. parallel and space-efficient algorithms for some concrete parameterized problems. 2. the connection between parameterized and classical parallel and space-efficient algorithms. This work will deepen our understanding of the algorithms and complexity for those computational problems with small parameters. And in practice, it could improve the existing parameterized algorithms with new techniques and theory concerning parallelism and space-efficiency.

参数算法为解决许多NP难问题提供了切实可行的手段，而其时间复杂性一直是研究和应用的重点。在经典算法复杂性中，并行化和空间高效的算法研究也取得了很多深刻的结果。重要的例子包括无向图联通性的对数空间算法[Reingold, 2004]；k-团问题在平均意义下能被大小为n^{k/4+O(1)}的AC^0电路判定[Amano, 2010]-这里AC^0电路可以被视为常数时间的并行算法。这些结果对处理多项式时间可解问题给出了在空间和并行化度量下更高效的算法。相比而言，参数算法在这些方面的研究还比较初步。基于一些已有工作，我们计划考察两个主要课题：1. 具体问题的并行化及空间高效的参数算法。2. 并行和空间参数算法复杂性与经典算法复杂性之间的关系。该项研究将加深我们对参数较小的情况下各种计算问题的并行及空间参数算法复杂性的理解；同时也为实际应用中已有参数算法效率的提高提供新的技术手段和理论基础。

参数算法为解决很多NP难问题提供了切实可行的手段，但前人的研究主要聚焦于参数算法的时间复杂性。本项目考察参数算法的并行和空间复杂性，利用最新的图论和逻辑工具设计高度并行化和空间高效的算法。我们主要研究了通过逻辑语言定义的NP难问题的相关算法。由于一阶逻辑FO对应了常数时间多项式处理器计算模型上的并行算法，我们研究了关于它在图上表达能力的一些重要问题，特别是FO与所谓禁止导出子图之间的关联。最后我们也进入了图论算法领域一个较为崭新的方向，研究了所谓同态计数的表达能力和算法复杂性。我们在以下几个问题上取得重要进展。..1. 我们证明了在所谓shrub-depth有界图上所有能由MSO（monadic second-order logic）逻辑定义的NP难问题都存在常数时间的大规模并行算法。作为这个并行算法的核心，我们给出了shrub-depth的一阶逻辑刻画。该刻画为我们理解更一般的稠密图提供了新的结构图论和逻辑工具。..2. 我们使用模型论中的Los-Tarski定理给出了几个图类（即图性质）的禁止导出子图刻画，由此得到了判定这些图性质的小常数时间并行算法。另一方面，我们也证明了Los-Tarski定理在有限图上不成立，解决了有限模型论中一个公开多年的问题。..3. Lovasz证明了每个图G都能由所有同态计数hom(F, G)（即由任意图F至G的同态个数）构成的无穷向量唯一确定。由于其在人工智能、算法和逻辑中的应用，人们最近开始将这个无穷向量限制在一些图类K上（即上述的图F取自K），研究得到的子向量的复杂性和表达能力。我们给出了在一些自然图类上，判定相应子向量相等性的复杂性，以及当K为有限图类时的子向量的表达能力。