1 Search Results for "Fan, Jing"

Document
DOI: 10.4230/LIPIcs.MFCS.2022.53
Approximation Algorithms for Covering Vertices by Long Paths

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

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{gong_et_al:LIPIcs.MFCS.2022.53,
  author =	{Gong, Mingyang and Fan, Jing and Lin, Guohui and Miyano, Eiji},
  title =	{{Approximation Algorithms for Covering Vertices by Long Paths}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.53},
  URN =		{urn:nbn:de:0030-drops-168517},
  doi =		{10.4230/LIPIcs.MFCS.2022.53},
  annote =	{Keywords: Path cover, k-path, local improvement, amortized analysis, approximation algorithm}
}
  • Refine by Author
  • 1 Fan, Jing
  • 1 Gong, Mingyang
  • 1 Lin, Guohui
  • 1 Miyano, Eiji

  • Refine by Classification
  • 1 Theory of computation → Packing and covering problems

  • Refine by Keyword
  • 1 Path cover
  • 1 amortized analysis
  • 1 approximation algorithm
  • 1 k-path
  • 1 local improvement

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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