A 2116-approximation for the minimum 3-path partition problem
Document Type
Conference Proceeding
Publication Date
2019
Department/School
Computer Science
Publication Title
Leibniz International Proceedings in Informatics, LIPIcs
Abstract
The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k = 3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers' attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of 32 , which was recently improved to 139 and further to 43 . We investigate the 32 -approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for `-paths, ` ∈ {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios 139 and 43 . When switching back to the unweighted objective function, we prove the approximation ratio 2116 via amortized analysis.
Link to Published Version
Recommended Citation
Chen, Y., Goebel, R., Su, B., Tong, W., Xu, Y., & Zhang, A. (2019). A 21/16-approximation for the minimum 3-path partition problem. 20 pages. https://doi.org/10.4230/LIPICS.ISAAC.2019.46