4

I have a directed graph (more specifically, a control flow graph), and each of the vertices has a set of properties.

I'd like to find (or write) an algorithm that, given a vertex V with property P, finds the longest path to some vertex E such that all vertices along all possible paths from V to E contain the property P.

Example 1

Say I had the following graph. (Please excuse the bad ascii drawing.)

                    +----+            
           +--------+P   +--------+   
           |        +----+        |   
           |         V1           |   
           |                      |   
           |                      |   
        +--v--+                   |   
   +----+P    ++                  |   
   |    +-----++               +--v--+
   |           |          +----+P    |
   |           |          |    +-----+
+--v--+     +--v--+       |           
|P    +-+ +-+P    |       |           
+-----+ | | +-----+       |           
        | |               |           
        | |               |           
       +v-v--+            |           
  V6   |P    +---------+  |           
       +-----+         |  |           
                       |  |           
                       |  |           
                       |  |           
                       |  |           
                     +-v--v-+         
                V7   |P     |         
                     +---+--+         
                         |            
                         |            
                     +---v--+         
                V8   |!P    |         
                     +------+

Starting at V1, the longest path where P always holds on all possible paths is V1 -> V7. Note that the other paths, say V1 -> V6, are "valid" in that P always holds, but V1 -> V7 is the longest.

Example 2

This example is the same as above, except now the P doesn't hold in V3:

                    +----+            
           +--------+P   +--------+   
           |        +----+        |   
           |         V1           |   
           |                      |   
           |                      |   
        +--v--+                   |   
   +----+P    ++                  |   
   |    +-----++               +--v--+
   |           |          +----+!P   |  V3
   |           |          |    +-----+
+--v--+     +--v--+       |           
|P    +-+ +-+P    |       |           
+-----+ | | +-----+       |           
        | |               |           
        | |               |           
       +v-v--+            |           
  V6   |P    +---------+  |           
       +-----+         |  |           
                       |  |           
                       |  |           
                       |  |           
                       |  |           
                     +-v--v-+         
                V7   |P     |         
                     +---+--+         
                         |            
                         |            
                     +---v--+         
                V8   |!P    |         
                     +------+

In this case, starting at V1, the longest path where P always holds in all possible paths is V1 -> V6. The path V1 -> V7 is not valid, because there is a path between V1 and V7 in which P does not hold.

Further notes about my situation

  • The graph could be cyclic.
  • The graph will be of a "small to medium" size, with maybe 1000 vertices or less.
  • The graph does not necessarily always have one root and one leaf, like my examples above.

Question

Is there a standard algorithm for computing such paths?

stepthom
  • 1,432
  • 2
  • 16
  • 27
  • I'm a bit confused by your second example. Do you say there that you want the longest path from vertex `S` to some vertex `E` such that `P` holds on *all* vertices on *all* paths between `S` and `E`? That seems a very strict constraint... – Vincent van der Weele Sep 17 '14 at 13:56
  • What about the edge v6 -> v7? Won't that make the path to v7 the longest? – Abhishek Bansal Sep 17 '14 at 13:58
  • 1
    The problem has no simple solution, as it is easily reduceable from Hamiltonian Path Problem. (Given Hamiltonian Path problem, label all nodes with `p`, and find longest path). Since Hamiltonian path is NP-Complete, so is this problem, and there is no known polynomial solution to it. – amit Sep 17 '14 at 14:24
  • @VincentvanderWeele: Yes, what you said is the (admittedly strict) constraint I'm after. – stepthom Sep 17 '14 at 14:44
  • @doofuslarge Can you clarify: - Is the start vertex always a fixed detail? - Does the graph always have one root and one leaf? - Is the graph always acyclic? – Christian Convey Sep 17 '14 at 14:45
  • @user1990169: I assume you are referring to Example 2. In that case, `V7` is not "valid" because there is a path from `V1` to `V7` where `P` does not hold, namely the path containing `V3`. – stepthom Sep 17 '14 at 14:45
  • @ChristianConvey: Question updated with more detail. – stepthom Sep 17 '14 at 15:02
  • For every vertex v that does not hold the property P set all its adjacent edges' weights to -infinity. Then use a known algorithm to find the longest path. If your resulting path has length = -infinity it means that there is no path from v to e such that the constraint is satisfied. – Enrique Sep 17 '14 at 15:48
  • Does the path have to be simple (i.e., doesn't repeat any vertices)? – David Eisenstat Sep 17 '14 at 16:54
  • @DavidEisenstat Yes, the path has to be simple. – stepthom Sep 18 '14 at 20:12

1 Answers1

3

The problem has no known efficient solution, as it is easily reduceable from Hamiltonian Path Problem, which says - given a graph - is there a path that goes through all vertices exactly once?

The reduction is simple - Given Hamiltonian Path problem, label all nodes with p, and find longest path. Since Hamiltonian path is NP-Complete, so is this problem, and there is no known polynomial solution to it.

An alternative is using a brute-force search (simplest form is generate all permutations and chose the best valid one) - but that will become impossible for large graphs. You might also need to consider using a heuristic approach (that finds a "good" solution, but not the optimal), like Genetic Algorithms.
Another possible solution is to reduce the problem to a Traveling Salesman Problem, and use some existing TSP solver. Note that while this problem is also NP-hard, since it is well-studied, there are some pretty efficient solutions for medium size graphs.

Also, if your graph happens to be somehow 'special' (a DAG for example), you might utilize some smart techniques to achieve significant speed up to polynomial time, like Dynamic Programming.

amit
  • 175,853
  • 27
  • 231
  • 333
  • The brute-force search seems like it might work for me in my case, since the graphs I'm dealing with are usually small. How would it work, exactly? Would I just do a breadth-first search on the graph to generate all possible paths from the starting node `V` to all nodes reachable from `V`, and then discard those paths that have a vertex where `P` doesn't hold, and then sort the remaining paths by length? – stepthom Sep 17 '14 at 14:57
  • @doofuslarge One solution is using a Depth-First-Search, with a dynamic 'visited' set. This set will remember only the vertices visited in the current path, and whenever you backtrack - remove the last vertex from the set. – amit Sep 17 '14 at 15:14
  • I ended up implementing a brute-force algorithm for my problem, which seems to work OK for my smaller graphs. – stepthom Sep 25 '14 at 12:44