Efficient algorithm to decide if a graph is a cactus?

Question

A cactus is a connected graph in which every edge belongs to at most one simple cycle.

How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a given graph is a cactus?

A solution I tried exploring is to detect all the cycles in the graph and then check if there are two "nested" cycles. However I can't determine if a cycle I found at a certain steps starts or ends inside another cycle without checking it against all the cycles I discovered before.

Answer 1

This is a fun question!

After academic searches and Wiki came up bare, I dug through the source code of SageMath. That gets us to this:

#A graph is called *cactus graph* if it is connected and every pair of
simple cycles have at most one common vertex.

# Special cases
if self.order() < 4: #Number of vertices
    return True

# Every cactus graph is outerplanar
if not self.is_circular_planar():
    return False

if not self.is_connected():
    return False

# the number of faces is 1 plus the number of blocks of order > 2
B = self.blocks_and_cut_vertices()[0]
return len(self.faces()) == sum(1 for b in B if len(b) > 2) + 1

Determining whether the graph is connected is an O(N) operation. Just start a DFS at any node, keep the nodes you visit in a hashset, and then check to see that you've visited all of the nodes.

You can check for circular planarity using an O(N) algorithm by Boyer and Myrvold:

John M. Boyer and Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 241-273, 2004.

And blocks and cuts can be found using an O(N) algorithm by Tarjan:

R.E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160 (1972).

You can also accelerate the SageMath implementation by noting that the number of edges in a cactus graph is at most $\lfloor1.5(n-1)\rfloor$ where $n$ is the number of vertices.

Answer 2

If you have an algorithm that finds all cycles, then do the following steps:

• Take cycle 1, tag all edges that are part of it.
• Take cycle 2 and go through all edges that are part of it:
  • If an edge is already tagged, then clearly that edge is part of another cycle and you don't have a cactus
  • Otherwise, tag that edge
• Repeat with cycles 3...n