Approximation algorithms for cycle and path partitions in complete graphs

Given an edge-weighted (metric/general) complete graph with n vertices, where n mod k = 0, the maximum weight (metric/general) k-cycle/path partition problem is to find a set of n k vertex-disjoint k-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric k-cycle partition, we improve the previous approximation ratio from 3 5 to 7 10 for k = 5, and from 7 8 ( 1 − 1 k ) 2 for k > 5 to ( 7 8 − 1 8 k ) ( 1 − 1 k ) for constant odd k > 5 and to 7 8 ( 1 − 1 k + 1 k ( k − 1 ) ) for even k > 5. For metric k-path partition, we improve the approximation ratio from 7 8 ( 1 − 1 k ) to 27 k 2 − 48 k + 16 32 k 2 − 36 k − 24 for k ∈ { 6, 8, 10 }. For the case of k = 4, we improve the approximation ratio from 3 4 to 5 6 for metric 4-cycle partition, from 2 3 to 3 4 for general 4-cycle partition, and from 3 4 to 14 17 for metric 4-path partition.

Authors

• Jingyang Zhao
• Mingyu Xiao

Keywords

• Approximation algorithms
• Cycle partition
• Path partition