Positive topological ordering

Question

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?

Answer 1

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

Answer 2

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.

Answer 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?

Answer 4

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.

Answer 5

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.