Positive topological ordering, take 2

Question

This is a followup to David Eppstein's recent question and is motivated by the same problems.

Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are unmarked. I can change the set of marked vertices by either (1) marking a vertex with no unmarked predecessors, or (2) unmarking a vertex with no marked successors. (Thus, the set of marked vertices is always a prefix of the partial order.) I want to find a sequence of marking/unmarking operations that ends with all vertices marked, such that the total weight of the marked vertices is always non-negative.

• How hard is finding such a sequence of operations? Unlike David's problem, it's not even clear that this problem is in NP; in principle (although I don't have any examples) every legal move sequence could have exponential length. The best I can prove is that the problem is in PSPACE.

• Is the unmarking operation actually unnecessary? If there is a valid move sequence, must there be a valid move sequence that never unmarks a vertex? An affirmative answer would make this problem identical to David's. On the other hand, if unmarking is sometimes necessary, there should be a small (constant size) example that proves it.

Answer 1

On our regular 666 research seminar we came up with the following proof.

We start with some definitions. Let P be our poset. For simplicity, suppose that none of the weights sum up to zero. Denote the weight of a vertex by w(x) and the sum of the weights of a set by w(X). We say that a set X is Y-up (closed) if it is contained in Y and every element of Y that is bigger than an element of X is also in X. Similarly, say that a set X is Y-down if it is contained in Y and every element of Y that is smaller than an element of X is also in X. In this language the set of marked elements must be always P-down.

We prove by contradiction. Take the shortest mark/unmark sequence that marks every element. We call such sequences full. At any given point, consider the set of elements that were marked before but are now unmarked. Denote this set by U.

Claim: w(U)>0.

Proof: We prove that the weight of any U-up set, X, is positive. The proof is by induction on the size of X. If there is an X-down set, Y, such that w(Y)>0, then since by induction we know that w(X\Y)>0 (since it is X-up), we also have w(X)>0. If for every X-down set, Y, we have w(Y)<0, then by deleting up to this point all the markings and unmarkings of the elements of X from our sequence, we get a shorter full sequence. We are done with the proof of the claim.

Now suppose that we have a full sequence where w(U)>0 at any point for the set U of currently unmarked elements. Take the sequence that we obtain from this by taking the first marking of every element and never unmarking anything. It is clear that this will also be a full sequence satisfying that the set of marked elements is always P-down. Moreover, the sum of the weights will be always at least as much as in the original sequence since at any given time the difference is w(U). We are done.

With this method one can even prove that if instead of marking the whole of P, we only want to mark a subset of P, then it can be done with a sequence of markings followed by a sequence of unmarkings. The proof is the same except that at the end some elements, U, stay unmarked but these can be moved to the end of the sequence as the weight of any U-up set is positive.