4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is your graph directed or undirected? $\endgroup$ – Richard Jul 19 at 16:04
  • $\begingroup$ It is undirected. $\endgroup$ – Cianotico Jul 19 at 16:48
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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
$\endgroup$
  • 5
    $\begingroup$ Surely an algorithm that finds all cycles has exponential complexity. $\endgroup$ – Federico Poloni Jul 19 at 18:24
  • 1
    $\begingroup$ Of course. I just took the OP at his word hat he can do that part of the problem. $\endgroup$ – Wolfgang Bangerth Jul 21 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.