论文部分内容阅读
本文为k-边诱导子图问题提供了一个固定参数算法,从而解决了由蔡雷振提出的一个公开问题。更具体地说,我们证明,对于任意给定的k,我们能设计出一个算法,使得在线性时间内判断一个图G是否含有k边诱导子图。我们的算法基于一些二分图上的Ramesey类型的结果,高斯的Eureka定理[1]以及一个算法元定理。另一方面,我们还证明了k边诱导子图在简单图上是NP完全的,而且在包含多重边的图上是W[1]难的。