A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs

被引：13

作者：

Li, Yuchao ^{[1
]}

Tu, Jianhua ^{[1
]}

机构：

[1] Beijing Univ Chem Technol, Sch Sci, Beijing 100029, Peoples R China

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 2014年 / 91卷 / 10期

基金：

中国国家自然科学基金;

关键词：

05C85; 05C70; combinatorial optimization; cubic graph; approximation algorithm; sharp lower and upper bounds; vertex cover P-4 problem; APPROXIMATION ALGORITHM;

D O I：

10.1080/00207160.2014.881476

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A subset F of vertices of a graph G is called a vertex cover P-k set if every path of order k in G contains at least one vertex from F. Denote by psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The vertex cover P-k (VCPk) problem is to find a minimum vertex cover P-k set. It is easy to see that the VCP2 problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP4 problem in cubic graphs. The paper proves that the VCP4 problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on psi(4)(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.

引用

页码：2103 / 2108

页数：6

共 12 条

[1]

Bresar B., 2001, DISCRET APPL MATH, V159, P1189

[2] On the vertex k-path cover [J].

Bresar, Bostjan ;

Jakovac, Marko ;

Katrenic, Jan ;

Semanisin, Gabriel ;

Taranenko, Andrej .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) :1943-1949

[3]

Chen J. E., 2012, 6 INT FRONT ALG WORK, P199

[4] A generalization of Nemhauser and Trotter's local optimization theorem [J].

Fellows, Michael R. ;

Guo, Jiong ;

Moser, Hannes ;

Niedermeier, Rolf .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (06) :1141-1158

[5]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[6] On the k-path vertex cover of some graph products [J].

Jakovac, Marko ;

Taranenko, Andrej .

DISCRETE MATHEMATICS, 2013, 313 (01) :94-100

[7] On computing the minimum 3-path vertex cover and dissociation number of graphs [J].

Kardos, Frantisek ;

Katrenic, Jan ;

Schiermeyer, Ingo .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) :7009-7017

[8] The vertex cover P3 problem in cubic graphs [J].

Tu, Jianhua ;

Yang, Fengmei .

INFORMATION PROCESSING LETTERS, 2013, 113 (13) :481-485

[9] A primal-dual approximation algorithm for the vertex cover P3 problem [J].

Tu, Jianhua ;

Zhou, Wenli .

THEORETICAL COMPUTER SCIENCE, 2011, 412 (50) :7044-7048

[10] A factor 2 approximation algorithm for the vertex cover P3 problem [J].

Tu, Jianhua ;

Zhou, Wenli .

INFORMATION PROCESSING LETTERS, 2011, 111 (14) :683-686

← 1 2 →