NP-Complete Problems and Special Bipartite Graphs

NP完全问题是计算机科学理论的核心概念之一，对于理论研究和实际应用都有重要意义。大量的NP完全问题中有很多有实际应用但目前还缺乏多项式时间算法的计算问题，如最小顶点反馈集、最小联通支配集、最小独立支配集、哈密顿回路与通路等。这几个重要的计算问题在一般二部图上是NP完全的，在凸二部图上有多项式时间算法。二部图是重要的图类，不仅可用来为实际问题建模，还可获得在一般图上难以获得的结论，其内部包含丰富的结构，可定义各种特殊的二部图，如凸二部图、环凸二部图、树凸二部图、弦二部图等。近年来，报告人和合作者许可教授以及学生们把凸二部图扩充到树凸二部图，并对相关的树施加不同限制，分别得到星凸二部图、三岔凸二部图等，在这些特殊的二部图上研究上述NP完全问题的算法和复杂度，确定对哪些图类有多项式时间算法及对哪些图类是NP完全的。下一步，将对这些特殊的图类开展组合刻画、随机图、近似算法、参数算法、指数算法等方面的研究，目的是理解这些特殊二部图的数学结构对上述有重要应用的NP完全问题的算法设计的影响，为实际应用打下坚实的理论基础。本报告将从NP完全问题的基础知识讲起，回顾各种对付NP完全性的方法和理论成果，重点介绍报告人和合作者过去几年在特殊二部图上取得的结果，并展望未来几年可能的研究方向和研究问题。