Exact Algorithms for Edge Deletion to Cactus

arXiv:2603.27655 · cs.DS, cs.CC, cs.DM, math.CO · Submitted 2026-03-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Exact Algorithms for Edge Deletion to Cactus".

Jane: Here's the gist of the paper. Exact Algorithms for Edge Deletion to Cactus studies two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus.

Tom: Our first main result is that Spanning Tree to Cactus can be solved in polynomial time.

Jane: We use the polynomial-time algorithm for Spanning Tree to Cactus as a black box to obtain an exact algorithm that solves Edge Deletion to Cactus in O⋆(n(n-2)) time.

Tom: We further improve the running time for Edge Deletion to Cactus to O⋆(3 n) using dynamic programming, which is our second main result.

Title and authors: Jane: So we’re diving into "Exact Algorithms for Edge Deletion to Cactus," and we start by looking at who did this work. We want to know the names behind this research because understanding the team can tell us a lot about the approach they took.

Tom: This paper is by Sheikh Shakil Akhtar and Geevarghese Philip from the Chennai Mathematical Institute, India. They are academics focusing on graph theory, which makes sense given that this is a deep dive into graph structures.

Lu: I’ve read their background, and they have been working on cactus graphs and related problems for a while now. They seem to have a good understanding of the underlying structure needed for this kind of analysis.

Meng: I don't really know much about them personally, but when you see a paper tackling NP-hard problems like Edge Deletion to Cactus, you want to know if the authors have experience dealing with those kinds of challenges before they claim a solution.

Lalam: They are experts in graph theory, so they aren't just throwing out an algorithm without knowing the structural constraints of the graphs they are working with. That’s important for this kind of work.

Jane: Exactly, because Edge Deletion to Cactus is NP-hard on general graphs even when restricted to bipartite graphs, so we need authors who know how to handle those restrictions and complexities.

Tom: And from what I see in the abstract, they immediately tackle the complexity of Spanning Tree to Cactus as an open problem, which sets up their first main result nicely.

Lu: That's smart strategy. By solving one related problem efficiently first, they create a tool that can then be used to solve the harder one exactly later.

Meng: So they are using the polynomial-time algorithm for Spanning Tree to Cactus as a black box, which means they aren't claiming to have invented that polynomial-time method themselves.

Lalam: That’s exactly right. They use it as a tool, and then they combine it with their structural observations to prove Theorem one and subsequently lead them to the final O star three n squared time result for Edge Deletion to Cactus > <ref:2603.27655#pg3>

The paper's summary: Jane: So what is the main takeaway from this paper? They are trying to find the size of a minimum set F of edges such that removing them leaves a connected cactus subgraph.

Tom: Exactly, and they show that while Edge Deletion to Cactus was known to be NP-hard, they found an exact algorithm running in O star n squared time for the first version.

Lu: The summary explains that they use structural properties of cactus graphs and results on edge path tree graphs to prove Theorem one as a key step in their proof structure <ref:2603.27655#pg3,structural properties of cactus graphs and>.

Meng: So the summary is essentially: we take these known structural facts about how cycles interact in cactus graphs and combine them with results from EPT graphs to build a framework that solves the problem.

Lalam: They are using these properties to prove Theorem one which then allows them to use it as a subroutine to obtain Theorem two leading ultimately to the O star three n squared time algorithm for Edge Deletion to Cactus > <ref:2603.27655#pg3,as a subroutine to obtain Theorem 2>

Jane: The paper summarizes the process of moving from structural properties, through EPT graphs, and then into dynamic programming to reach the final result. It’s a lot of machinery.

Tom: It sounds like they’re showing that even though the problem is hard, you can find an exact solution if you have good structural tools to exploit.

Lu: They are essentially building a proof structure where the structural properties of cactus graphs dictate how the dynamic programming should be set up for finding that maximum spanning cactus subgraph >

The paper's improvements: Jane: Now let’s talk about what they actually improved. They didn't just find a solution, they found a faster one.

