Approximation algorithms on $k-$ cycle covering and $k-$ clique covering

Abstract

Given a weighted graph $G(V,E)$ with weight $\mathbf{w}:E\to Z_{+}^{|E|}$. A $k-$cycle covering is an edge subset $A$ of $E$ such that $G-A$ has no $k-$cycle. The minimum weight of $k-$cycle covering is the weighted covering number on $k-$cycle, denoted by ${\tau }_k(G_w)$. In this paper, we design a $k-1/2$ approximation algorithm for the weighted covering number on $k-$cycle when $k$ is odd. Given a weighted graph $G(V,E)$ with weight $\mathbf{w}:E\to Z_{+}^{|E|}$. A $k-$clique covering is an edge subset $A$ of $E$ such that $G-A$ has no $k-$clique. The minimum weight of $k-$clique covering is the weighted covering number on $k-$clique, denoted by $\widetilde{{\tau }_k}(G_w)$. In this paper, we design a $(k^2-k-1)/2$ approximation algorithm for the weighted covering number on $k-$clique. Last, we discuss the relationship between $k-$clique covering and $k-$clique packing in complete graph $K_n$.