pith. sign in

arxiv: 2606.17578 · v1 · pith:ES44FLDLnew · submitted 2026-06-16 · 💻 cs.DS

Exact Algorithms for Edge Deletion to Cactus Graphs and Weighted Variants

Wenhao Song This is my paper

Pith reviewed 2026-06-26 22:26 UTC · model grok-4.3

classification 💻 cs.DS
keywords edge deletioncactus graphsexact algorithmsexponential timedynamic programmingweighted problems
0
0 comments X

The pith

Edge deletion to make a connected cactus graph is solvable exactly in O*(2^n) time.

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

The paper studies the problem of deleting the smallest number of edges from a connected graph so that what remains is still connected and forms a cactus. Akhtar and Philip previously solved the unweighted version in O*(3^n) time. The new work improves this to O*(2^n) time and space via a dynamic-programming approach. When deletion costs take at most q distinct nonnegative values, the same framework yields O*(2^n n^{O(q)}) time. The result also supplies an O*(2^n (W+1)) pseudo-polynomial algorithm for integer costs summing to W and falls back to O*(3^n) for arbitrary real costs.

Core claim

The minimum number of edges to delete to obtain a connected cactus admits an exact algorithm running in O*(2^n) time and space; when costs take q distinct nonnegative real values the same bound becomes O*(2^n n^{O(q)}), and for total integer weight W it becomes O*(2^n (W+1)).

What carries the argument

A dynamic-programming recurrence whose state space is bounded by 2^n (or 2^n n^{O(q)} when costs take q values).

If this is right

  • Every instance of the unweighted problem is solvable in single-exponential time.
  • Any fixed number of distinct deletion costs yields a near-single-exponential algorithm.
  • Integer-cost instances with total weight W are solvable in O*(2^n W) time.
  • Arbitrary real costs still require only O*(3^n) time, matching the prior bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar subset-based recurrences may apply to other deletion-to-sparse-graph problems whose target class has bounded treewidth or feedback edge set.
  • The n^{O(q)} overhead suggests that the number of distinct costs, rather than their magnitudes, is the main barrier to single-exponential time.

Load-bearing premise

A correct dynamic-programming or branching recurrence exists whose states can be limited to size 2^n while still computing the exact minimum deletion cost.

What would settle it

An explicit small graph on which any 2^n-state recurrence either misses an optimal deletion set or reports an incorrect cost.

read the original abstract

We study exact exponential-time algorithms for Edge Deletion to Cactus. Given a connected graph $G$, the task is to delete a minimum number of edges so that the remaining spanning graph is a connected cactus. Akhtar and Philip (IWOCA 2026) gave an $O^*(3^n)$-time algorithm for the unweighted problem, where $n$ is the number of vertices in the input graph and the $O^*(\cdot)$ notation hides polynomial factors. We improve this bound to $O^*(2^n)$ time and space. More generally, if the deletion costs take at most $q$ distinct nonnegative real values, then the weighted problem can be solved in $O^*(2^n n^{O(q)})$ time and space. Thus every fixed number of distinct costs, and in particular the unweighted case, admits a faster exact algorithm. For nonnegative integer costs of total weight $W$, we obtain an $O^*(2^n(W+1))$ pseudo-polynomial algorithm, while arbitrary nonnegative real costs admit an $O^*(3^n)$ exact algorithm.

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 / 1 minor

Summary. The manuscript claims an improvement for the Edge Deletion to Cactus problem (delete minimum edges to obtain a connected cactus) from the prior O*(3^n) bound of Akhtar and Philip to O*(2^n) time and space in the unweighted case. For the weighted variant where deletion costs take at most q distinct nonnegative real values, it claims an O*(2^n n^{O(q)}) algorithm; for nonnegative integer costs with total weight W it claims O*(2^n (W+1)); and for arbitrary nonnegative reals it retains O*(3^n).

Significance. If the claimed single-exponential bound holds via a correct DP or branching procedure over subsets that exploits the block structure of cacti, the result would constitute a meaningful advance for exact algorithms on this graph-modification problem, moving it into the 2^n regime that is often optimal under ETH for subset-based problems. The parameterized weighted results by number of distinct costs and the pseudo-polynomial bound are also of practical interest.

minor comments (1)
  1. The abstract states the O*(2^n) and O*(2^n n^{O(q)}) bounds without a recurrence or high-level proof sketch; while the full manuscript presumably supplies the DP definition and analysis, adding a one-sentence outline of the state space in the abstract would aid quick verification of the improvement over the 3^n baseline.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation to accept. There are no major comments requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity; algorithmic bound is independent

full rationale

The paper presents a new exact algorithm for Edge Deletion to Cactus, claiming an O^*(2^n) time bound (and O^*(2^n n^{O(q)}) generalization) that improves on the cited prior O^*(3^n) result of Akhtar and Philip. The derivation consists of designing a DP or branching procedure whose states and transitions are analyzed to produce the stated bound; this analysis does not reduce by construction to any fitted parameter, self-citation loop, or input that is renamed as output. The cactus structure (blocks are edges or cycles) is used to define compatible states, but the exponential bound follows from the subset enumeration or recurrence size rather than tautological redefinition. No load-bearing step matches any of the enumerated circularity patterns. The result is self-contained against external benchmarks (prior algorithm and standard exact-algorithm techniques).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions of connected graphs and cactus graphs together with conventional exact-algorithm design; no free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions and properties of connected graphs and cactus graphs hold.
    Problem statement presupposes these background facts from graph theory.