Tom: Their first improvement was getting the O star n squared time algorithm by using the polynomial-time solution for Spanning Tree to Cactus as a subroutine. That’s the first big win in complexity reduction.

Lu: And then the second major improvement is switching to dynamic programming, which brings it down from O star n squared time to O star three n squared time for Edge Deletion to Cactus >

Meng: That drop from two exponents is significant, even if they are both in the same polynomial class, because it suggests that DP can actually be very effective here. What does that mean for deployment?

Lalam: It means they’ve found a better way to compute the maximum size of a spanning cactus subgraph using dynamic programming over connected vertex sets.

Tom: So, so we moved from one big exponent to another, which is exciting because it shows how powerful this approach can be when applied correctly. This is what I like to see in an engineering context >

Jane: The implication is that for Edge Deletion to Cactus, we now have a much more efficient way to find the solution than before, moving us toward better practical applications.

Lu: And they also suggest looking at parameterized versions based on treewidth later on, which is where the real theoretical power lies, as it connects this problem to other hard problems that are already well-studied in complexity theory.

Conclusion: Tom: So to wrap up on "Exact Algorithms for Edge Deletion to Cactus," we have an exact algorithm running in O star three n squared time based on dynamic programming.

Jane: We started with a polynomial-time solution for Spanning Tree to Cactus, which enabled the first improvement, and then the dynamic programming brought us to this final runtime.

Lu: The big picture is that they're using structural properties of cactus graphs to design a dynamic programming approach over connected vertex sets that proves Theorem three > <ref:2603.27655#pg1>

Meng: From my side, I just see the result as an exact solution for finding the maximum spanning cactus subgraph in time O star three n squared time.

Lalam: I’m sure this paper is going to be a very useful reference for anyone interested in graph modification problems because it provides a concrete, improved complexity bounds.

Tom: It’s a solid contribution to the field of finding better ways to solve hard problems exactly. We're done with this paper, and now we move on to what else is interesting out there >

Sheikh Shakil Akhtar, Geevarghese Philip

Chennai Mathematical Institute, Chennai, India

cs.DS, cs.CC, cs.DM, math.CO

Submitted: 2026-03-29

Updated: 2026-11-16

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 90/100

The gist: Exact Algorithms for Edge Deletion to Cactus studies two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus.

Key concepts

Edge Deletion to Cactus
This problem asks for the smallest set of edges to remove from a graph so that the remaining connected structure is a cactus. A cactus is a graph where any two simple cycles share at most one vertex, meaning cycles are mostly independent.
Spanning Tree to Cactus
This problem seeks the largest set of non-tree edges that can be added to an existing spanning tree to form a spanning cactus. Solving this in polynomial time is crucial because it provides a black box for finding an exact solution to the edge deletion problem.
Dynamic Programming over Connected Vertex Sets
This technique is used to find the maximum size of a spanning cactus subgraph. It works by defining values based on subsets of vertices (X) and recursively computing optimal solutions by considering how to split these sets into smaller connected parts, leading to an improved O(3^n) time complexity.
Edge-Minimal Non-Cactus Graph Properties
These structural properties describe graphs that are 'just barely' not cacti. They establish relationships between cycles and edges, ensuring that any two edges in such a graph are contained within a shared cycle, which is essential for the dynamic programming approach.

Terminology

Summary

Exact Algorithms for Edge Deletion to Cactus studies two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. p. 0

Where the paper says it

Exact Algorithms for Edge Deletion to Cactus Sheikh Shakil Akhtar and Geevarghese Philip Chennai Mathematical Institute, Chennai, India Abstract. We study two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus .

Our first main result is that Spanning Tree to Cactus can be solved in polynomial time. p. 0
Where the paper says it

, 2024) posed the complexity of Spanning Tree to Cactus as an open problem. Our first main result is that Spanning Tree to Cactus can be solved in polynomial time.

We use the polynomial-time algorithm for Spanning Tree to Cactus as a black box to obtain an exact algorithm that solves Edge Deletion to Cactus in O⋆(n(n-2)) time. p. 0
Where the paper says it

