圈结构及其算法研究

Cycles are the oldest and one of the most important structures in graphs. Algorithmic problems on cycles have always been pivotal in the area of algorithmic graph theory, and their development is heavily based on our combinatorial understanding of cycles. The first purpose of our focused study is the feedback vertex set problems, both on directed and undirected graphs, which are both long known NP-hard. We propose to design more efficient parameterized algorithms for them. On the other hand, the perfect graph theory is built on a special type of cycles, namely, induced cycles that are not triangles, which are also known as holes. A graph containing no holes is called chordal. The second problems we propose to study are modification problems to chordal graphs, that is, how to apply a minimum number of modifications to make a graph chordal. They are also well known to be NP-hard. Finally, we are interested in the detection of shortest holes and shortest even holes, which are both known to be solved in polynomial time, but only very high-order polynomial-time algorithms are currently known.

圈是图论中最古老也最重要的结构之一，围绕它的算法问题一直是图算法领域的核心课题之一，而这些算法都依赖于对圈的组合理解。我们第一个重点关注的问题是顶点反馈集问题，这个问题在有向图和无向图中都是NP难的。我们计划提出更有效的固定参数算法。完美图理论及其它各种应用中关注一种特殊的圈，就是三角形之外其它导出子圈（induced cycles），又叫做洞。没有洞的图叫做弦图。我们的另一个关注点就是弦图的修改问题，也就是说，如果通过最少的修改将一个给定图变成弦图。这个也是NP难的。此外，我们还将研究多项式时间可解的最短洞检测和最短偶长度洞的检测。

在本基金的支持下，课题组对圈结果和其算法应用进行了深入的研究，并且取得了很大进展。在无圈图有关的算法设计方面，通过对森林和树结构的深入分析，我们用最简单的贪心和局部搜索方法，得到了一系列突破性的结果，包括顶点反馈集、最大内部节点生成子树。我们对无洞图，也就是著名的弦图上解决了若干著名的开放问题，包括区间图的图修改问题、单位区间图的图修改问题、弦图子类之间的点删除问题，以及稀疏矩阵运算中著名的最小填充问题。我们还在有关的问题上得到了一系列的核心化结果，这些成果在国际上有很大的影响。..此外，此项目的研究对图算法未来的发展起到了推动作用。