Positive topological ordering Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of the weights is non-negative. Or if you prefer order-theoretic terminology, I have a weighted partial order and I want a linear extension such that each prefix has non-negative weight. What is known about this problem? Is it NP-complete or solvable in polynomial time?
This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in Garey &amp; Johnson. To wit:


  INSTANCE: Set $T$ of tasks, partial order $\prec$ on $T$, a "cost" $c(t) \in Z$ for each $t \in T$ (if $c(t) &lt; 0$, it can be viewed as a "profit"), and a constant $K \in Z$. 
  
  QUESTION: Is there a one-processor schedule $\sigma$ for $T$ that obeys the precedence constraints and which has the property that, for every task $t \in T$, the sum of the costs for all tasks $t'$ with $\sigma(t') \leq \sigma(t)$ is at most $K$?


I am uncertain whether the problem remains NP-complete when $K$ is fixed to 0. G&amp;J mention that the problem remains NP-complete if $c(t) \in \{-1,0,1\}$ for all $t \in T$.