Our first main result is that Spanning Tree to Cactus can be solved in polynomial time. We use the polynomial-time algorithm for Spanning Tree to Cactus as a black box to obtain an exact algorithm that solves Edge Deletion to Cactus in O ⋆ ( n n − 2 ) time, where n is the number of vertices in the input graph and the O ⋆ () notation hides polynomial factors.

We further improve the running time for Edge Deletion to Cactus to O⋆(3 n) using dynamic programming, which is our second main result. p. 0
Where the paper says it

This is a significant improvement over the brute-force algorithm for Edge Deletion to Cactus that enumerates all subsets of the edge set. We further improve the running time for Edge Deletion to Cactus to O⋆ (3 n ) using dynamic programming; this is our second main result.

Problem Definitions and Context

The paper investigates two edge modification problems aimed at transforming a connected graph into a cactus by deleting or selecting edges. Edge Deletion to Cactus asks for the size of a minimum sized set F ⊆ E such that H = (V, E - F) is a connected cactus subgraph of G. p. 1

Where the paper says it

Edge Deletion To Cactus Input: A simple, undirected connected graph G = (V, E). Question: Find the size of a minimum sized set F ⊆ E such that H = (V, E \ F) is a connected cactus subgraph of G.

Spanning Tree to Cactus asks for the maximum size of a set F ⊆ E(T) such that H = (V, E(T) ∪ F) is a spanning cactus subgraph of G. p. 0
Where the paper says it

Spanning Tree To Cactus Input: A simple, undirected connected graph G = (V, E) and a spanning tree T of G . Question: Find the maximum size of a set F ⊆ E \ E ( T) such that H = (V, E ( T ) ∪ F) is a spanning cactus subgraph of G .

The computational complexity of Edge Deletion to Cactus was first investigated by El-Mallah and Coulborn [5]. p. 1
Where the paper says it

Several results in this direction are known [13,2,11,1]. The computational complexity of Edge Deletion to Cactus was first investigated by El-Mallah and Coulborn [5], who proved that the problem is NP-complete for general graphs.

Polynomial Time Solution for Spanning Tree to Cactus

The authors design a polynomial-time algorithm for Spanning Tree to Cactus based on a reduction to the Maximum Independent Set problem on Edge Path Tree (EPT) graphs [7,6,12]. This involves constructing an auxiliary intersection graph of the unique paths between the endpoints of the non-tree edges. p. 1

Where the paper says it

There exists a polynomial-time algorithm that solves Spanning Tree to Cactus. This algorithm is based on a reduction to the Maximum Independent Set problem on Edge Path Tree (EPT) graphs [7,6,12], obtained by constructing an auxiliary intersection graph of the unique paths between the endpoints of the non-tree edges.

By combining this routine with enumeration over all spanning trees of G, they obtain an exact algorithm for Edge Deletion to Cactus in time O⋆(n(n-2)). p. 1
Where the paper says it

This algorithm is based on a reduction to the Maximum Independent Set problem on Edge Path Tree (EPT) graphs [7,6,12], obtained by constructing an auxiliary intersection graph of the unique paths between the endpoints of the non-tree edges. By combining this polynomial-time routine with enumeration over all spanning trees of G, we obtain our first exact algorithm for Edge Deletion to Cactus.

Improved Exact Algorithm via Dynamic Programming

The second main result is an improved running time for Edge Deletion to Cactus to O⋆(3 n) using dynamic programming. This algorithm computes the size of a maximum-sized spanning cactus subgraph by defining values I(X) over connected vertex sets X. p. 7

Where the paper says it

We now proceed with the design of the algorithm to find the maximum sized spanning cactus subgraph of a connected graph. For every set X such that G[X] is connected and |X| ≤ 5, we compute I(X) and all values JX[x, A] (whenever they are defined) by brute force.

The procedure FindMaxCactus considers all choices of a cut vertex x ∈ X and partitions the remaining vertices into two non-empty sets A and B, calculating JX[x, A]. p. 7
Where the paper says it

