Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916028086222848 |
|---|---|
| author | Liu, Yuxi Tian, Kangyi Xiao, Mingyu |
| author_facet | Liu, Yuxi Tian, Kangyi Xiao, Mingyu |
| contents | The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most $k$ vertices (resp., $k$ edges). Both are fundamental problems with significant applications in bioinformatics and have been extensively studied within the framework of exact and parameterized algorithms. Currently, the state-of-the-art approach utilizes the randomized ``Cut \& Count'' technique, which solves \textsc{Co-Path Set} in $O^*(4^{\mathbf{tw}})$ time and \textsc{Co-Path Packing} in $O^*(5^{\mathbf{pw}})$ time, where $\mathbf{tw}$ is treewidth and $\mathbf{pw}$ is pathwidth. However, as there is no known method to derandomize the ``Cut \& Count'' technique, the existence of deterministic single exponential time algorithms for these problems parameterized by treewidth has remained an open question. In this paper, we resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19870 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth Liu, Yuxi Tian, Kangyi Xiao, Mingyu Data Structures and Algorithms The \textsc{Co-Path Packing} (resp., \textsc{Co-Path Set}) problem asks whether a given graph can be edited to a collection of induced paths by deleting at most $k$ vertices (resp., $k$ edges). Both are fundamental problems with significant applications in bioinformatics and have been extensively studied within the framework of exact and parameterized algorithms. Currently, the state-of-the-art approach utilizes the randomized ``Cut \& Count'' technique, which solves \textsc{Co-Path Set} in $O^*(4^{\mathbf{tw}})$ time and \textsc{Co-Path Packing} in $O^*(5^{\mathbf{pw}})$ time, where $\mathbf{tw}$ is treewidth and $\mathbf{pw}$ is pathwidth. However, as there is no known method to derandomize the ``Cut \& Count'' technique, the existence of deterministic single exponential time algorithms for these problems parameterized by treewidth has remained an open question. In this paper, we resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth. |
| title | Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.19870 |