47

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?

a3nm
  • 9,269
  • 27
  • 86
David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • A clarification: Is the decision problem to decide if such a linear extension of the input weighted DAG exists? – Robin Kothari Sep 16 '10 at 02:21
  • Yes. Thats what is needed. – Suresh Venkat Sep 16 '10 at 02:31
  • Out of curiosity, why do you consider this problem? – Tsuyoshi Ito Sep 16 '10 at 02:53
  • It's a highly abstracted version of some of the Frechet distance problems JeffE and others have been looking at. – David Eppstein Sep 16 '10 at 03:28
  • I don't see why the trivial greedy algorithm does not work? Am I missing something? – Kaveh Sep 16 '10 at 03:30
  • 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 Sep 16 '10 at 03:42
  • 4
    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 Sep 16 '10 at 03:43
  • David, is anything known for more structured orders ? like lattices ? if the weight function is modular ? and so on ? – Suresh Venkat Sep 16 '10 at 03:56
  • 2
    "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ε Sep 16 '10 at 04:33
  • 3
    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 Sep 16 '10 at 04:37
  • 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 Sep 16 '10 at 04:43
  • 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 Sep 16 '10 at 05:17
  • 1
    @David: Thanks for the explanation. This time I can understand how it is related to the current question, and it is interesting! – Tsuyoshi Ito Sep 16 '10 at 05:36
  • @JeffE: And now I understand the connection between your explanation and David’s explanation. Thanks! – Tsuyoshi Ito Sep 16 '10 at 12:02
  • @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 Sep 16 '10 at 14:17
  • 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. – Tsuyoshi Ito Sep 17 '10 at 12:45
  • 1
    Is the problem easy to solve on trees? – Hrushikesh Sep 27 '10 at 05:37
  • 1
    It's self-reducible, so we can concentrate on the decision variant rather than the search variant. – Warren Schudy Oct 01 '10 at 03:30

5 Answers5

18

This problem appears to be very similar to SEQUENCING TO MINIMIZE MAXIMUM CUMULATIVE COST, problem [SS7] in Garey & 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) < 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$.

mhum
  • 3,382
  • 1
  • 21
  • 22
  • 7
    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 Oct 05 '10 at 09:23
  • @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 Jan 12 '12 at 16:27
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

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.

Community
  • 1
domotorp
  • 13,931
  • 37
  • 93
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?

Aldo
  • 31
  • 1
  • 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 Sep 16 '10 at 16:57
  • 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 Sep 16 '10 at 18:31
  • I think that the reduction is not as easy as I thought at the beginning. I'm not sure anymore of my answer. – Aldo Sep 16 '10 at 19:09
  • 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 Sep 17 '10 at 11:28
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.

Daniel Martin
  • 21
  • 2
  • 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 Sep 22 '10 at 22:05
  • 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 Sep 22 '10 at 22:41
  • Yeah... it does not work... 1 --> 2 --> 3, 1 --> 4 with weights 4, -7, 6, 3 respectively. – Daniel Martin Sep 22 '10 at 22:53
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.

chazisop
  • 3,796
  • 2
  • 29
  • 37