pith-pipeline@v0.9.1-grok · 5710 in / 1252 out tokens · 29592 ms · 2026-06-26T22:26:24.484045+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

15 extracted references · 12 canonical work pages

  1. [1]

    Exact algorithms for edge deletion to cactus

    Sheikh Shakil Akhtar and Geevarghese Philip. Exact algorithms for edge deletion to cactus. In Florent Foucaud and Aline Parreau, editors,Combinatorial Algorithms, IWOCA 2026, Lecture Notes in Computer Science, vol. 16587, pages 32–44. Springer, Cham, 2026.https://doi.org/10.1007/978-3-032-27732-9_3

    work page doi:10.1007/978-3-032-27732-9_3 2026

  2. [2]

    Dynamic programming treatment of the travelling salesman problem.Journal of the ACM, 9(1):61–63, 1962

    Richard Bellman. Dynamic programming treatment of the travelling salesman problem.Journal of the ACM, 9(1):61–63, 1962. https://doi.org/10.1145/ 321105.321111

    arXiv 1962

  3. [3]

    2007 , isbn =

    Andreas Bj¨ orklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets M¨ obius: Fast subset convolution. InProceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 67–74. ACM, 2007. https: //doi.org/10.1145/1250790.1250801

    work page doi:10.1145/1250790.1250801 2007

  4. [4]

    Fixed-parameter tractability of graph modification problems for hereditary properties.Information Processing Letters, 58(4):171–176, 1996

    Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties.Information Processing Letters, 58(4):171–176, 1996. https: //doi.org/10.1016/0020-0190(96)00050-6

    work page doi:10.1016/0020-0190(96)00050-6 1996

  5. [5]

    E. S. El-Mallah and C. J. Colbourn. The complexity of some edge deletion problems.IEEE Transactions on Circuits and Systems, 35(3):354–362, 1988. https: //doi.org/10.1109/31.1748

    work page doi:10.1109/31.1748 1988

  6. [6]

    Fomin and Dieter Kratsch.Exact Exponential Algorithms

    Fedor V. Fomin and Dieter Kratsch.Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg, 2010.https://doi.org/10.1007/978-3-642-16533-7

    work page doi:10.1007/978-3-642-16533-7 2010

  7. [7]

    Martin Charles Golumbic and Robert E. Jamison. Edge and vertex intersection of paths in a tree.Discrete Mathematics, 55(2):151–159, 1985. https://doi.org/10. 1016/0012-365X(85)90043-3

    1985

  8. [8]

    Martin Charles Golumbic and Robert E. Jamison. The edge intersection graphs of paths in a tree.Journal of Combinatorial Theory, Series B, 38(1):8–22, 1985. https://doi.org/10.1016/0095-8956(85)90088-7

    work page doi:10.1016/0095-8956(85)90088-7 1985

  9. [9]

    Uhlenbeck

    Frank Harary and George E. Uhlenbeck. On the number of Husimi trees, I. Proceedings of the National Academy of Sciences of the United States of America, 39(4):315–322, 1953.https://doi.org/10.1073/pnas.39.4.315

    work page doi:10.1073/pnas.39.4.315 1953

  10. [10]

    Michael Held and Richard M. Karp. A dynamic programming approach to se- quencing problems.Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962.https://doi.org/10.1137/0110015

    work page doi:10.1137/0110015 1962

  11. [11]

    Algorithm 447: Efficient algorithms for graph manipulation.Communications of the ACM, 16(6):372–378, 1973

    John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation.Communications of the ACM, 16(6):372–378, 1973. https://doi. org/10.1145/362248.362272

    work page doi:10.1145/362248.362272 1973

  12. [12]

    Edge deletion to tree-like graph classes.Discrete Applied Mathematics, 348:122–131, 2024

    Ivo Koch, Nina Pardal, and Vinicius Fernandes dos Santos. Edge deletion to tree-like graph classes.Discrete Applied Mathematics, 348:122–131, 2024. https: //doi.org/10.1016/j.dam.2024.01.028

    work page doi:10.1016/j.dam.2024.01.028 2024

  13. [13]

    Complexity classification of some edge modification problems.Discrete Applied Mathematics, 113(1):109–128, 2001

    Assaf Natanzon, Ron Shamir, and Roded Sharan. Complexity classification of some edge modification problems.Discrete Applied Mathematics, 113(1):109–128, 2001. https://doi.org/10.1016/S0166-218X(00)00391-7

    work page doi:10.1016/s0166-218x(00)00391-7 2001

  14. [14]

    A. T. White.Graphs of Groups on Surfaces: Interactions and Models. North-Holland Mathematics Studies, vol. 188. Elsevier, Amsterdam, 2001

    2001

  15. [15]

    Edge-deletion problems.SIAM Journal on Computing, 10(2):297–309, 1981.https://doi.org/10.1137/0210021

    Mihalis Yannakakis. Edge-deletion problems.SIAM Journal on Computing, 10(2):297–309, 1981.https://doi.org/10.1137/0210021. A Integer weights Assume now thatc e ∈Z ≥0 for all edges and let W= X e∈E ce. All dynamic programming values lie in {0, 1, . . . , W} ∪ {−∞}. Thus Lemma 3 applies withM=W. The one-block values are maximum-weight Hamiltonian-cycle valu...

    work page doi:10.1137/0210021 1981