Geodesic
An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph
Trudy Instituta matematiki, Tome 28 (2020) no. 1, pp. 63-73.

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

The problem of removing the minimal number of vertices of a given graph so that the resulting graph contains no cycles $C_4$ on 4 vertices and no paths $P_5$ on 5 vertices as subgraphs is considered. A 4-approximation algorithm for this problem is described. 
@article{TIMB_2020_28_1_a6,
     author = {V. V. Lepin},
     title = {An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph},
     journal = {Trudy Instituta matematiki},
     pages = {63--73},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2020_28_1_a6/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph
JO  - Trudy Instituta matematiki
PY  - 2020
SP  - 63
EP  - 73
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2020_28_1_a6/
LA  - ru
ID  - TIMB_2020_28_1_a6
ER  - 
%0 Journal Article
%A V. V. Lepin
%T An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph
%J Trudy Instituta matematiki
%D 2020
%P 63-73
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2020_28_1_a6/
%G ru
%F TIMB_2020_28_1_a6
V. V. Lepin. An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph. Trudy Instituta matematiki, Tome 28 (2020) no. 1, pp. 63-73. http://geodesic.mathdoc.fr/item/TIMB_2020_28_1_a6/

[1] Alekseev V. E., Mokeev D. B., “König graphs for 3-paths and 3-cycles”, Discrete Applied Mathematics, 204 (2016), 1–5 | DOI | MR | Zbl

[2] Bafna V., P. Berman, T. Fujito, “A 2-approximation algorithm for the undirected feedback vertex set problem”, SIAM Journal on Discrete Mathematics, 12 (1999), 289–297 | DOI | MR | Zbl

[3] 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 | MR

[4] Becker A., D. Geiger, “Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem”, Artificial Intelligence, 83 (1996), 167–188 | DOI | MR

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

[6] Bresar B., M. Jakovac, J. Katrenic, G. Semanisin, A. Taranenko, “On the vertex k-path cover”, Discrete Applied Mathematics, 161:13 (2013), 1943–1949 | DOI | MR | Zbl

[7] Bresar B., F. Kardos, J. Katrenic, G. Semanisin, “Minimum k-path vertex cover”, Discrete Applied Mathematics, 159 (2011), 1189–1195 | DOI | MR | Zbl

[8] Camby E., Cardinal J., Chapelle M., Fiorini S., Joret G., “A primal-dual 3-approximation algorithm for hitting 4-vertex paths”, 9th International Colloquium on Graph Theory and Combinatorics, ICGT, 2014, 61

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

[10] Chudak F. A., M.X. Goemans, D.S.Hochbaum, D.P. Williamson, “A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs”, Operations Research Letters, 22 (1998), 111–118 | DOI | MR | Zbl

[11] Goemans M. X., D.P. Williamson, “The primal-dual method for approximation algorithms and its application to network design problems”, Approximation algorithms for NP-hard problems, 1997, 144–191

[12] Gollmann D., “Protocol analysis for concrete environments”, Computer Aided Systems Theory, EUROCAST 2005, 2005, 365–372 | Zbl

[13] Goring F., J. Harant, D. Rautenbach, I. Schiermeyer, “On Findependence in graphs”, Discussiones Mathematicae Graph Theory, 29 (2009), 377–383 | DOI | MR | Zbl

[14] Guruswami V., E. Lee, “Inapproximability of Feedback Vertex Set for Bounded Length Cycles”, Electronic Colloquium on Computational Complexity, 21 (2014), 2

[15] Hassin R., Rubinstein S., “An approximation algorithm for maximum packing of 3-edge paths”, Information Processing Letters, 63:2 (1997), 63–67 | DOI | MR | Zbl

[16] Kardoš F., J. Katrenic, I. Schiermeyer, “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theoretical Computer Science, 412 (2011), 7009–7017 | DOI | MR | Zbl

[17] Katrenič J., “A faster FPT algorithm for 3-path vertex cover”, Information Processing Letters, 116:4 (2016), 273–278 | DOI | MR | Zbl

[18] Li Y., Tu J., “A 2-approximation algorithm for the vertex cover $P_4$ problem in cubic graphs”, International Journal of Computer Mathematics, 91:10 (2014), 2103–2108 | DOI | MR | Zbl

[19] Novotnỳ M., “Design and analysis of a generalized canvas protocol”, Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices, 2010, 106–121

[20] Novotnỳ M., “Formal analysis of security protocols for wireless sensor networks”, Tatra Mountains Mathematical Publications, 47, 2010, 81–97 | DOI | MR | Zbl

[21] Tanahashi R., Chen Z.-Z., “A simple test on 2-vertex-and 2-edgeconnectivity”, IEICE Transactions on Information and Systems, E93-D:2 (2010), 241–249 | DOI

[22] Tu J., “A fixed-parameter algorithm for the vertex cover $P_3$ problem”, Information Processing Letters, 115:2 (2015), 96–99 | DOI | MR | Zbl

[23] Tu J., “Efficient algorithm for the vertex cover $P_k$ problem on cacti”, Applied Mathematics and Computation, 311 (2017), 217–222 | DOI | MR | Zbl

[24] Tu J., L. Wu, J. Yuan, L. Cui, “On the vertex cover $P_3$ problem parameterized by treewidth”, Journal of Combinatorial Optimization, 34:2 (2017), 414–425 | DOI | MR | Zbl

[25] Tu J., F. Yang, “The vertex cover P3 problem in cubic graphs”, Information Processing Letters, 113 (2013), 481–485 | DOI | MR | Zbl

[26] Tu J., W. Zhou, “A factor 2 approximation algorithm for the vertex cover P3 problem”, Information Processing Letters, 111 (2011), 683–686 | DOI | MR | Zbl

[27] Tu J., W. Zhou, “A primal-dual approximation algorithm for the vertex cover P3 problem”, Theoretical Computer Science, 412 (2011), 7044–7048 | DOI | MR | Zbl

[28] Tu J., Jin Z., “An FPT algorithm for the vertex cover $P_4$ problem”, Discrete Applied Mathematics, 200 (2016), 186–190 | DOI | MR | Zbl

[29] Xiao M., Kou S., “Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs”, International Workshop on Frontiers in Algorithmics, Springer, 2015, 282–293 | DOI | Zbl

[30] Vogt H., Integrity preservation for communication in sensor networks, Technical Report 434, Institute for Pervasive Computing, ETH, Zürich, 2004

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

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