顶点P_k覆盖问题的研究综述

A survey on vertex cover P_k problem

顶点覆盖问题是经典的NP完全问题,在排序、计算机网络等现实生活中有许多的应用.近几年来,许多研究者开始探究它的推广形式——顶点P_k覆盖(VCP_k)问题,即寻找一个顶点子集,从拓扑结构图中删除后使得剩下的顶点导出的子图不包含P_k路,其中P_k是指包含k个顶点的路.本文简单介绍了VCP_k问题的应用背景,归纳了它在近似算法、精确算法、参数化算法3个方面的主要研究进展,并分析了一些主要的方法和技巧.在此基础上,对VCP_k问题及其相关问题的研究前景进行了展望.

Vertex cover problem is a classical NP complete problem,which has many applications in areas of sor-ting,computer network,etc.In recent years,many researchers begin to explore its generalized form,namely vertexcover P_k problem,which requires to find a subset of vertices such that the induced subgraphs by the rest vertices ofthe topological structure do not include any P_k path,where P_k is the path onkvertices.This paper firstly introducesthe application background of vertex cover P_k problem,then summarizes current researches in approximation algo-rithms,exact algorithms and parameter algorithms,and analyzes some commonly used methods and techniques.Onthis basis,we point out the direction for further research on the vertex cover P_k problem and its related issues.