<p>Well, my answer is my question from which it turns out that if you could solve this problem in P, you could also solve another open problem:
<a href="https://cstheory.stackexchange.com/questions/1842/positive-topological-ordering-take-3">Positive topological ordering, take 3</a></p>

<p>Edit: This problem also turned out to be NP-complete, so your problem is NP-complete already if your DAG has only two levels, i.e. if there are no directed paths with two edges.</p>

CC BY-SA 2.5
2010-10-01T14:16:37.810Z
2010-11-22T10:23:37.450Z
2017-04-13T12:32:28.080Z
domotorp
<p>If I understand the problem correctly, I think that the precedence constrained single machine scheduling problem to minimize the weighted sum of completion times (1|prec|\sum wc) can be reduced to the problem you are interested. 
In problem 1|prec|\sum wc we have n jobs, each with a non-negative weight and a processing time, a poset on the jobs and we want a linear extension of the jobs such that the weighted sum of jobs completion times is minimized. The problems is NP-complete even though we assume that the processing time of each job is equal to 1. Does it make any sense?</p>

CC BY-SA 2.5
2010-09-16T16:57:39.833Z
It's definitely an interesting possibility. But how do you do the reduction in such a way that the optimization criterion (minimize sum of completion times) gets transformed into constraints (non-negative prefixes)?
David Eppstein
CC BY-SA 2.5
2010-09-16T18:31:51.607Z
I do not know this NP-completeness result of scheduling problem, but I think that it refers to the decision problem of deciding whether there is a linear extension such that the weighted sum of job completion times is at most K, therefore I do not think the distinction between an optimization criterion and a constraint is important here.  However, I have not understood how to represent the constraint on the _weighted_ sum of completion times in the current problem.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T19:09:36.927Z
I think that the reduction is not as easy as I thought at the beginning. I'm not sure anymore of my answer.
Aldo
CC BY-SA 2.5
2010-09-17T11:28:16.633Z
I have just realized an error in my previous comment.  When I posted it, I thought that representing a constraint on the unweighted sum was easy (hence the emphasis on _weighted_), but that was completely wrong.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T16:50:13.727Z
2010-09-16T16:50:13.727Z
Aldo
<p>What if we always take the maximal element (in the partial order) with the least weight. After we exhaust the elements, we return them in reverse order as the output. </p>

CC BY-SA 2.5
2010-09-22T22:05:18.607Z
The problem is invariant under the transformation of reversing the partial ordering and negating all the weights. So I don't see how this can be different from the forward-greedy algorithm Robin K gave a counterexample to in the comments.
David Eppstein
CC BY-SA 2.5
2010-09-22T22:41:00.090Z
But this method works for his example: first, vertex 5 would be chosen, then vertex 4, then 3, 2, and finally 1. So the final order would be 1, 2, 3, 4, 5. 
In fact, I don't think it is hard to prove that this method works. Suppose you have a solution which does not have a maximal element (sink) of minimum weight in the last position. Then you can find another solution that does have this property, simply by changing the position of such an element to last, and preserving the rest as it is. Proceed by induction on what is left, and you get a formal proof.
Daniel Martin
CC BY-SA 2.5
2010-09-22T22:53:48.140Z
Yeah...  it does not work... 1 --> 2 --> 3, 1 --> 4 with weights 4, -7, 6, 3 respectively.
Daniel Martin
CC BY-SA 2.5
2010-09-22T19:52:09.163Z
2010-09-22T19:52:09.163Z
Daniel Martin
<p>This problem reminds me a lot of decision trees. I would consider this type of solution, which tries to always pick the most promising path, but by looking at the whole subgraph:</p>

<p>Starting from sink nodes, work your way towards the sources, one level at a time. While you do this, give every edge a weight. This weight should represent the minimum amount you'll have to "pay" or you will "gain" by traversing the subgraph starting from the node the edge points to. Suppose we are at level i+1 and we are moving up to level i . This is what I would do to assign a weight for an edge pointing to a node of level i:</p>

<ol>
<li>edge_weight = pointing_node_weight.</li>
<li>Find edge starting from "pointing node" with the maximum weight. Let this weight be next_edge_weight.</li>
<li>edge_weight += next_edge_weight</li>
</ol>

<p>Then, build the order as follows : </p>

<ol>
<li>Let S be the search frontier, i.e. the set of nodes to select from next.</li>
<li>Select the node so that (node_weight+maximum_edge_weight) is maximized. </li>
<li>Remove the node from the graph and S. Add the node's "children" to S.</li>
<li>If the graph is not empty, go to step 1.</li>
<li>Halt.</li>
</ol>