Before describing the algorithm for this case, we need to establish some structural properties of cactus graphs that will be used in the design of the algorithm. Any connected non-cactus graph, with at least five vertices, must have a maximum sized spanning cactus subgraph with a cut vertex.

Structural Properties for Dynamic Programming

The dynamic programming approach relies on several structural properties of cactus graphs. Key structural observations include Theorem 4, which states that for an edge-minimal non-cactus connected graph, any two edges e1 and e2 are contained in a cycle C. p. 3

Where the paper says it

Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2. An edge-minimal non-cactus graph with two marked edges e1 and e2, such that there exists a cycle which contains both e1 and e2, as claimed in Theorem 4 The following theorem establishes a key structural property that is central to the design of our algorithm.

Furthermore, Lemma 9 shows that if E(G) = E(P1) ∪ E(P2) for distinct paths P1 and P2 between x and y, then every edge of G lies in a cycle. p. 4
Where the paper says it

Moreover, it is connected and every edge belongs either to P˜ or to P1, which are two distinct paths between a1 and b1. By Lemma 10, every edge in E(P˜)∆E(P1) lies in a cycle.

Conclusion and Future Directions

The paper establishes an exact algorithm for Edge Deletion to Cactus running in time O⋆(3n). This result is achieved by solving the problem of finding the size of a maximum spanning cactus subgraph using dynamic programming. p. 6

Where the paper says it

4 A Faster Exact Algorithm In this section, we prove Theorem 3 and thereby obtain, using dynamic programming, an improved algorithm for Edge Deletion to Cactus with running time O⋆ (3n). We observe that solving the above problem is equivalent to finding the size of a maximum-sized spanning cactus subgraph of G.

Future research directions include the parameterized version of Edge Deletion to Cactus, where FPT algorithms are sought based on treewidth. p. 0
Where the paper says it

Exact Algorithms for Edge Deletion to Cactus Sheikh Shakil Akhtar and Geevarghese Philip Chennai Mathematical Institute, Chennai, India Abstract. We study two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus .

Weighted variants and extensions to related graph modification problems are also suggested. p. 0
Where the paper says it

Cactus graphs form a natural generalisation of trees and arise in several areas of graph theory, network design, and algorithmic graph modification problems [8,3]. In this paper, we study two closely related edge modification problems whose objective is to transform a given connected graph into a cactus by deleting or selecting edges.

