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?

Answer 1

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.