<p>The idea is to traverse those subgraphs that will give as much gain as possible first, in order to be able to bear the cost of the negative weight subgraphs later. </p>

CC BY-SA 2.5
2010-10-03T20:00:23.880Z
2010-10-03T20:00:23.880Z
chazisop
<p>This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in <a href="http://rads.stackoverflow.com/amzn/click/0716710455">Garey &amp; Johnson</a>. To wit:</p>

<blockquote>
  <p>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$. </p>
  
  <p>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$?</p>
</blockquote>

<p>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$.</p>

CC BY-SA 3.0
2012-01-12T16:27:41.963Z
@mhum: I am working on a technical report on related results and would like to cite you. Would you give me your real name? If you wish you can email it to me, or just stay anon...
domotorp
CC BY-SA 2.5
2010-10-05T09:23:15.653Z
This looks good. Then I think one can take $K=0$ without loss of generality, otherwise add an unconstrained job with $c$-value $-K$ (or $K$ jobs of $c$-value $-1$).
daveagp
CC BY-SA 2.5
2010-10-05T05:24:23.413Z
2010-10-05T17:02:25.820Z
2010-10-05T17:02:25.820Z
mhum
<p>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?</p>

CC BY-SA 2.5
2010-09-16T02:21:14.880Z
A clarification: Is the decision problem to decide if such a linear extension of the input weighted DAG exists?
Robin Kothari
CC BY-SA 2.5
2010-09-16T02:31:38.757Z
Yes. Thats what is needed.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T02:53:13.050Z
Out of curiosity, why do you consider this problem?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T03:28:25.197Z
It's a highly abstracted version of some of the Frechet distance problems JeffE and others have been looking at.
David Eppstein
CC BY-SA 2.5
2010-09-16T03:30:11.573Z
I don't see why the trivial greedy algorithm does not work? Am I missing something?
Kaveh
CC BY-SA 2.5
2010-09-16T03:42:20.700Z
Hmm, I asked the motivation because I thought that this question probably had an interesting background story, but sadly I have no idea what you are talking about because of my lack of knowledge.  Anyway thanks for answering.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T03:43:28.790Z
Try the greedy algorithm on this graph: 1-->2-->3, 1-->4-->5, vertex weights are 1:+2, 2:-2, 3:+3, 4:-1, 5:-2.  The greedy algorithm would start with v1, then choose v4, and then get stuck. The correct order is v1, v2, v3, v4, v5.
Robin Kothari
CC BY-SA 2.5
2010-09-16T03:56:17.577Z
David, is anything known for more structured orders ? like lattices ? if the weight function is modular ? and so on ?
Suresh Venkat
CC BY-SA 2.5
2010-09-16T04:33:48.437Z
"some of the Frechet distance problems JeffE and others have been looking at" — Nice abstraction!  For others' benefit, here's one version: Suppose you are given an edge-weighted plane graph G, and two vertices s and t n the outer face. You want to transform one boundary path from s to t into the other by a sequence of elementary moves. Each move replaces the current path with its symmetric difference with some face boundary. How quickly can we find the mve sequence that minimizes the maximum length of the evolving path?
Jeffε
CC BY-SA 2.5
2010-09-16T04:37:34.513Z
Tsuyoshi, sorry about that, I attempted to add a newline while commenting and it caused my comment to get cut off.

