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.