DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2024.11

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k

Authors: Yuxi Liu and Mingyu Xiao

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

The Co-Path/Cycle Packing problem (resp. The Co-Path Packing problem) asks whether we can delete at most k vertices from the input graph such that the remaining graph is a collection of induced paths and cycles (resp. induced paths). These two problems are fundamental graph problems that have important applications in bioinformatics. Although these two problems have been extensively studied in parameterized algorithms, it seems hard to break the running time bound 3^k. In 2015, Feng et al. provided an O^*(3^k)-time randomized algorithms for both of them. Recently, Tsur showed that they can be solved in O^*(3^k) time deterministically. In this paper, by combining several techniques such as path decomposition, dynamic programming, cut & count, and branch-and-search methods, we show that Co-Path/Cycle Packing can be solved in O^*(2.8192^k) time deterministically and Co-Path Packing can be solved in O^*(2.9241^{k}) time with failure probability ≤ 1/3. As a by-product, we also show that the Co-Path Packing problem can be solved in O^*(5^p) time with probability at least 2/3 if a path decomposition of width p is given.

Cite as

Yuxi Liu and Mingyu Xiao. Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.IPEC.2024.11,
  author =	{Liu, Yuxi and Xiao, Mingyu},
  title =	{{Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.11},
  URN =		{urn:nbn:de:0030-drops-222376},
  doi =		{10.4230/LIPIcs.IPEC.2024.11},
  annote =	{Keywords: Graph Algorithms, Parameterized Algorithms, Co-Path/Cycle Packing, Co-Path Packing, Cut \& Count, Path Decomposition}
}

Search Results

Documents authored by Liu, Yuxi

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than 3^k

Abstract

Cite as

Thanks for your feedback!

Could not send message