References

  1. Aoike, Y., Gima, T., Hanaka, T., Kiyomi, M., Kobayashi, Y., Kobayashi Y., Kurita K., Otachi Y.: An improved deterministic parameterized algorithm for cactus vertex deletion. p. 6

    Where the paper says it

    This yields an algorithm for Edge Deletion to Cactus with running time O⋆ (n n−2 ). 4 A Faster Exact Algorithm In this section, we prove Theorem 3 and thereby obtain, using dynamic programming, an improved algorithm for Edge Deletion to Cactus with running time O⋆ (3n).

  2. Bonnet, E., Brettell, N., Kwon, O.j., Marx, D.: Parameterized vertex deletion problems for hereditary graph classes with a block property. p. 1

    Where the paper says it

    Such problems have been extensively studied for graph classes including forests, interval graphs, chordal graphs, and planar graphs. A closely related problem is Vertex Deletion to Cactus, which asks for a minimum-sized set of vertices whose removal transforms the input graph into a cactus.

  3. Brimkov, B., Hicks, I.V.: Memory efficient algorithms for cactus graphs and block graphs. p. 0

    Where the paper says it

    Exact Algorithms for Edge Deletion to Cactus Sheikh Shakil Akhtar and Geevarghese Philip Chennai Mathematical Institute, Chennai, India Abstract. We study two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus .

  4. Courcelle, B., Engelfriet, J.: Graph structure and monadic second-order logic. p. 8

    Where the paper says it

    The next two theorems capture the additive behaviour of optimal cactus subgraphs when a connected graph is decomposed at a cut vertex. When such a decomposition separates the graph into two connected parts, any maximal cactus structure respecting this separation consists of optimal cactus subgraphs on each part, and its size is the sum of their sizes.

  5. El-Mallah, E. p. 1

    Where the paper says it

    Several results in this direction are known [13,2,11,1]. The computational complexity of Edge Deletion to Cactus was first investigated by El-Mallah and Coulborn [5], who proved that the problem is NP-complete for general graphs.

    , Colbourn, C.: The complexity of some edge deletion problems. p. 0
    Where the paper says it

    In their recent work where they showed—inter alia—that Edge Deletion to Cactus is NP-hard even when restricted to bipartite graphs, Koch et al. , 2024) posed the complexity of Spanning Tree to Cactus as an open problem.

  6. Golumbic, M. p. 2

    Where the paper says it

    A block of a graph is a maximal biconnected subgraph. We now define Edge Path Tree (EPT) graphs following Golumbic and Jamison [7,6].

    p. 2
    Where the paper says it

    A block of a graph is a maximal biconnected subgraph. We now define Edge Path Tree (EPT) graphs following Golumbic and Jamison [7,6].

    C., Jamison, R. p. 2
    Where the paper says it

    A block of a graph is a maximal biconnected subgraph. We now define Edge Path Tree (EPT) graphs following Golumbic and Jamison [7,6].

    p. 2
    Where the paper says it

    A block of a graph is a maximal biconnected subgraph. We now define Edge Path Tree (EPT) graphs following Golumbic and Jamison [7,6].

    E.: Edge and vertex intersection of paths in a tree. p. 2
    Where the paper says it

    Let T be a tree, and let P be a collection of nontrivial simple paths in T; that is, each path in P contains at least one edge. We define the edge intersection graph of P in T, denoted by Γ(P, T), as the graph whose vertex set corresponds to the elements of P, with two vertices joined by an edge if and only if their corresponding paths share at least one edge in T.

  7. Golumbic, M.C., Jamison, R.E.: The edge intersection graphs of paths in a tree. p. 1

    Where the paper says it

    There exists a polynomial-time algorithm that solves Spanning Tree to Cactus. This algorithm is based on a reduction to the Maximum Independent Set problem on Edge Path Tree (EPT) graphs [7,6,12], obtained by constructing an auxiliary intersection graph of the unique paths between the endpoints of the non-tree edges.

  8. Harary, F., Uhlenbeck, G.E.: On the number of husimi trees. p. 5

    Where the paper says it

    Using any existing algorithm to enumerate all possible spanning tree of the graph G (input to Edge Deletion To Cactus), we call the above algorithm for each spanning tree of G and return the overall maximum value reported. Winter [14], provides an O⋆ (τ (G)) time algorithm for enumerating all spanning tree of a graph G, where τ (G) is number of spanning trees of a graph

  9. Hopcroft, J. p. 0

    Where the paper says it

    Another equivalent characterization is that every block (biconnected component) of the graph is either a single edge or a simple cycle. This characterization implies that cactus graphs can be recognized in polynomial time using a block decomposition algorithm, such as the classical linear-time algorithm for computing biconnected components by Hopcroft and Tarjan [ 9].

    , Tarjan, R. p. 0
    Where the paper says it

    Another equivalent characterization is that every block (biconnected component) of the graph is either a single edge or a simple cycle. This characterization implies that cactus graphs can be recognized in polynomial time using a block decomposition algorithm, such as the classical linear-time algorithm for computing biconnected components by Hopcroft and Tarjan [ 9].

    : Algorithm 447: efficient algorithms for graph manipulation. p. 5
    Where the paper says it

    Observe that the above algorithm can be used to design another algorithm for Edge Deletion To Cactus, although not as efficient as the one from Theorem 3. Using any existing algorithm to enumerate all possible spanning tree of the graph G (input to Edge Deletion To Cactus), we call the above algorithm for each spanning tree of G and return the overall maximum value reported.

  10. Koch, I., Pardal, N., dos Santos, V.F.: Edge deletion to tree-like graph classes. p. 1

    Where the paper says it

    The second problem, Edge Deletion to Cactus, belongs to the broad class of graph modification problems, in which the goal is to transform a given graph into a graph belonging to a specified class using a minimum number of edits. Such problems have been extensively studied for graph classes including forests, interval graphs, chordal graphs, and planar graphs.

  11. Misra, P., Raman, V., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms for even cycle transversal. p. 0

    Where the paper says it

    Exact Algorithms for Edge Deletion to Cactus Sheikh Shakil Akhtar and Geevarghese Philip Chennai Mathematical Institute, Chennai, India Abstract. We study two related problems on simple, undirected graphs: Edge Deletion to Cactus and Spanning Tree to Cactus .

  12. Tarjan, R.E.: Decomposition by clique separators. p. 0

    Where the paper says it

    Another equivalent characterization is that every block (biconnected component) of the graph is either a single edge or a simple cycle. This characterization implies that cactus graphs can be recognized in polynomial time using a block decomposition algorithm, such as the classical linear-time algorithm for computing biconnected components by Hopcroft and Tarjan [ 9].

  13. Tsur, D.: Faster deterministic algorithm for cactus vertex deletion. p. 6

    Where the paper says it

    This yields an algorithm for Edge Deletion to Cactus with running time O⋆ (n n−2 ). 4 A Faster Exact Algorithm In this section, we prove Theorem 3 and thereby obtain, using dynamic programming, an improved algorithm for Edge Deletion to Cactus with running time O⋆ (3n).

  14. Winter, P.: An algorithm for the enumeration of spanning trees. p. 1

    Where the paper says it

    This algorithm is based on a reduction to the Maximum Independent Set problem on Edge Path Tree (EPT) graphs [7,6,12], obtained by constructing an auxiliary intersection graph of the unique paths between the endpoints of the non-tree edges. By combining this polynomial-time routine with enumeration over all spanning trees of G, we obtain our first exact algorithm for Edge Deletion to Cactus.

