30 June 2008

Black and White

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.

3 comments:

Anonymous said...

Looks like a max flow problem to me.

rgrig said...

I'm an idiot. I make many mistakes lately.

Anyway, this problem is not really the problem I have, but a simple version of it. A solution to this one would be somewhat useful too.

@anonymous: Can you explain a little?

Martin Harrigan said...

Compute a topological ordering of the DAG and 'greedily' assign integers from left-to-right?

I would think you could also delete all white vertices and proceed in the same way since every white vertex can 'reset' the numbering.

Or am I missing something?

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.