pith. sign in

arxiv: 2605.19870 · v1 · pith:WU6ANEWYnew · submitted 2026-05-19 · 💻 cs.DS

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth

Yuxi Liu , Kangyi Tian , Mingyu Xiao This is my paper

Pith reviewed 2026-05-20 01:49 UTC · model grok-4.3

classification 💻 cs.DS
keywords co-path packingco-path settreewidthdeterministic algorithmssingle-exponential timeparameterized complexitygraph editingbioinformatics
0
0 comments X

The pith

Deterministic single-exponential time algorithms solve co-path packing and co-path set parameterized by treewidth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that deterministic algorithms exist for the co-path packing and co-path set problems with single-exponential dependence on treewidth. These problems ask whether a graph can be turned into a collection of induced paths by deleting at most k vertices or edges respectively. Sympathetic readers care because prior solutions used randomized Cut & Count methods, leaving open the question of whether equally fast deterministic versions were possible. The authors close the gap with new algorithms based on tree decompositions. This provides reliable computation for applications in bioinformatics without relying on randomness.

Core claim

We resolve this gap by providing deterministic single exponential time algorithms for both problems when parameterized by treewidth, in contrast to the previous randomized Cut & Count approaches.

What carries the argument

Deterministic dynamic programming on tree decompositions that tracks partial solutions for induced path collections.

Load-bearing premise

The approach assumes a deterministic dynamic programming setup on tree decompositions can achieve single-exponential dependence on treewidth without randomization or extra graph assumptions.

What would settle it

A concrete graph with treewidth 3 where the algorithm either exceeds single-exponential runtime or fails to return the correct minimum vertex or edge deletions to create induced paths.

Figures

Figures reproduced from arXiv: 2605.19870 by Kangyi Tian, Mingyu Xiao, Yuxi Liu.

Figure 1
Figure 1. Figure 1: An example for a connectivity graph of t and E ′ . All edges marked with black lines in G (the left graph) are in E ′ . The vertices marked black are in V (F). The vertex marked 0 is in R0 and the vertices marked 1-5 are in R1. The vertices marked 1 and 2 (3 and 4) are adjacent since they are in the same induced path in G[E ′ ]. in R0 ∪ R1 corresponding to u and v belong to the same induced path in G[E′ ].… view at source ↗
Figure 2
Figure 2. Figure 2: An example for a connectivity graph of t and E ′ with respect to (D, R0, R1, R2). The vertices marked black are in V (F). The vertex marked 0 is in R0 and the vertices marked 1-5 are in R1. The vertices marked 1 and 2 (3 and 4) are adjacent since they are in the same induced path in G[E ′ ]. Lemma 4. Let t be a node of T and (D, R0, R1, R2) be a partition of Xt. Let Sˆ t[D, R0, R1, R2] be a family of verte… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper claims to resolve an open question by giving the first deterministic single-exponential algorithms for Co-Path Packing and Co-Path Set parameterized by treewidth. It does so via explicit dynamic programming on tree decompositions whose per-bag states record vertex deletion status together with a constant number of path-endpoint labels and connectivity components; transitions are enumerated in polynomial time per state, producing an overall O*(c^tw) bound for a small constant c with no use of randomization or Cut & Count.

Significance. If the claimed DP recurrences are correct, the work supplies the missing deterministic single-exponential algorithms for two well-studied graph-editing problems with bioinformatics applications. The explicit construction of states and transition tables, together with the avoidance of randomized primitives, constitutes a clear technical advance over the prior randomized O*(4^tw) and O*(5^pw) results.

minor comments (3)
  1. §3.2: the precise constant c appearing in the O*(c^tw) bound for Co-Path Set is stated only asymptotically; an explicit numerical value (or tight upper bound) would strengthen the comparison with the previous 4^tw randomized bound.
  2. Figure 2: the diagram of a representative bag state would benefit from an explicit legend indicating which labels correspond to path endpoints versus connectivity components.
  3. §4.1, last paragraph: the running-time analysis assumes a nice tree decomposition of width tw; a brief remark on the cost of obtaining such a decomposition (or a reference to the standard O(2^{O(tw)} n) algorithm) would improve self-containedness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the technical contribution, and recommendation for minor revision. The referee's description of our explicit DP approach on tree decompositions is accurate. No major comments appear in the provided report, so we have no specific points requiring rebuttal or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The manuscript supplies explicit deterministic DP recurrences on tree decompositions for both problems. States per bag track vertex deletion status together with a constant number of path-endpoint labels and connectivity components; the transition tables are enumerated in polynomial time per state and yield an overall running time of the form O*(c^tw) for small constant c, with no invocation of Cut & Count or other randomized primitives. The central claim resolves an independent open question by direct construction of these recurrences rather than by fitting parameters to data, renaming prior results, or relying on load-bearing self-citations. No step reduces to its own inputs by definition or construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available so ledger is minimal; relies on standard graph-theoretic assumptions for treewidth parameterization and problem definitions.

axioms (1)
  • domain assumption Treewidth parameterization allows single-exponential time dynamic programming for the problems.
    Implicit in the claim of single-exponential time in treewidth.

