若干图优化问题的参数复杂性研究

Parameterized tractability theory is a new approach to tackle NP-hard problems, which has seen wide applications in Artificial Intelligence, Operation Research, Access Control , Voting Theory and so on. In this project, we study the parameterized complexity of feedback vertex set problem and Chinese postman problem, which are two important optimization problems in graph theory. Feedback vertex set problem is an important NP-hard problem which has applications in bio-computing, operating system and artificial intelligence. The field has obtained plenty of parameterized results about feedback vertex set related problems in the past ten years. But till now, most of the researches are parameterized with the solution size, i.e. the size of the minimum feedback vertex set. There are not many results about other smaller parameterizations. Chinese postman problem is a classical routing problem, which has many NP-hard variants. There are also many open problems regarding the parameterized complexity of the Chinese postman related problems. This project intends to study the parameterized complexity of feedback vertex set and Chinese postman related problems under different kinds of structural parameters. The purpose of this research project is to establish the boundary between FPT and W[1]-hardness for these two problems in the parameter landscape, that is to find the minimum parameter which makes them fixed parameter tractable and the maximum parameter which makes them W[1]-hard.

参数复杂性理论是一种新的处理NP-困难问题的方法，被广泛应用于人工智能、运筹学、信息安全、投票理论等领域。本项目对顶点反馈集问题和中国邮递员问题这两类重要的图优化问题进行参数复杂性研究。反馈集问题是重要的NP-困难问题，在生物计算、操作系统、人工智能等领域都有重要应用。近十年来，参数复杂性领域对反馈集相关问题进行了大量研究，但是截至目前，大多数研究关注以反馈集大小为参数的参数复杂性，对于更小的参数，目前研究较少。中国邮递员问题是经典的路径优化问题，存在多种NP-困难的变形问题。对于中国邮递员相关问题的参数复杂性研究，目前也存在多个未解决问题。本项目研究在多种结构参数选择下，顶点反馈集问题和中国邮递员问题的参数复杂性。本项目的目标是确定这两类问题在参数选择下，固定参数可解与不可解的边界，也就是寻找使得这两类问题固定参数可解的最小参数和固定参数不可解的最大参数。

参数复杂性理论是求解困难离散优化问题的新工具。本项目针对图论中若干优化问题的参数复杂性展开研究。我们的主要目标是考察顶点反馈集和中国邮递员问题在不同参数选择下的固定参数可解性。对于顶点反馈集问题，我们得到 3 个方面的成果。首先我们研究了推广的顶点反馈集问题，d-quasiforest deletion, 并给出它的首个参数化算法。其次，对删除点以得到 r-pseudoforest 这个问题，我们改进了已有算法。最后，对于混合图上的顶点反馈集问题，我们以有向边的数目与解的大小作为参数，设计了参数化算法。在有向边的数目较小的情形，改进了已有的以解的大小为参数的算法。.对于中国邮递员问题，我们改进了混合图中以有向边数目为参数的固定参数算法，同时改进了 5 个相关问题的算法。我们改进了圈收缩问题的线性核算法。.我们也从其他角度研究了一些图优化问题。对满足给定树连通度的最小连通图的大小给出了紧的上界与下界。在 3-正则图上证明了关于配对控制集大小的一个猜想。对于在线 P_3 点覆盖问题给出了近似比为常数的近似算法。