In a graph, find longest path with a certain property?

Question

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?

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
What about the edge v6 -> v7? Won't that make the path to v7 the longest? — Abhishek Bansal
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
@VincentvanderWeele: Yes, what you said is the (admittedly strict) constraint I'm after. — stepthom
@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

amit amit · Accepted Answer · 2014-09-17T14:29:15

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.