Geodesic
An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 55-65.

Voir la notice de l'article provenant de la source Library of Science

Given a graph G = (V,E), the task in the vertex cover P3(VCP3) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP3 problem on planar graphs.
Keywords: combinatorial optimization, vertex cover P3 problem, branch- width, planar graphs, EPTAS 
@article{DMGT_2019_39_1_a5,
     author = {Tu, Jianhua and Shi, Yongtang},
     title = {An {Efficient} {Polynomial} {Time} {Approximation} {Scheme} for the {Vertex} {Cover} {P\protect\textsubscript{3}} {Problem} on {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {55--65},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a5/}
}
TY  - JOUR
AU  - Tu, Jianhua
AU  - Shi, Yongtang
TI  - An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 55
EP  - 65
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a5/
LA  - en
ID  - DMGT_2019_39_1_a5
ER  - 
%0 Journal Article
%A Tu, Jianhua
%A Shi, Yongtang
%T An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 55-65
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a5/
%G en
%F DMGT_2019_39_1_a5
Tu, Jianhua; Shi, Yongtang. An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 55-65. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a5/

[1] B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. ACM 41 (1994) 153-180. doi: 10.1145/174644.174650

[2] F. Bienstock and C.L. Monma, On the complexity of embedding planar graphs to minimize centain distance measure, Algorithmica 5 (1990) 93-109. doi: 10.1007/BF01840379

[3] H.L. Bodlaender, M. Cygan, S. Kratsch and J. Nederlof, Deterministic single expo- nential time algorithms for connectivity problems parameterized by treewidth, Inform. and Comput. 243 (2015) 86-111. doi: 10.1016/j.ic.2014.12.008

[4] R. Boliac, K. Cameron and V.V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004) 241-253.

[5] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmil- lan/Elsevier, London/New York, 1976).

[6] B. Breˇsar, F. Kardoˇs, J. Katreniˇc and G. Semaniˇsin, Minimum k-path vertex cover, Discrete Appl. Math. 159 (2011) 1189-1195. doi: 10.1016/j.dam.2011.04.008

[7] M.S. Chang, L.H. Chen, L.J. Hung, Y.Z. Liu, P. Rossmanith and S. Sikdar, An O*(1.4658n)-time exact algorithm for the maximum bounded-degree-1 set problem, in: Proceedings of the 31st Workshop on Combinatorial Mathematics and Computation Theory (2014) 9-18.

[8] M.S. Chang, L.H. Chen, L.J. Hung, P. Rossmanith and P.C. Su, Fixed-parameter algorithms for vertex cover P3, Discrete Optim. 19 (2016) 12-22. doi: 10.1016/j.disopt.2015.11.003

[9] E.D. Demaine, F.V. Fomin, M. Hajiaghayi and D.M. Thilikos, Fixed-parameter al- gorithms for (k, r)-center in planar graphs and map graphs, ACM Trans. Algorithms 1 (2005) 33-47.

[10] M.R. Fellows, J. Guo, H. Moser and R. Niedermeier, A complexity dichotomy for finding disjoint solutions of vertex deletion problems, ACM Trans. Comput. Theory 2 (2011) #5.

[11] F.V. Fomin and D.M. Thilikos, New upper bounds on the decomposability of planar graphs, J. Graph Theory 51 (2006) 53-81. doi: 10.1002/jgt.20121

[12] Q. Gu and H. Tamaki, Optimal branch-decomposition of planar graphs in O(n3) time, ACM Trans. Algorithms 4 (2008) #30.

[13] O. Hjortas, Branch decompositions of k-outerplanar graphs (Master’s Thesis, Uni- versity of Bergen, Department of Informatics, 2005).

[14] F. Kardoš, J. Katrenič and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci. 412 (2011) 7009-7017. doi: 10.1016/j.tcs.2011.09.009

[15] J. Katrenič, A faster FPT algorithm for 3-path vertex cover, Inform. Process. Lett. 116 (2016) 273-278. doi: 10.1016/j.ipl.2015.12.002

[16] R.J. Lipton and R.E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177-189. doi: 10.1137/0136016

[17] H. Moser, R. Niedermeier and M. Sorge, Exact combinatorial algorithms and exper- iments for finding maximum k-plexes, J. Comb. Optim. 24 (2012) 347-373. doi: 10.1007/s10878-011-9391-5

[18] M. Novotný, Design and analysis of a generalized canvas protocol, in: Proceedings of WISTP 2010, Lecture Notes in Comput. Sci. 6033 (2010) 106-121. doi: 10.1007/978-3-642-12368-9 8

[19] N. Robertson and P.D. Seymour, Graph minors, X. obstructions to tree-decompo- sition, J. Combin. Theory Ser. B 52 (1991) 153-190. doi: 10.1016/0095-8956(91)90061-N

[20] J.H. Tu, A fixed-parameter algorithm for the vertex cover P3 problem, Inform. Pro- cess. Lett. 115 (2015) 96-99. doi: 10.1016/j.ipl.2014.06.018

[21] J.H. Tu and F.M. Yang, The vertex cover P3 problem in cubic graphs, Inform. Process. Lett. 113 (2013) 481-485. doi: 10.1016/j.ipl.2013.04.002

[22] J.H. Tu and W.L. Zhou, A primal-dual approximation algorithm for the vertex cover P3 problem, Theoret. Comput. Sci. 412 (2011) 7044-7048. doi: 10.1016/j.tcs.2011.09.013

[23] J.H. Tu and W.L. Zhou, A factor 2 approximation algorithm for the vertex cover P3 problem, Inform. Process. Lett. 111 (2011) 683-686. doi: 10.1016/j.ipl.2011.04.009

[24] B.Y. Wu, A measure and conquer approach for the parameterized bounded degree- one vertex deletion, COCOON (2015) 469-480. doi: 10.1007/978-3-319-21398-9 37

[25] M.Y. Xiao and S.W. Kou, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theoret. Comput. Sci. 657 (2017) 86-97. doi: 10.1016/j.tcs.2016.04.043

[26] M.Y. Xiao and H. Nagamochi, Complexity and kernels for bipartition into degree- bounded induced graphs, Theoret. Comput. Sci. 659 (2017) 72-82. doi: 10.1016/j.tcs.2016.11.011

[27] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981) 310-327. doi: 10.1137/0210022.