A 2116-approximation for the minimum 3-path partition problem

Document Type

Conference Proceeding

Publication Date



Computer Science

Publication Title

Leibniz International Proceedings in Informatics, LIPIcs


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