pith-pipeline@v0.9.0 · 5722 in / 1108 out tokens · 55407 ms · 2026-05-20T01:49:56.940289+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Alman, J., Duan, R., Williams, V.V., Xu, Y., Xu, Z., Zhou, R.: More asymmetry yields faster matrix multiplication. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 2005–2039. SIAM (2025)

    work page 2025

  2. [2]

    Information and Computation243, 86–111 (2015)

    Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single ex- ponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation243, 86–111 (2015)

    work page 2015

  3. [3]

    PLoS computational biology4(11), e1000234 (2008)

    Chauve, C., Tannier, E.: A methodological framework for the reconstruction of con- tiguous regions of ancestral genomes and its application to mammalian genomes. PLoS computational biology4(11), e1000234 (2008)

    work page 2008

  4. [4]

    In: Algorithmic Aspects in Information and Man- agement: 6th International Conference, AAIM 2010, Weihai, China, July 19-21,

    Chen, Z.Z., Fellows, M., Fu, B., Jiang, H., Liu, Y., Wang, L., Zhu, B.: A linear kernel for co-path/cycle packing. In: Algorithmic Aspects in Information and Man- agement: 6th International Conference, AAIM 2010, Weihai, China, July 19-21,

    work page 2010

  5. [5]

    Proceedings 6. pp. 90–102. Springer (2010)

    work page 2010

  6. [6]

    Science250(4978), 245–250 (1990)

    Cox, D.R., Burmeister, M., Price, E.R., Kim, S., Myers, R.M.: Radiation hybrid mapping: a somatic cell genetic method for constructing high-resolution maps of mammalian chromosomes. Science250(4978), 245–250 (1990)

    work page 1990

  7. [7]

    Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, vol. 5. Springer (2015)

    work page 2015

  8. [8]

    In: 2011 IEEE 52nd Annual Symposium on Foundations of Com- puter Science

    Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M., Woj- taszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: 2011 IEEE 52nd Annual Symposium on Foundations of Com- puter Science. pp. 150–159. IEEE (2011)

    work page 2011

  9. [9]

    Journal of Combinatorial Optimization 29, 125–140 (2015)

    Feng, Q., Wang, J., Li, S., Chen, J.: Randomized parameterized algorithms for p2-packing and co-path packing problems. Journal of Combinatorial Optimization 29, 125–140 (2015)

    work page 2015

  10. [10]

    In: International Workshop on Frontiers in Algorithmics

    Feng, Q., Zhou, Q., Li, S.: Randomized parameterized algorithms for co-path set problem. In: International Workshop on Frontiers in Algorithmics. pp. 82–93. Springer (2014)

    work page 2014

  11. [11]

    Feng, Q., Zhou, Q., Wang, J.: Kernelization and randomized parameterized algo- rithms for co-path set problem. J. Comb. Optim.32(1), 67–78 (2016)

    work page 2016

  12. [12]

    Fernau, H.: Parameterized algorithmics for linear arrangement problems. Discret. Appl. Math.156(17), 3166–3177 (2008)

    work page 2008

  13. [13]

    Journal of the ACM (JACM)63(4), 1–60 (2016)

    Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM (JACM)63(4), 1–60 (2016)

    work page 2016

  14. [14]

    Information and Computation p

    Liu, Y., Xiao, M.: Solving co-path/cycle packing and co-path packing faster than 3k. Information and Computation p. 105406 (2026)

    work page 2026

  15. [15]

    Oxley, J.G.: Matroid theory, vol. 3. Oxford University Press, USA (2006)

    work page 2006

  16. [16]

    American journal of human genetics49(6), 1189 (1991)

    Richard 3rd, C., Withers, D., Meeker, T., Maurer, S., Evans, G., Myers, R., Cox, D.: A radiation hybrid map of the proximal long arm of human chromosome 11 containing the multiple endocrine neoplasia type 1 (men-1) and bcl-1 disease loci. American journal of human genetics49(6), 1189 (1991)

    work page 1991

  17. [17]

    In: Proceedings of the first annual international conference on Computational molecular biology

    Slonim, D., Kruglyak, L., Stein, L., Lander, E.: Building human genome maps with radiation hybrids. In: Proceedings of the first annual international conference on Computational molecular biology. pp. 277–286 (1997)

    work page 1997

  18. [18]

    In: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

    Sullivan, B.D., van der Poel, A.: A fast parameterized algorithm for co-path set. In: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). pp. 28–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2017)

    work page 2016

  19. [19]

    Journal of Combinatorial Optimization44(5), 3701–3710 (2022)

    Tsur, D.: Faster deterministic algorithms for co-path packing and co-path/cycle packing. Journal of Combinatorial Optimization44(5), 3701–3710 (2022)

    work page 2022

  20. [20]

    Information Processing Letters180, 106335 (2023)

    Tsur, D.: Faster deterministic algorithm for co-path set. Information Processing Letters180, 106335 (2023)

    work page 2023

  21. [21]

    Journal of Combinatorial Optimization27(1), 3–13 (2014)

    Zhang, C., Jiang, H., Zhu, B.: Radiation hybrid map construction problem param- eterized. Journal of Combinatorial Optimization27(1), 3–13 (2014)

    work page 2014