Appendix A Properties of Edge Minimal Cacti

Theorem 4. Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. p. 3

Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2. p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

Lemma 5. Let G = (V, E) contain two distinct cycles C1 and C2 that share at least one edge. p. 3

Where the paper says it

Suppose first that there exist two edges in Eˆ, say e ′ 1 and e ′ 2 , such that the unique paths between their respective endpoints in T, denoted by P ′ 1 and P ′ 2 , share at least one edge. Then H contains two distinct cycles, namely P ′ 1 ∪ e ′ 1 and P ′ 2 ∪ e ′ 2 , that share an edge, and hence H is not a cactus.

Then there exists a third cycle that is distinct from both C1 and C2. p. 4
Where the paper says it

Moreover, it is connected and every edge belongs either to P˜ or to P1, which are two distinct paths between a1 and b1. By Lemma 10, every edge in E(P˜)∆E(P1) lies in a cycle.

Lemma 6. Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Let C1 and C2 be two cycles in G that share at least one edge. p. 3

Where the paper says it

Suppose first that there exist two edges in Eˆ, say e ′ 1 and e ′ 2 , such that the unique paths between their respective endpoints in T, denoted by P ′ 1 and P ′ 2 , share at least one edge. Then H contains two distinct cycles, namely P ′ 1 ∪ e ′ 1 and P ′ 2 ∪ e ′ 2 , that share an edge, and hence H is not a cactus.

p. 3
Where the paper says it

Suppose first that there exist two edges in Eˆ, say e ′ 1 and e ′ 2 , such that the unique paths between their respective endpoints in T, denoted by P ′ 1 and P ′ 2 , share at least one edge. Then H contains two distinct cycles, namely P ′ 1 ∪ e ′ 1 and P ′ 2 ∪ e ′ 2 , that share an edge, and hence H is not a cactus.

Then E ⊆ E(C1) ∪ E(C2).

Lemma 7. Let G = (V, E) be an edge-minimal non-cactus connected graph. p. 3

Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

Let C1 and C2 be two cycles in G that share at least one edge. Then, for every cycle C of G, we have E(C) ∩ E(C1)! p. 0
Where the paper says it

