Restricting directed paths on a Cactus Graph

user_3197444 0
Viewed 105

I want to find the longest path distance on a cactus graph with certain restricting directed paths.

For example, if we have following 4 nodes, enter image description here

This would mean that

  • if we visit 1, we cannot go to 2 anymore

That is, 1 → 2 and 1 → 3 → 2 are not allowed. However, 2 → 1 is allowed.

Likewise

  • cannot travel from 2 to 3

  • cannot travel from 3 to 1

  • cannot travel from 1 to 0

  • can travel any others

So we have the probable paths (1, 3, 2), (0, 2, 1), and so on. Therefore the longest distance is 3, and we never get 4.

enter image description here

In this case, the answer is 9. (4, 5, 6, 7, 8, 0, 9, 2, 3), etc...

I’m stuck on this problem one week. Still, I have no idea how to approach. Thanks.

path-finding graph-algorithm graph algorithm
1 Answers

Observation 1: there exists a path* on a set of nodes if and only if that set induces a subgraph with no cycles. Proof: if there is a cycle, then we cannot visit all of the nodes of the cycle, because the last one visited is forbidden by the node preceding it in the cycle. If there is no cycle, then reverse all of the arcs in the subgraph and find a topological order.

Observation 2: this problem is equivalent to the classical NP-hard problem minimum feedback vertex set, which asks for the smallest set of nodes whose deletion eliminates all cycles.

There are efficient algorithms for feedback vertex set in cactus graphs claimed, e.g., Das (2012).

* Path seems to be defined in a nonstandard way for this question, as a sequence of nodes with no repetitions such that for each arc in the graph, the head of the arc does not appear after the tail. This is the definition that accords with the solution to the example graph, (4, 5, 6, 7, 8, 0, 9, 2, 3), which has multiple consecutive vertices not connected by an arc.

user_21446690
Related