逼近4正则图的最小顶点覆盖问题的难解性(英文)  

Hardness of approximating the Minimum Vertex Cover problem for 4-regular graphs

作　　者：陈文彬[1] 

机构地区：[1]广州大学计算机科学与教育软件学院,广东广州510006

出　　处：《广州大学学报（自然科学版）》2014年第1期65-69,共5页Journal of Guangzhou University:Natural Science Edition

基　　金：Our research has been supported by the National Science Foundation of China(NSFC)under GrantNo.11271097;the research project of Guangzhou Education Bureau under Grant No.2012A074;the project IIPL-2011-001 from Shanghai Key Laboratory of Intelligent Information Processing;the project KFKT2012B01 from State Key Laboratory for Novel Software Technology,Nanjing University

摘　　要：证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.In this paper,we show that it is hard to approximate the Minimum Vertex Cover for 4-regular graphs within some constant factor. Similarly,the result is also correct for 5-regular graphs,6-regular graphs and so on. It is known that approximating the Minimum Vertex Cover problem for 3-regular graphs within some constant factor is NP-hard. We extend the result to 4-regular graphs. We use K-reductions to prove this result. We give a K-reduction from the Minimum Vertex Cover of 3-regular graphs to that of 4-regular graphs.

关 键 词：NP-难解性 计算复杂性 正则图 顶点覆盖 近似性 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]