| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 417992 | Discrete Applied Mathematics | 2016 | 5 Pages |
Abstract
A subset FF of vertices of a graph GG is called a vertex cover PtPt (VCPtVCPt) set if every path of order tt in GG contains at least one vertex from FF. The vertex cover PtPt (VCPtVCPt) problem is to find a minimum VCPtVCPt set in a graph. The VCPtVCPt problem is NP-complete for any integer t≥2t≥2. In this paper, we restrict our attention to the VCP4VCP4 problem and present an FPT algorithm with runtime O∗(3k)O∗(3k) for the VCP4VCP4 problem. The algorithm constructs a VCP4VCP4 set of size at most kk in a given graph GG, or reports that no such VCP4VCP4 set exists in GG.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jianhua Tu, Zemin Jin,