To the best of our knowledge, this is the fastest known exact-exponential algorithm for Edge Deletion to Cactus . 1 Introduction A cactus graph is a connected graph in which every edge belongs to at most one cycle.

= ∅.

Lemma 8. Let G = (V, E) be an edge-minimal non-cactus connected graph. Let C1 and C2 be two cycles in G such that E(C1) ∩ E(C2)! p. 8

Where the paper says it

Intuitively, every cycle in the resulting graph remains entirely within one of the original cacti, and therefore no two cycles can share an edge. Let C and C ′ be two edge-disjoint cacti, such that V (C)∩V (C ′ ) = {v}.

= ∅, and let C3 be a distinct cycle in G. p. 4
Where the paper says it

Moreover, it is connected and every edge belongs either to P˜ or to P1, which are two distinct paths between a1 and b1. By Lemma 10, every edge in E(P˜)∆E(P1) lies in a cycle.

Then E(C1)∆E(C2) ⊆ E(C3).

Theorem 4. Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

Lemma 9. Let G be a connected graph. p. 3

Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

p. 3
Where the paper says it

Let G = (V, E) be an edge-minimal non-cactus connected graph; that is, for every e ∈ E, the graph G − e is a cactus. Then, for any two edges e1 = a1b1 and e2 = a2b2, there exists a cycle C in G that contains both e1 and e2.

Suppose that there exists distinct vertices x, y ∈ V (G) and two distinct edge-disjoint paths P1 and P2 with endpoints x and y such that E(G) = E(P1) ∪ E(P2). p. 3
Where the paper says it

Suppose first that there exist two edges in Eˆ, say e ′ 1 and e ′ 2 , such that the unique paths between their respective endpoints in T, denoted by P ′ 1 and P ′ 2 , share at least one edge. Then H contains two distinct cycles, namely P ′ 1 ∪ e ′ 1 and P ′ 2 ∪ e ′ 2 , that share an edge, and hence H is not a cactus.

Then every edge of G lies in a cycle. p. 4
Where the paper says it

Moreover, it is connected and every edge belongs either to P˜ or to P1, which are two distinct paths between a1 and b1. By Lemma 10, every edge in E(P˜)∆E(P1) lies in a cycle.

Lemma 10. Let G be a connected graph. Suppose there exist distinct vertices x, y ∈ V (G) and two distinct paths P1 and P2 with endpoints x and y such that E(G) = E(P1) ∪ E(P2). p. 3

Where the paper says it

Suppose first that there exist two edges in Eˆ, say e ′ 1 and e ′ 2 , such that the unique paths between their respective endpoints in T, denoted by P ′ 1 and P ′ 2 , share at least one edge. Then H contains two distinct cycles, namely P ′ 1 ∪ e ′ 1 and P ′ 2 ∪ e ′ 2 , that share an edge, and hence H is not a cactus.

Then every edge of G that belongs to E(P1)∆E(P2) lies in a cycle. p. 4
Where the paper says it

Moreover, it is connected and every edge belongs either to P˜ or to P1, which are two distinct paths between a1 and b1. By Lemma 10, every edge in E(P˜)∆E(P1) lies in a cycle.

Lemma 11. Let H = (V, E) be a connected graph, and let x ∈ V be a vertex such that degH(x) >= 2. p. 7

Where the paper says it

Otherwise it is a simple cycle, and since the original graph is not a cactus, we can swap in a non-cycle edge and remove a cycle edge to obtain another spanning cactus of the same size that now has a cut vertex. Let H = (V, E) be a connected graph that is not a cactus, and assume that |V | ≥ 5.

Let A ⊆ V - x be nonempty, and set B:= V - (A ∪ x), with B also nonempty. p. 9
Where the paper says it

Let G = (V, E) be a connected graph, and let X ⊆ V be such that |X| > 5 and G[X] is connected. Let x ∈ X satisfy degG[X] (x) ≥ 2, and let A ⊆ X \ {x} be a nonempty set.

Suppose that both H[A U x] and H[B U x] are connected. p. 7
Where the paper says it

