二部图上NP完全问题的研究

Bipartite Graphs are an important class of graphs, not only of use in modelling practical problems, but also in obtaining results which are impossible for general graphs. There are a plenty of structures in bipartite graphs, and different kinds of special bipartite graphs can be defined based on these structures, such as convex bipartite graphs, circular convex bipartite graphs，tree convex bipartite graphs and chordal biaprtite graphs, etc. There are many NP-complete computational problems which have practical appliactions but have no known polynomial time algorithms, including minimum feedback vertex set, minimum connected dominating set, minimum independent dominating set, Hamiltonian circuit and path, etc. These important computational problems are NP-complete for bipartite graphs, but tractable for convex bipartite graphs. In this project, convex bipattite graphs are extended to tree convex biaprtite graphs, and by setting restrictions on the associated trees, the so-called star convex bipartite graphs, triad convex bipartite graphs and so on are defined respectively. Algorithms and complexity of these NP-complete problems for these restricted bipartite graphs will be explored, to determine for which bipartite graphs these problems are polynomial time solvable and for which bipartite graphs these problems are still NP-complete, as well as explorations on combinatorial charaterizations, random bipartie graphs, approximation algorithms, parameterized algorithms, exponential time algorithms for these bipartite graphs. The aim of this project is to understand how the mathematical structures on these special bipartite graphs will have effects on algorithm designs for these important practical NP-complete problems, and to build a solid theoretical foundation for practical applications.

二部图是重要的图类，不仅可用来为实际问题建模，还可获得在一般图上难以获得的结论，其内部包含丰富的结构，可定义各种特殊的二部图，如凸二部图、环凸二部图、树凸二部图、弦二部图等。NP完全问题中有很多有实际应用但目前还缺乏多项式时间算法的计算问题，如最小顶点反馈集、最小联通支配集、最小独立支配集、哈密顿回路与通路等。这几个重要的计算问题在一般二部图上是NP完全的，在凸二部图上有多项式时间算法。本项目把凸二部图扩充到树凸二部图，并对相关的树施加不同限制，分别得到星凸二部图、三岔凸二部图等，在这些特殊的二部图上研究上述NP完全问题的算法和复杂度，确定对哪些图类有多项式时间算法及对哪些图类是NP完全的，对这些特殊的图类开展组合刻画、随机图、近似算法、参数算法、指数算法等方面的研究，目的是理解这些特殊二部图的数学结构对上述有重要应用的NP完全问题的算法设计的影响，为实际应用打下坚实的理论基础。

二部图是重要的图类，不仅可用来为实际问题建模，还可获得在一般图上难以获得的结论，其内部包含丰富的结构，可定义各种特殊的二部图，如凸二部图、环凸二部图、树凸二部图、弦二部图等。NP完全问题中有很多有实际应用但目前还缺乏多项式时间算法的计算问题，如最小顶点反馈集、最小联通支配集、最小独立支配集、哈密顿回路与通路、树宽度、最大边偶团等。这几个重要的计算问题在一般二部图上是NP完全的，在凸二部图上有多项式时间算法。本项目把凸二部图扩充到树凸二部图，并对相关的树施加不同限制，分别得到星凸二部图、三岔凸二部图等，在这些特殊的二部图上研究上述NP完全问题的算法和复杂度，确定对哪些图类有多项式时间算法及对哪些图类是NP完全的。取得的主要成果有：(1) 上述NP完全问题在星凸二部图上NP完全的证明；上述部分NP完全问题在三岔凸二部图和圈凸二部图上的多项式时间算法；(2) 构造反例图说明凸二部图、三岔凸二部图、弦二部图、树凸二部图、完美消除二部图、圈（圆）凸二部图之间的不同；在树凸集上证明了Frankl猜想或闭并集猜想；(3) 随机实例的结构参数、相变现象、解空间的性质；(4) 应用问题的求解等。发表学术论文20篇（含国际期刊10篇，全部为SCI检索；国际会议口头报告8篇，全部为EI检索；国内学报1篇；公开技术报告1篇），编著国家级规划教材2部。