2

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.

ZeroPepsi
  • 141
  • 3
  • Can you elaborate on the restrictions a bit? – Anmol Singh Jaggi Sep 10 '20 at 12:57
  • 1
    This question is an exact duplicate of [Blocking directed paths on a Cactus Graph](https://stackoverflow.com/questions/63821481/blocking-directed-paths-on-a-cactus-graph). Instead of duplicating a closed question, please improve the original so that it can be reopened and answered. – beaker Sep 10 '20 at 15:30

1 Answers1

1

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.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • Could you elaborate on your observation #2? I can see that you can reduce the first problem into the second one. What about the reverse? – ciamej Sep 10 '20 at 22:10
  • @ciamej Hmm, it's pretty much by definition? I edited Observation 1 slightly to make it more obvious. – David Eisenstat Sep 10 '20 at 23:05
  • Hmm, minimum feedback vertex set asks for the smallest set of nodes whose deletion eliminates all cycles, then within such an acyclic graph we can find the longest path, *but* the path may not cover all vertexes of that graph. On the other hand we may remove a different set of vertexes (not the smallest one), to obtain a different acyclic graph with less vertexes but with a longer path. Or can't we? If not, why? It's not obvious to me... – ciamej Sep 10 '20 at 23:24
  • @ciamej Ah, the notion of "path" here is nonstandard, going by the example answer. – David Eisenstat Sep 10 '20 at 23:58
  • I'm not sure what's the problem with the "path". How is your solution meant to work with a classic path notion? Consider an example of a directed graph with digit 8 shape (a central node connects two loops). By minimum feedback vertex set we have to remove the central node to eliminate all cycles. We end up with two disjoint cut loops. The longest path will be in the remains of one of the loops. But we can do better! Instead, we remove two neighbours of the central node, each one from a different loop, to get an S shaped graph. Now the path may span the entire graph. – ciamej Sep 11 '20 at 08:00
  • @ciamej The question gives (4, 5, 6, 7, 8, 0, 9, 2, 3) as a valid solution for the graph shown even though several of the consecutive vertices are not connected by an arc. – David Eisenstat Sep 11 '20 at 11:03
  • Ah, ok. I haven't analyzed the more complex example. Still, I think your solution is not correct even with regular paths, unless I misunderstood something. – ciamej Sep 11 '20 at 15:02