论文部分内容阅读
反馈顶点集是给定图中的一个顶点子集,删除这个顶点子集让剩下的图成为森林。最小反馈顶点集问题是经典的NP完全问题之一,在实践中有广泛应用,包括操作系统中死锁预防和解除、信息安全领域、超大规模集成电路芯片设计、人工智能领域、基因序列组装等,围绕该问题有大量的研究,包括近似算法、随机算法、参数算法、精确算法、在受限图上的多项式时间算法等。
已知最小反馈顶点集问题在一般二部图上还是NP完全的,而在受限制的二部图即凸二部图上有多项式时间算法。本文把凸二部图的概念推广到一类新的受限制的二部图,即树凸二部图及其子类上,包括星树凸二部图、三岔树凸二部图和K岔树凸二部图等,给出了最小反馈顶点集问题在三岔树凸二部图上的多项式时间算法,证明了最小反馈顶点集问题在星树凸二部图上还NP完全的,还否定了最小反馈顶点集问题在树的度数有界的树凸二部图上有多项式时间算法的猜想,证明了最小反馈顶点集问题在树的度数有界但度数大于2的顶点个数无界(因此树的度数大于2的顶点度数之和无界)的树凸二部图上还是NP完全的,并把三岔树凸二部图的多项式时间算法推广到K岔树凸二部图以及树的度数大于2的顶点度数之和有界的树凸二部图上。