Exact Algorithms for Edge Deletion to Cactus
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 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
. , 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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
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
. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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
. 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.Where the paper says it
Where the paper says it
Where the paper says it
References
-
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).
-
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.
-
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 .
-
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.
-
El-Mallah, E. p. 1
, Colbourn, C.: The complexity of some edge deletion problems. p. 0Where 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.
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.
-
Golumbic, M. p. 2
p. 2Where 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. 2Where 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. 2Where 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. 2Where 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].
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.
-
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.
-
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
-
Hopcroft, J. p. 0
, Tarjan, R. p. 0Where 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. 5Where 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].
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.
-
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.
-
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 .
-
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].
-
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).
-
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 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 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 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 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Lemma 5. Let G = (V, E) contain two distinct cycles C1 and C2 that share at least one edge. p. 3 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Lemma 7. Let G = (V, E) be an edge-minimal non-cactus connected graph. p. 3 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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}. 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.Where the paper says it
Where the paper says it
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 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 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Lemma 11. Let H = (V, E) be a connected graph, and let x ∈ V be a vertex such that degH(x) >= 2. p. 7 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 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 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
. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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
. All graphs considered in this paper
are simple and undirected. Let G = (V, E) be a graph. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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 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
).Where the paper says it
Where the paper says it
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
-
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.
-
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. -
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles