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

2018/07/18 by Tang, Zhongzheng, Diao, Zhuo
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1807.06867

Abstract

Given a weighted graph G(V,E) with weight \mathbf w: E→ 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 τ_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→ 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τ_k(G_w). In this paper, we design a (k²-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.

Related

• Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
• Minimum-weight Cycle Covers and Their Approximability
• Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
• On Approximating Restricted Cycle Covers
• A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs