Alright, here's a question for the programming geniuses among you:
I have a digraph (directed graph) whose edges have color (you can think of it as an integer label). I want to compute a sequence S of edge colors, such that the number of strongly-connected components in the graph under edge colors S[0...i], for each i, forms the longest and slowest strictly-decreasing sequence.
For example, suppose the graph has black, red, and blue edges. Suppose we pick the sequence of colors [black, red, blue]. Then we compute the number of strongly-connected components firstly under black edges (say we get 50 SCCs), then under both black and red edges (say we get 40 SCCs), and then under black, red, and blue edges (say we get 20 SCCs). I want to find the sequences of colors such that the reduction in the number of SCCs in each step is the smallest possible.
What's the most efficient algorithm for computing this sequence?