Hi Ravi:

I was thinking about your algorithm. Do you have time to discuss this before
Wednesday?

-- Karl

Ravi's strategy minimization algorithm

We start with a class graph G = (V,E) and a 
strategy graph S = (V', E') where V' is a subset 
of V. We consider the strongly connected component
graphs of both G and S calling them H and T.
This reduction allows us to work with dags.

careful: Consider the shortcut graph:
E of G: (A,X) (X,B) (B,X) (X,C)
Strategy graph S : {A -> B B -> C}

H is: (A,B) (B,C)
T is the same as S.

The minimal strategy is {A->C} but this is wrong because
the path A.X.C is not allowed.
end careful.

We can deal with this later and let's assume that class graphs
and strategy graphs are dags.

Ravi constructs the expanded graph from the strategy S, called Exp.
Every edge (s,t) in the strategy is replaced by the graph
corresponding to PathSet[G](s,t). (There is again an
issue with shortcuts or zigzags?)

Instead of using the graph corresponding to the path set,
let's use the path sets? Exp now becomes a graph where
the edges are labeled by path sets. Then we need to solve lots
of questions of the form:

PathSet[Exp](s,t) = PathSet[G](s,t) where Exp is a 
graph where the edges are labeled by path sets.
G is the class graph.

If PathSet[Exp](s,t) = PathSet[G](s,t) holds, we introduce
a red edge (s,t). We do this for all pairs of nodes in Exp.
From the red edges we derive the minimal strategy using
an algorithm Ravi has in mind. (all disjoint shortest paths?)

What is the complexity of PathSet[Exp](s,t) = PathSet[G](s,t)?
Path sets are regular expressions. How big are those regular expressions?
Regular expression inequivalence is PSPACE complete.
Do our regular expressions have special properties that 
allow for a polynomial check? Those special properties might have to
do with DAGs.

The algorithm Ravi suggested is useful to simplify startegies
by looking for the pattern {A -> B B -> C} and check
whther it can be replaced by {A -> C}. 

But the running time of those algorithms remains open.
There is also the issue of generality in the presence
of shortcuts and zigzags.

-- Karl