You are given a dag. Some nodes are white, the others are black. An integer r(n) is attached to each node n. For each edge m->n we have r(n)>=r(m)+[n is black]. The cost of a numbering is the number of edges m->n such that r(n)>r(m)+[n is black]. What's the best algorithm for finding a minimum cost numbering that you can find?
Really, I'm curious: I don't know any good one. I bumped into this while working on FreeBoogie and, although it's probably not terribly important in practice to find an answer, I think it makes a cute puzzle.