Suppose that B is also nonempty and that both G[A ∪ {x}] and G[B ∪ {x}] are connected. We then define JX[x, A] by JX[x, A] := max |E(C)| C is a spanning connected subgraph of G[X], x is a cut vertex of C, C[A ∪ {x}] and C[B ∪ {x}] are cacti .

Then there exists a spanning connected subgraph of H, say T, such that x is one of the cut vertices of T, and such that both T[A U x] and T[B U x] are cacti. p. 7
Where the paper says it

Any connected non-cactus graph, with at least five vertices, must have a maximum sized spanning cactus subgraph with a cut vertex. If a maximum spanning cactus already has more than one block, then it necessarily has a cut vertex.

C.1 The Dynamic Programming Algorithm

Algorithm 2 FindMaxCactus(X) computes the contribution of a decomposition of X into the two vertex sets A ∪ x and B ∪ x, where B:= X - (A U x), under the assumption that both induced subgraphs G[A U x] and G[B U x] are connected. Algorithm 3 FindCutCactus(x, A, X) computes the maximum size of a spanning subgraph obtained by joining optimal cactus subgraphs of G[A U x] and G[B U x] at the common vertex x. p. 6

Where the paper says it

Consequently, if we execute Algorithm 1 for every spanning tree of G and select the largest value obtained, we recover the size of a maximum spanning cactus subgraph of G, namely |E(H)|. The number of spanning trees of an n-vertex graph is at most n n−2 .

Theorem 8. Let G = (V, E) be a graph with n:= V. p. 2
Where the paper says it

All graphs considered in this paper are simple and undirected. Let G = (V, E) be a graph.

The procedures FindMaxCactus and FindCutCactus compute the values I(X) for all vertex sets X ⊆ V such that G[X] is connected in time O⋆(3n). p. 7
Where the paper says it

We now proceed with the design of the algorithm to find the maximum sized spanning cactus subgraph of a connected graph. For every set X such that G[X] is connected and |X| ≤ 5, we compute I(X) and all values JX[x, A] (whenever they are defined) by brute force.

Algorithm 1 SpanningTreeToCactus

Algorithm 1 runs in polynomial time by constructing an auxiliary graph AT and computing a maximum independent set of AT, which yields an O⋆(n(n-2)) algorithm for Edge Deletion to Cactus. This is improved to O⋆(3 n) using dynamic programming. p. 6

Where the paper says it

This yields an algorithm for Edge Deletion to Cactus with running time O⋆ (n n−2 ). 4 A Faster Exact Algorithm In this section, we prove Theorem 3 and thereby obtain, using dynamic programming, an improved algorithm for Edge Deletion to Cactus with running time O⋆ (3n).

The overall running time of the combined execution of FindMaxCactus and FindCutCactus runs in time O⋆(3n). p. 6
Where the paper says it

The number of spanning trees of an n-vertex graph is at most n n−2 . Since Algorithm 1 runs in polynomial time for each spanning tree, the overall running time is O⋆ (n n−2 ).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved algorithm for Edge Deletion to Cactus running in time O⋆(3n). This allows AI systems to efficiently solve NP-hard graph modification problems by finding a maximum sized spanning cactus subgraph using dynamic programming over connected vertex subsets.

  2. Polynomial time algorithm for Spanning Tree to Cactus problem. The ability to find the maximum size of a set F such that H = (V, E(T) ∪ F) is a spanning cactus subgraph of G in polynomial time enables AI systems to optimize graph structures by selecting non-tree edges based on an auxiliary EPT graph construction and maximum independent set computation.

  3. Alternative exact algorithm for Edge Deletion to Cactus running in time O⋆(n 2). This provides a practical, though less efficient, method for solving the problem by enumerating all spanning trees and applying the polynomial-time algorithm from Spanning Tree to Cactus for each tree.

Abstract

We study two related problems on simple, un-directed graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general graphs at least since 1988. We show improved exact algorithms for the former and a polynomial time algorithm for the latter.

Related papers