So the idea is, you have a string tied tightly around your wrist and you want to know if you can wriggle it off. Your wrist is represented as a polygonal mesh, the cells of which are elements of a partial order (closer to the string earlier, closer to off later in the order). The weight of a cell is the difference in lengths between its inner and outer boundaries.
David Eppstein
CC BY-SA 2.5
2010-09-16T04:43:53.333Z
Suresh: any partial order can be embedded in a lattice (the MacNeille completion) and you can give the extra elements created in the embedding weight zero. But of course the lattice could be much bigger than the partial order. So it seems like being a lattice wouldn't help but I'm not certain of that. For the application I have in mind, st-planar lattices (i.e. lattices of order dimension two) would be an interesting special case, but I don't even know anything about that case.
David Eppstein
CC BY-SA 2.5
2010-09-16T05:17:26.103Z
ok. I was also thinking of restricting the weight function to be modular or something convenient, but I have no intuition about whether that might help.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T05:36:22.523Z
@David: Thanks for the explanation.  This time I can understand how it is related to the current question, and it is interesting!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T12:02:55.820Z
@JeffE: And now I understand the connection between your explanation and David’s explanation.  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T14:17:00.420Z
@David: is the integer weight special case interesting?  That seems to reduce to deciding whether a particular kind of lattice walk stays in the non-negative quadrant, or equivalently, whether a one-counter automaton can reach the target state.
András Salamon
CC BY-SA 2.5
2010-09-17T12:45:22.107Z
A not-so-useful but fun observation: This problem is equivalent to the single-machine sequencing problem with deadlines and precedence constraints _where the processing time of each job can be negative_.  With nonnegative processing time, this problem is in P (Lawler and Mooer 1969 http://www.jstor.org/stable/2628367), and if a solution exists, then a solution exists which is independent of the processing time.  This clearly breaks down if some jobs have negative processing time.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T05:37:02.583Z
Is the problem easy to solve on trees?
Hrushikesh
CC BY-SA 2.5
2010-10-01T03:30:34.397Z
It's self-reducible, so we can concentrate on the decision variant rather than the search variant.
Warren Schudy
<ds.algorithms><directed-acyclic-graph><partial-order><topological-sorting>
Positive topological ordering
David Eppstein
# Positive topological ordering

(Asked by: username_0 on 2010-09-16)

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?

**Tags:** ds.algorithms, directed-acyclic-graph, partial-order, topological-sorting

> **Comments:**
> **username_1**: A clarification: Is the decision problem to decide if such a linear extension of the input weighted DAG exists?  
> **username_2**: Yes. Thats what is needed.  
> **username_3**: Out of curiosity, why do you consider this problem?  
> **username_0**: It's a highly abstracted version of some of the Frechet distance problems JeffE and others have been looking at.  
> **username_4**: I don't see why the trivial greedy algorithm does not work? Am I missing something?  
> **username_3**: Hmm, I asked the motivation because I thought that this question probably had an interesting background story, but sadly I have no idea what you are talking about because of my lack of knowledge.  Anyway thanks for answering.  
> **username_1**: Try the greedy algorithm on this graph: 1-->2-->3, 1-->4-->5, vertex weights are 1:+2, 2:-2, 3:+3, 4:-1, 5:-2.  The greedy algorithm would start with v1, then choose v4, and then get stuck. The correct order is v1, v2, v3, v4, v5.  
> **username_2**: David, is anything known for more structured orders ? like lattices ? if the weight function is modular ? and so on ?  
> **username_5**: "some of the Frechet distance problems JeffE and others have been looking at" — Nice abstraction!  For others' benefit, here's one version: Suppose you are given an edge-weighted plane graph G, and two vertices s and t n the outer face. You want to transform one boundary path from s to t into the other by a sequence of elementary moves. Each move replaces the current path with its symmetric difference with some face boundary. How quickly can we find the mve sequence that minimizes the maximum length of the evolving path?  
> **username_0**: Tsuyoshi, sorry about that, I attempted to add a newline while commenting and it caused my comment to get cut off.  So the idea is, you have a string tied tightly around your wrist and you want to know if you can wriggle it off. Your wrist is represented as a polygonal mesh, the cells of which are elements of a partial order (closer to the string earlier, closer to off later in the order). The weight of a cell is the difference in lengths between its inner and outer boundaries.  
> **username_0**: Suresh: any partial order can be embedded in a lattice (the MacNeille completion) and you can give the extra elements created in the embedding weight zero. But of course the lattice could be much bigger than the partial order. So it seems like being a lattice wouldn't help but I'm not certain of that. For the application I have in mind, st-planar lattices (i.e. lattices of order dimension two) would be an interesting special case, but I don't even know anything about that case.  
> **username_2**: ok. I was also thinking of restricting the weight function to be modular or something convenient, but I have no intuition about whether that might help.  
> **username_3**: @David: Thanks for the explanation.  This time I can understand how it is related to the current question, and it is interesting!  
> **username_3**: @JeffE: And now I understand the connection between your explanation and David’s explanation.  Thanks!  
> **username_6**: @David: is the integer weight special case interesting?  That seems to reduce to deciding whether a particular kind of lattice walk stays in the non-negative quadrant, or equivalently, whether a one-counter automaton can reach the target state.  
> **username_3**: A not-so-useful but fun observation: This problem is equivalent to the single-machine sequencing problem with deadlines and precedence constraints _where the processing time of each job can be negative_.  With nonnegative processing time, this problem is in P (Lawler and Mooer 1969 http://www.jstor.org/stable/2628367), and if a solution exists, then a solution exists which is independent of the processing time.  This clearly breaks down if some jobs have negative processing time.  
> **username_7**: Is the problem easy to solve on trees?  
> **username_8**: It's self-reducible, so we can concentrate on the decision variant rather than the search variant.  

---

## 5 answers

### Answer by username_13 on 2010-10-05. Score: 18 | Accepted answer

This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in [Garey & Johnson](http://rads.stackoverflow.com/amzn/click/0716710455). 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) < 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&J mention that the problem remains NP-complete if $c(t) \in \{-1,0,1\}$ for all $t \in T$.

> **Comments:**
> **username_14**: This looks good. Then I think one can take $K=0$ without loss of generality, otherwise add an unconstrained job with $c$-value $-K$ (or $K$ jobs of $c$-value $-1$).  
> **username_9**: @username_13: I am working on a technical report on related results and would like to cite you. Would you give me your real name? If you wish you can email it to me, or just stay anon...  

---

### Answer by username_9 on 2010-10-01. Score: 9

Well, my answer is my question from which it turns out that if you could solve this problem in P, you could also solve another open problem:
[Positive topological ordering, take 3](https://cstheory.stackexchange.com/questions/1842/positive-topological-ordering-take-3)

Edit: This problem also turned out to be NP-complete, so your problem is NP-complete already if your DAG has only two levels, i.e. if there are no directed paths with two edges.


---

### Answer by username_10 on 2010-09-16. Score: 3

If I understand the problem correctly, I think that the precedence constrained single machine scheduling problem to minimize the weighted sum of completion times (1|prec|\sum wc) can be reduced to the problem you are interested.
In problem 1|prec|\sum wc we have n jobs, each with a non-negative weight and a processing time, a poset on the jobs and we want a linear extension of the jobs such that the weighted sum of jobs completion times is minimized. The problems is NP-complete even though we assume that the processing time of each job is equal to 1. Does it make any sense?

> **Comments:**
> **username_0**: It's definitely an interesting possibility. But how do you do the reduction in such a way that the optimization criterion (minimize sum of completion times) gets transformed into constraints (non-negative prefixes)?  
> **username_3**: I do not know this NP-completeness result of scheduling problem, but I think that it refers to the decision problem of deciding whether there is a linear extension such that the weighted sum of job completion times is at most K, therefore I do not think the distinction between an optimization criterion and a constraint is important here.  However, I have not understood how to represent the constraint on the _weighted_ sum of completion times in the current problem.  
> **username_10**: I think that the reduction is not as easy as I thought at the beginning. I'm not sure anymore of my answer.  
> **username_3**: I have just realized an error in my previous comment.  When I posted it, I thought that representing a constraint on the unweighted sum was easy (hence the emphasis on _weighted_), but that was completely wrong.  

---

### Answer by username_11 on 2010-09-22. Score: 2

What if we always take the maximal element (in the partial order) with the least weight. After we exhaust the elements, we return them in reverse order as the output.

> **Comments:**
> **username_0**: The problem is invariant under the transformation of reversing the partial ordering and negating all the weights. So I don't see how this can be different from the forward-greedy algorithm Robin K gave a counterexample to in the comments.  
> **username_11**: But this method works for his example: first, vertex 5 would be chosen, then vertex 4, then 3, 2, and finally 1. So the final order would be 1, 2, 3, 4, 5.  In fact, I don't think it is hard to prove that this method works. Suppose you have a solution which does not have a maximal element (sink) of minimum weight in the last position. Then you can find another solution that does have this property, simply by changing the position of such an element to last, and preserving the rest as it is. Proceed by induction on what is left, and you get a formal proof.  
> **username_11**: Yeah...  it does not work... 1 --> 2 --> 3, 1 --> 4 with weights 4, -7, 6, 3 respectively.  

---

### Answer by username_12 on 2010-10-03. Score: 1

This problem reminds me a lot of decision trees. I would consider this type of solution, which tries to always pick the most promising path, but by looking at the whole subgraph:

Starting from sink nodes, work your way towards the sources, one level at a time. While you do this, give every edge a weight. This weight should represent the minimum amount you'll have to "pay" or you will "gain" by traversing the subgraph starting from the node the edge points to. Suppose we are at level i+1 and we are moving up to level i . This is what I would do to assign a weight for an edge pointing to a node of level i:

1. edge\_weight = pointing\_node\_weight.
2. Find edge starting from "pointing node" with the maximum weight. Let this weight be next\_edge\_weight.
3. edge\_weight += next\_edge\_weight

Then, build the order as follows :

1. Let S be the search frontier, i.e. the set of nodes to select from next.
2. Select the node so that (node\_weight+maximum\_edge\_weight) is maximized.
3. Remove the node from the graph and S. Add the node's "children" to S.
4. If the graph is not empty, go to step 1.
5. Halt.

The idea is to traverse those subgraphs that will give as much gain as possible first, in order to be able to bear the cost of the negative weight subgraphs later.


---

