Document Open Access Logo

Approximation Algorithms for Covering Vertices by Long Paths

Authors Mingyang Gong, Jing Fan, Guohui Lin , Eiji Miyano

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.53.pdf
  • Filesize: 0.74 MB
  • 14 pages

Document Identifiers

Author Details

Mingyang Gong
  • Department of Computing Science, University of Alberta, Edmonton, Canada
Jing Fan
  • Department of Computing Science, University of Alberta, Edmonton, Canada
  • College of Arts and Sciences, Shanghai Polytechnic University, Shanghai, China
Guohui Lin
  • Department of Computing Science, University of Alberta, Edmonton, Canada
Eiji Miyano
  • Department of Artificial Intelligence, Kyushu Institute of Technology, Iizuka, Japan

Funding

  • Fan, Jing: A visiting scholarship from the Shanghai Polytechnic University
  • Lin, Guohui: NSERC Canada
  • Miyano, Eiji: KAKENHI Grants JP21K11755 and JP17K00016 and JST CREST JPMJR1402

Cite AsGet BibTex

Mingyang Gong, Jing Fan, Guohui Lin, and Eiji Miyano. Approximation Algorithms for Covering Vertices by Long Paths. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.53

Abstract

Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least k vertices is considered long. When k ≤ 3, the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4, the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O(1))-approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4. Both algorithms are based on local improvement, and their performance analyses are done via amortization.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Path cover
  • k-path
  • local improvement
  • amortized analysis
  • approximation algorithm

Metrics

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

References

  1. K. Asdre and S. D. Nikolopoulos. A linear-time algorithm for the k-fixed-endpoint path cover problem on cographs. Networks, 50:231-240, 2007. Google Scholar
  2. K. Asdre and S. D. Nikolopoulos. A polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphs. Theoretical Computer Science, 411:967-975, 2010. Google Scholar
  3. P. Berman and M. Karpinski. 8/7-approximation algorithm for (1,2)-TSP. In ACM-SIAM Proceedings of the Seventeenth Annual Symposium on Discrete Algorithms (SODA'06), pages 641-648, 2006. Google Scholar
  4. Y. Cai, G. Chen, Y. Chen, R. Goebel, G. Lin, L. Liu, and An Zhang. Approximation algorithms for two-machine flow-shop scheduling with a conflict graph. In Proceedings of the 24th International Computing and Combinatorics Conference (COCOON 2018), LNCS 10976, pages 205-217, 2018. Google Scholar
  5. Y. Chen, Y. Cai, L. Liu, G. Chen, R. Goebel, G. Lin, B. Su, and A. Zhang. Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph. Journal of Combinatorial Optimization, 2021. Accepted on August 2, 2021. Google Scholar
  6. Y. Chen, Z.-Z. Chen, C. Kennedy, G. Lin, Y. Xu, and A. Zhang. Approximation algorithms for the directed path partition problems. In Proceedings of FAW 2021, LNCS 12874, pages 23-36, 2021. Google Scholar
  7. 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 Proceedings of FAW 2019, LNCS 11458, pages 14-25, 2019. Google Scholar
  8. 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:150-164, 2019. Google Scholar
  9. Y. Chen, R. Goebel, B. Su, W. Tong, Y. Xu, and A. Zhang. A 21/16-approximation for the minimum 3-path partition problem. In Proceedings of ISAAC 2019, LIPIcs 149, pages 46:1-46:20, 2019. Google Scholar
  10. H. N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC'83), pages 448-456, 1983. Google Scholar
  11. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979. Google Scholar
  12. R. Gómez and Y. Wakabayashi. Nontrivial path covers of graphs: Existence, minimization and maximization. Journal of Combinatorial Optimization, 39:437-456, 2020. Google Scholar
  13. D. S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6:243-254, 1983. Google Scholar
  14. N. Immorlica, M. Mahdian, and V. Mirrokni. Cycle cover with short cycles. In Proceedings of STACS 2005, LNCS 3404, pages 641-653, 2005. Google Scholar
  15. K. Kobayashi, G. Lin, E. Miyano, T. Saitoh, A. Suzuki, T. Utashima, and T. Yagita. Path cover problems with length cost. In Proceedings of WALCOM 2022, LNCS 13174, pages 396-408, 2022. Google Scholar
  16. J. Monnot and S. Toulouse. The path partition problem and related problems in bipartite graphs. Operations Research Letters, 35:677-684, 2007. Google Scholar
  17. M. Neuwohner. An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), LIPIcs 187, pages 53:1-53:20, 2021. Google Scholar
  18. L. L. Pao and C. H. Hong. The two-equal-disjoint path cover problem of matching composition network. Information Processing Letters, 107:18-23, 2008. Google Scholar
  19. R. Rizzi, A. I. Tomescu, and V. Mäkinen. On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinformatics, 15:S5, 2014. Google Scholar
  20. J.-H. Yan, G. J. Chang, S. M. Hedetniemi, and S. T. Hedetniemi. k-path partitions in trees. Discrete Applied Mathematics, 78: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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact