Geodesic
The weighted $k$-path vertex cover problem on series-parallel graphs
Trudy Instituta matematiki, Tome 25 (2017) no. 1, pp. 62-81.

Voir la notice de l'article provenant de la source Math-Net.Ru

Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{R}^+$ and a positive integer $k,$ we consider the weighted $k$-path vertex cover problem: it consists in finding a minimum-weight subset $S$ of vertices of a graph $G$ such that every path of order $k$ in $G$ contains at least one vertex from $S.$ We give $O(n)$ algorithms for finding the minimum weight of $k$-path vertex cover and connected $k$-path vertex cover for series-parallel graphs. 
@article{TIMB_2017_25_1_a5,
     author = {V. V. Lepin},
     title = {The weighted $k$-path vertex cover problem on series-parallel graphs},
     journal = {Trudy Instituta matematiki},
     pages = {62--81},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2017_25_1_a5/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - The weighted $k$-path vertex cover problem on series-parallel graphs
JO  - Trudy Instituta matematiki
PY  - 2017
SP  - 62
EP  - 81
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2017_25_1_a5/
LA  - ru
ID  - TIMB_2017_25_1_a5
ER  - 
%0 Journal Article
%A V. V. Lepin
%T The weighted $k$-path vertex cover problem on series-parallel graphs
%J Trudy Instituta matematiki
%D 2017
%P 62-81
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2017_25_1_a5/
%G ru
%F TIMB_2017_25_1_a5
V. V. Lepin. The weighted $k$-path vertex cover problem on series-parallel graphs. Trudy Instituta matematiki, Tome 25 (2017) no. 1, pp. 62-81. http://geodesic.mathdoc.fr/item/TIMB_2017_25_1_a5/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp.

[2] Lepin V. V., “Algoritmy dlya nakhozhdeniya nezavisimoi $\{K_1,K_2\}$-upakovki naibolshego vesa v grafe”, Trudy Instituta matematiki, 22:1 (2014), 78–97

[3] Lepin V. V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh s ogranichennoi drevesnoi shirinoi”, Trudy Instituta matematiki, 23:1 (2015), 98–114

[4] Lepin V. V., “Reshenie zadachi o vzveshennoi nezavisimoi $\{K_1,K_2\}$-upakovke na grafakh so spetsialnymi blokami”, Trudy Instituta matematiki, 23:2 (2015), 62–71

[5] Lepin V. V., “Nekotorye sluchai polinomialnoi razreshimosti zadachi nakhozhdeniya nezavisimoi $\{K_1,K_2\}$-upakovki naibolshego vesa v grafe”, Trudy Instituta matematiki, 24:2 (2016), 72–90

[6] Lepin V. V., “Reshenie vzveshennoi zadachi o $k$-razdelitele grafa, imeyuschego osobye moduli”, Trudy Instituta matematiki, 24:1 (2016), 61–74

[7] Acharya H. B., Choi T., Bazzi R. A., Gouda M. G., “The k-observer problem in computer networks”, Networking. Science, 1 (2012), 15–22 | DOI

[8] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theoret. Comput. Sci., 389:1–2 (2007), 219–236 | DOI | MR

[9] Asdre K., Nikolopoulos S. D., Papadopoulos C., “An optimal parallel solution for the path cover problem on $P_4$-sparse graphs”, Journal of Parallel and Distributed Computing, 67:1 (2007), 63–76 | DOI | MR

[10] Bai Z., Tu J., Shi Y., An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth, 2016, arXiv: 1603.09448

[11] Bakalarski S., Zygadlo J., “On path sequences of graphs”, Schedae Informaticae, 24 (2015), 239–251

[12] Boliac R., Cameron K., Lozin V. V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Comb., 72 (2004), 241–253 | MR

[13] Brause C., Krivos-Bellus R., “On a relation between k-path partition and k-path vertex cover”, Discrete Applied Mathematics, 223 (2017), 28–38 | DOI | MR

[14] Brešar B., Jakovac M., Katrenič J., Semanišin G., Taranenko A., “On the vertex k-path cover”, Discrete Applied Mathematics, 161:13–14 (2013), 1943–1949 | MR

[15] Brešar B., Kardoš F., Katrenič J., Semanišin G., “Minimum k-path vertex cover”, Discrete Applied Mathematics, 159:12 (2011), 1189–1195 | DOI | MR

[16] Brešar B., Krivoš-Belluš R., Semanišin G.,Šparl P., “On the weighted k-path vertex cover problem”, Discrete Appl. Math., 177 (2014), 14–18 | DOI | MR

[17] Cameron K., Hell P., “Independent packings in structured graphs”, Math. Program. Ser. B, 105:2–3 (2006), 201–213 | DOI | MR

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

[19] Chang M., Chen L., Hung L., Rossmanith P., Su P., “Fixed-parameter algorithms for vertex cover $P_3$”, Discrete Optim., 19 (2016), 12–22 | DOI | MR

[20] Chu Y., Fan J., Liu W., Lin C. K., “PTAS for minimum k-path connected vertex cover in growth-bounded graphs”, ICA3PP, LNCS, 8630, 2014, 114–126

[21] Dettlaff M., Lemańska M., Semanišin G., Zuazua R., “Some variations of perfect graphs”, Discuss. Math. Graph Theory, 36 (2016), 661–668 | DOI | MR

[22] Fujito T., “A unified approximation algorithm for node-deletionproblems”, Discrete Appl. Math., 86 (1998), 213–231 | DOI | MR

[23] Goring F., Harant J., Rautenbach D., Schiermeyer I., “On F-independence in graphs”, Discuss. Math. Graph Theory, 29:2 (2009), 377–383 | DOI | MR

[24] Jakovac M., Taranenko A., “On the k-path vertex cover of some graph products”, Discrete Math., 313 (2013), 94–100 | DOI | MR

[25] Jakovac M., “The k-path vertex cover of rooted product graphs”, Discrete Appl. Math., 187 (2015), 111–119 | DOI | MR

[26] Kardoš F., Katrenič J., Schiermeyer I., “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theoret. Comput. Sci., 412:50 (2011), 7009–7017 | DOI | MR

[27] Katrenič J., “A faster FPT algorithm for 3-path vertex cover”, Inf. Process. Lett., 116:4 (2016), 273–278 | DOI | MR

[28] Krishnamoorthy M. S., Deo N., “Node-deletion NP-complete problems”, SIAM J. Comput., 8:4 (1979), 619–625 | DOI | MR

[29] Lee E., Partitioning a graph into small pieces with applications to path transversal, 2016, arXiv: 1607.05122 | MR

[30] Lewis J. M., Yannakakis M., “The node-deletion problem for hereditary properties is NP-complete”, J. Comput. Syst. Sci., 20 (1980), 219–230 | DOI | MR

[31] Li X., Zhang Z., Huang X., “Approximation algorithms for minimum (weight) connected k-path vertex cover”, Discrete Appl. Math., 205 (2016), 101–108 | DOI | MR

[32] Li Y., Tu J., “A 2-approximation algorithm for the vertex cover $P_4$ problem in cubic graphs”, Int. J. Comput. Math., 91:10 (2014), 2103–2108 | DOI | MR

[33] Liu X., Lu H., Wang W., Wu W., “PTAS for the minimum k-path connected vertex cover problem in unit disk graphs”, J. Glob. Optim., 56 (2013), 449–458 | DOI | MR

[34] Lozin V. V., Rautenbach D., “Some results on graphs without long induced paths”, Inform. Process. Lett., 88:4 (2003), 167–171 | DOI | MR

[35] Moser H., Niedermeier R., Sorge M., “Exact combinatorial algorithms and experiments for finding maximum k-plexes”, J. Combin. Optim., 24 (2012), 347–373 | DOI | MR

[36] Novotny M., “Design and analysis of a generalized canvas protocol”, Proceedings of WISTP 2010, LNCS, 6033, Springer-Verlag, 2010, 106–121

[37] Orlovich Y., Dolgui A., Finke G., Gordon V., Werner F., “The complexity of dissociation set problems in graphs”, Discrete Applied Mathematics, 159:13 (2011), 1352–1366 | DOI | MR

[38] Ries B., Schamberg B., Unger W., “The k-observer problem on d-regular graphs”, Stabilization, Safety, and Security of Distributed Systems, LNCS, 9212, Springer, 2015, 81–93 | MR

[39] Tu J., Wu L., Yuan J., Cui L., “On the vertex cover $P_3$ problem parameterized by treewidth”, J. Combin. Optim. | DOI | MR

[40] Tu J., Yang F., “The vertex cover $P_3$ problem in cubic graphs”, Inf. Process. Lett., 113 (2013), 481–485 | DOI | MR

[41] Tu J., Zhou W., “A factor 2-approximation algorithm for the vertex cover $P_3$ problem”, Inf. Process. Lett., 111 (2011), 683–686 | DOI | MR

[42] Tu J., Zhou W., “A primal-dual approximation algorithm for the vertex cover $P_3$ problem”, Theor. Comput. Sci., 412 (2011), 7044–7048 | DOI | MR

[43] Tu J., “A fixed-parameter algorithm for the vertex cover $P_3$ problem”, Inf. Process. Lett., 115 (2015), 96–99 | DOI | MR

[44] Valdes J., Tarjan R. E., Lawler E. L., “The recognition of series parallel digraphs”, SIAM J. Comput., 11 (1982), 298–313 | DOI | MR

[45] Wang L., Du W., Zhang Z., Zhang X., “A PTAS for minimum weighted connected vertex cover $P_3$ problem in 3-dimensional wireless sensor networks”, J. Comb. Optim., 2015 | DOI | MR

[46] Wang L., Zhang X., Zhang Z., Broersma H., “A PTAS for the minimum weight connected vertex cover $P_3$ problem on unit disk graphs”, Theor. Comput. Sci., 571 (2015), 58–66 | DOI | MR

[47] Wu B., “A measure and conquer approach for the parameterized bounded degree-one vertex deletion”, COCOON 2015, Lect. Notes Comput. Sci., 9198, 2015, 469–480 | DOI | MR

[48] Xiao M., Kou S., “Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs”, FAW 2015, Lect. Notes Comput. Sci., 9130, 2015, 282–293 | DOI | MR

[49] Xiao M., Kou S., Kernelization and Parameterized Algorithms for 3-Path Vertex Cover, 2016, arXiv: 1608.07022 | MR

[50] Yannakakis M., “Node-deletion problems on bipartite graphs”, SIAM J. Computing, 10 (1981), 310–327 | DOI | MR

[51] Zhang Y., Shi Y., Zhang Z., “Approximation algorithm for the minimum weight connected k-subgraph cover problem”, Theoret. Comput. Sci., 535 (2014), 54–58 | DOI | MR

[52] Zhang Z., Li X., Shi Y., Nie H., Zhu Y., “PTAS for minimum k-path vertex cover in ball graph”, Information Processing Letters, 119 (2017), 9–13 | DOI | MR