A 21/16-Approximation for the Minimum 3-Path Partition Problem

Authors Yong Chen, Randy Goebel, Bing Su, Weitian Tong , Yao Xu, An Zhang



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.46.pdf
  • Filesize: 0.56 MB
  • 20 pages

Document Identifiers

Author Details

Yong Chen
  • Department of Mathematics, Hangzhou Dianzi University, Hangzhou, Zhejiang, China
Randy Goebel
  • Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada
Bing Su
  • School of Economics and Management, Xi'an Technological University, Xi'an, Shaanxi, China
Weitian Tong
  • Department of Computer Science, Eastern Michigan University, Ypsilanti, Michigan 48197, USA
Yao Xu
  • Department of Computer Science, Kettering University, Flint, Michigan 48504, USA
An Zhang
  • Department of Mathematics, Hangzhou Dianzi University, Hangzhou, Zhejiang, China

Cite AsGet BibTex

Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu, and An Zhang. A 21/16-Approximation for the Minimum 3-Path Partition Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.46

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 3/2, which was recently improved to 13/9 and further to 4/3. We investigate the 3/2-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 l-paths, l in {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 13/9 and 4/3. When switching back to the unweighted objective function, we prove the approximation ratio 21/16 via amortized analysis.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Approximation algorithms analysis
Keywords
  • 3-path partition
  • exact set cover
  • approximation algorithm
  • local search
  • amortized analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Y. Chen, R. Goebel, G. Lin, L. Liu, B. Su, W. Tong, Y. Xu, and A. Zhang. A local search 4/3-approximation algorithm for the minimum 3-path partition problem. In FAW, pages 14-25, 2019. Google Scholar
  2. Y. Chen, R. Goebel, G. Lin, B. Su, Y. Xu, and A. Zhang. An improved approximation algorithm for the minimum 3-path partition problem. Journal of Combinatorial Optimization, 38(1):150-164, 2019. Google Scholar
  3. R.-c. Duh and M. Fürer. Approximation of k-set cover by semi-local optimization. In STOC, pages 256-264, 1997. Google Scholar
  4. M. R. Garey and D. S. Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. Google Scholar
  5. R. M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. 1972. Google Scholar
  6. N. Korpelainen. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics, 2018. Google Scholar
  7. J. Monnot and S. Toulouse. The P_k partition problem and related problems in bipartite graphs. In SOFSEM, pages 422-433, 2007. Google Scholar
  8. G. Steiner. On the k-th path partition problem in cographs. Congressus Numerantium, pages 89-96, 2000. Google Scholar
  9. G. Steiner. On the k-path partition of graphs. Theoretical Computer Science, 290(3):2147-2155, 2003. Google Scholar
  10. J.-H. Yan, G. J. Chang, S. M. Hedetniemi, and S. T. Hedetniemi. k-Path partitions in trees. Discrete Applied Mathematics, 78(1-3):227-233, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail