Given a weighted graph $G=(V, E)$ with weight $w: E \rightarrow \mathbb{Z}^{+}$, a $k$-cycle transversal is an edge subset $A$ of $E$ such that $G-A$ has no $k$-cycle. The minimum weight of $k$ cycle transversal is the weighted transversal number on $k$-cycle, denoted by $\tau_{k}\left(G_{w}\right)$. In this paper, we design a $(k-1 / 2)$-approximation algorithm for the weighted transversal number on $k$-cycle when $k$ is odd. Given a weighted graph $G=(V, E)$ with weight $w: E \rightarrow \mathbb{Z}^{+}$, a $k$-clique transversal is an edge subset $A$ of $E$ such that $G-A$ has no $k$-clique. The minimum weight of $k$-clique transversal is the weighted transversal number on $k$-clique, denoted by $\widetilde{\tau_{k}}\left(G_{w}\right)$. In this paper, we design a $\left(k^{2}-k-1\right) / 2-$ approximation algorithm for the weighted transversal number on $k$-clique. Last, we discuss the relationship between $k$-clique covering and $k$-clique packing in complete graph $K_{n}$.
Zhong-Zheng Tang, Zhuo Diao
. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal[J]. Journal of the Operations Research Society of China, 2021
, 9(4)
: 883
-892
.
DOI: 10.1007/s40305-020-00335-4
[1] Yannakakis,M.:Node-andedge-deletionNP-completeproblems.In:ProceedingsoftheTenthAnnual ACM Symposium on Theory of Computing, pp. 253-264(1978)
[2] Krivelevich, M.:On a conjecture of Tuza about packing and covering of triangles. Discret. Math. 142(1), 281-286(1995)
[3] Kortsarz, G., Langberg, M., Nutov, Z.:Approximating maximum subgraphs without short cycles. SIAM J. Discret. Math. 24(1), 255-269(2010)
[4] Khot, S., Regev, O.:Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci. 74(3), 335-349(2008)
[5] Xia, G., Zhang, Y.:On the small cycle transversal of planar graphs. Theor. Comput. Sci. 412(29), 3501-3509(2011)
[6] Xia, G., Zhang, Y.:Kernelization for cycle transversal problems. Discret. Appl. Math. 160(7-8), 1224-1231(2012)
[7] Brügmann, D., Komusiewicz, C., Moser, H.:On generating triangle-free graphs. Electron. Notes Discret. Math. 32, 51-58(2009)
[8] Tuza, Z.:A conjecture on triangles of graphs. Graphs Comb. 6(4), 373-380(1990)
[9] Haxell, P.E., Kohayakawa, Y.:Packing and covering triangles in tripartite graphs. Graphs Comb. 14(1), 1-10(1998)
[10] Haxell, P.E.:Packing and covering triangles in graphs. Discret. Math. 195(1), 251-254(1999)
[11] Cui, Q., Haxell, P., Ma, W.:Packing and covering triangles in planar graphs. Graphs Comb. 25(6), 817-824(2009)
[12] Haxell, P., Kostochka, A., Thomassé, S.:Packing and covering triangles in K4-free planar graphs. Graphs Comb. 28(5), 653-662(2012)
[13] Chen, X., Diao, Z., Hu, X., Tang, Z.:Sufficient conditions for Tuza's conjecture on packing and covering triangles. In:Combinatorial Algorithms, Volume 9843 of Lecture Notes in Computer Science, pp. 266-277(2016)
[14] Chen, X., Diao, Z., Hu, X., Tang, Z.:Total dual integrality of triangle covering. In:Combinatorial Optimization and Applications, Volume 10043 of Lecture Notes in Computer Science, pp. 128-143(2016)
[15] Chen, X., Diao, Z., Xiaodong, H., Tang, Z.:Covering triangles in edge-weighted graphs. Theory Comput. Syst. 62(6), 1525-1552(2018)
[16] Erdos, P., Stone, A.H., et al.:On the structure of linear graphs. Bull. Am. Math. Soc 52(1087-1091), 1(1946)
[17] Brualdi, R.A.:Introductory Combinatorics, 5th edn. Pearson, New York (2009)
