<p>After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.</p>

<p>Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the gadget with two configurations and same cost!).</p>

<p><img src="https://i.sstatic.net/ptnGf.png" alt="enter image description here"></p>

<p>Each blue horizontal line corresponds to a different schedule time ($s=1,2,...$).
On the left of the picture there is a complete assignment gadget for three variable ($x1,x2,x3$).
The <em>red</em> nodes correspond to a $true$ assignment ($+x_i$), the <em>blue</em> nodes to a $false$ assignment ($-x_i$). A <em>green</em> node correspond to a variable $x_i$ and can be placed
on the same schedule time of the red or the blue node, <em>without afftecting the total cost</em> of the gadget. The three possible combinations for $x_1$ are showed on the right. The number in the nodes represents the <em>cost</em> (the number of distinct parents). Both $x_1 = true, x_1 = false$ have a cost of 7 ($c=7$). Note that the last combination has a greater cost so it cannot be used.</p>

<p>Now we extend the assignment gadget to "simulate" the clauses of the formula.</p>

<p><img src="https://i.sstatic.net/pBODn.png" alt="enter image description here"></p>

<p>First we add a <em>top node</em>, and a <em>mirror chain</em> of $3n+2$ nodes (the chain of nodes on the left of the picture). By construction some of the nodes of the mirror chain must be on the same schedule time of the $true/false$ assignments; we call them $+x'_1, -x'_1, +x'_2, -x'_2,...$ (yellow nodes of the mirror chain in the figure).
Now we add a <em>clause node</em> $C_j$ for each clause and we force it to be at schedule time $s=1$ by adding two directed edges from the bottom of the mirror chain and assignment gadget.</p>

<p>We link the <em>clause node</em> to the three variables it contains (green edges in the figure), and to the corresponding positive/negative literal in the mirror chain (red edges in the figure). Finally we link the clause node to the top node using a chain of 6 <em>clause pegs</em> $P_{j_1},...,P_{j_6}$ (purple nodes in the figure).</p>

<p><strong>How it works</strong></p>

<p>The clause pegs of $C_j$ are linked together so they must be placed at different schedule times. So the cost of $C_j$ is greater than or equal to $6$. We can keep the cost of $C_j$ equal to 6 if and only if the assignment corresponding to the position of the green variables nodes contained in $C_j$ satisfies $C_j$.</p>

<p>First of all note that the bottom peg $P_{j,1}$ must be put at schedule time $s=2$ because $C_j$ is linked to the bottom of the assignment gadget and mirror chain. So only 5 of the pegs are "free" to be assigned to greater schedule times (otherwise the cost of $C_j$ is \geq 7$).</p>

<p>Now, suppose for example that $C_1$ is $(x_1 \lor \bar{x}_2 \lor x_3)$ (like in the figure). We have the green edges: $x_1 \to C_1, x_2 \to C_1, x_3 \to C_1$ and the red edges $+x'_1 \to C_1, -x'_2 \to C_1, +x'_3 \to C_1$.</p>

<p>Suppose that we set $x_1 = true, x_2 = true, x_3=false$ then the green variable $x_1$ will be on the same schedule time of $+x'_1$. But $x_2, -x'_2$ and $x_3, +x'_3$ will be on different schedule times. We can put a peg on the same schedule time of $x_1=true$, and the remaining 4 can be placed on the same schedule times of $x_2=true, -x'_2, +x'_3, x_3=false$ ("mask" them). The total cost of $C_1$ is still 6.</p>

<p>But what happens if we cannot find an assignment that satisfy all clauses? Then, in at least one clause (suppose $C_1$), the green variable nodes $x_1=false,x_2=true,x_3=false$ are all on a different schedule time of the corresponding $+x'_1, -x'_2, +x'_3$. So the 5 free pegs are not enough to "mask" them and the number of distinct parents of $C_1$ increases to $7$, like in the figure below.</p>

<p><img src="https://i.sstatic.net/Z3wiP.png" alt="enter image description here"></p>

<p>Note that without the pegs, the (minimum) total cost $c_t$ of the schedule is fixed, so we can conclude that after adding the pegs, the original formula is satisfiable if and only if the total cost of the graph is less than $c_t + 6*m$.</p>

CC BY-SA 3.0
2014-05-26T23:08:24.183Z
The induced graph on $X_1$ can be arbitrary large for example $n/2$. How do you want assign numbers in polynomial time?
Saeed
CC BY-SA 3.0
2014-05-28T18:51:27.400Z
@Saeed: I've switched from polynomial-time to NPC :-))) ... if you want take a look at the proof (I wrote it quickly so it can be wrong, as well).
Marzio De Biasi
CC BY-SA 3.0
2014-05-28T20:41:47.490Z
Hi Marzio, I tried to read it but I failed. At least I didn't get why "$x_1$ will be on the same schedule time of $+x′_1$"
Saeed
CC BY-SA 3.0
2014-05-28T20:44:51.180Z
Also I think this sentence is not correct while the aim you want to achieve is correct: "First of all note that the bottom peg Pj,1 must be put at schedule time s=2 because Cj is linked to the bottom of the assignment gadget and mirror chain. "
Saeed
CC BY-SA 3.0
2014-05-28T21:55:59.907Z
What is your hunch: is there any hope that a greedy solution could be e.g. a constant-factor approximation?
Jukka Suomela
CC BY-SA 3.0
2014-05-28T22:14:16.670Z
@Saeed: comment1: it means that if we choose $x_1 = true$ then, by construction, the green node corresponding to $x_1$ is on the same "line" (same schedule) of the node $+ x'_1$ of the mirror change. So their contribution to the cost of $C_1$ is only 1 and it is still 1 if we place a "peg" on the same line.
Marzio De Biasi
CC BY-SA 3.0
2014-05-28T22:24:16.317Z
@Saeed: comment2: there is a chain of 6 pegs (all linked to $C_1$) if all of them are placed above the schedule time $s=2$ then the number of parent distinct nodes of $C_1$ is $\geq 7$. If we place one of the peg at schedule time $s=2$ then the number of parent nodes of $C_1$ can be limited to $6$ (if poperly schedule the pegs and if the assignment can satisfy the clause).
Marzio De Biasi
CC BY-SA 3.0
2014-05-28T22:32:36.810Z
@JukkaSuomela: I really don't know; perhaps there is a greedy algorithm that works going bottom up (starting from the nodes that have outdeg=0). I'll think about it.
Marzio De Biasi
CC BY-SA 3.0
2014-05-28T22:50:47.850Z
C1: i know what does it mean but I still cannot see "why" we have to use this assignment of schedule, why any other assignment is bigger result or wrong? C2: I know what u mean and I said imho ur goal is correct but I think it was better to write something like: if s(pj1) greater than 2 then blah blahbad happens. Because before reading to the end is not clear why cj=7 is bad (ok it's easy to feel it before reading the end but it's not logical to accept it before reading to the end).
Saeed
CC BY-SA 3.0
2014-05-28T23:19:36.543Z
@Saeed: C1: $x_1 = true$ is only an example; by construction, the green variable node $x_1$ must be scheduled at the same time of $+x_1, +x'_1$ or at the same time of $-x_1, -x'_1$, if $x_1$ is linked to a clause $C_j$ where it appears as a positive literal, then $C_j$ is also linked (by construction) to $+x'_1$. If you schedule $x_1$ at the same time of $+x_1$ (i.e. you set it to true) then you can "mask" both $x_1, +x'_1$ with only one of the peg of $C_j$ (each peg can be viewed as a forced +1 cost for the corresponding clause).
Marzio De Biasi
CC BY-SA 3.0
2014-06-03T12:29:05.553Z
@MarzioDeBiasi: Nice reduction! Can't you merge the assignment gadget with the mirror chain? And, what did you use to create the figures? :)
Jonny5
CC BY-SA 3.0
2014-06-03T12:34:00.173Z
Yes, but the graph would be too confusing and I preferred to keep  the assignment part and the "simulation" of the clauses distinct. I used [yEd](http://www.yworks.com/en/downloads.html#yEd), a great tool to draw graphs quickly (though not of the same quality of those produced with TikZiT)
Marzio De Biasi
CC BY-SA 3.0
2014-05-26T22:42:40.723Z
2014-05-28T19:03:49.937Z
2014-05-28T19:03:49.937Z
Marzio De Biasi
<p>This is a <strong>non-answer</strong>, but it might help to understand the question (assuming that I understood it correctly).</p>

<p>Here is a simple but slightly non-trivial example:</p>

<p><img src="https://i.sstatic.net/grCRu.png" alt="enter image description here"></p>

<p>Here:</p>

<ul>
<li>input = black graph</li>
<li>output = on which blue line we place each node = when to schedule each job</li>
<li>costs = orange numbers = number of predecessors with different labels</li>
</ul>

<p>Left = simple greedy solution, right = optimal solution.</p>

<hr>

<p>I would not be surprised if this was NP-hard. There seem to be opportunities for designing all kinds of gadgets. For example, here is a gadget in which we have two optimal solutions—one of the sink nodes has to pay 2 units, but you can choose which one.</p>

<p><img src="https://i.sstatic.net/vBQKB.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-05-26T21:46:24.997Z
I still don't understand the problem :-S. The OP says that if $v_2 \to v_1$ then $S(v_1) < S(v_2)$, but in your (top) examples the constraint is not satisfied. Furthermore in your top two figures, the blue numbers (the legend says that is is the output) are the same. I was thinking of a greedy approach starting from the end of one of the longest path (that must have different decreasing costs) and going backward; but probably my interpretation is wrong. The question remains a mistery :-) And what is the role (if any) of P?
Marzio De Biasi
CC BY-SA 3.0
2014-05-26T22:15:37.877Z
@MarzioDeBiasi: In my drawing, e.g. $S(v) = 3$ is denoted by placing the node $v$ on top of the blue line labelled with "3". The constraints are satisfied; all edges point from larger labels towards smaller labels.
Jukka Suomela
CC BY-SA 3.0
2014-05-26T22:21:16.183Z
@MarzioDeBiasi: And forget about $P$, as far as I can see, it plays no role here.
Jukka Suomela
CC BY-SA 3.0
2014-05-26T22:35:40.863Z
Now I see it, thanks! :-) It seems it matches my interpretation. I'll post the greedy algorithm, perhaps you scan easily check if it is wrong and find a counterexample.
Marzio De Biasi
CC BY-SA 3.0
2014-05-26T19:57:30.137Z
2014-05-26T22:23:42.463Z
2014-05-26T22:23:42.463Z
Jukka Suomela
<p>I found a reduction from the Partition Problem to a modified version of the proposed problem.</p>

<h3>Partition Problem (Optimization)</h3>

<ul>
<li>input: set of integers S</li>
<li>output: partition of S into S1 and S1 such
that the difference of the sums of S1 and S2 is minimized: 
$$\lvert\sum_{s\in S1}s - \sum_{s\in S2}s\lvert.$$</li>
</ul>

<p>This problem is NP-hard.</p>

<h3>Level Assignment Problem (Optimization)</h3>

<ul>
<li>input: a DAG $G = (V,E)$, a weight function $w:V\rightarrow\mathbb{Z}$</li>
<li>output: a mapping $m:V\rightarrow[1,depth(G)]$ such that:

<ol>
<li>$(v1,v2) \in E \Rightarrow m(v1) &gt; m(v2)$</li>
<li>the following is minimized: 
$$sum\{ numlevels(v) \times w(v) \mid v \in V\},$$
where $$numlevels(v) = |\{m(v') \mid (v',v) \in E \}|.$$</li>
</ol></li>
</ul>

<h3>Reduction</h3>

<p>The reduction from the partition problem to the level assignment problem can be done as follows: for each $s_i \in S$, create the following gadget, where the weights are indicated between brackets:</p>

<p><img src="https://i.sstatic.net/kGcZH.png" alt="gadget for a number si"></p>

<p>It is easy to see that the following mappings are obligatory:</p>

<ul>
<li>$m(A_i) = 1$</li>
<li>$m(B_i) = 1$</li>
<li>$m(A'_i) = 2$</li>
<li>$m(B'_i) = 3$</li>
</ul>

<p>Hence, the only choice left is $m(v_i)$. When choosing $m(v_i) = 2$, this gadget will contribute $s_i$ to the total sum. When $m(v_i) = 3$, it will contribute $-s_i$.</p>

<p>Now, after solving the level assignment problem, group the $s_i$ in the following way:</p>

<ul>
<li>$S_1 = \{s_i \in S \mid m(v_i) = 2\}$  </li>
<li>$S_2 = \{s_i \in S \mid m(v_i) = 3\}$  </li>
</ul>

<p>The gadgets related to $S_1$ will contribute positively, those to $S_2$ negatively. Hence, we get a total cost of:
$$\sum_{s \in S_1} s + \sum_{s \in S_2} (-s) = \sum_{s \in S_1} s - \sum_{s \in S_2} s.$$</p>

<p>This is the function that is minimized and it corresponds to the minimization problem of the partition problem. Hence, our problem must be NP-hard as well.</p>

<p>Note: the partition problem has an absolute value in the function to be minimized. This is no problem, as this can be accomplished by swapping $S_1$ and $S_2$. </p>

CC BY-SA 3.0
2014-06-03T12:24:07.867Z
I didn't read the full reduction, yet; however in the equivalent DAG formulation of your original scheduling problem there are no "weights", but only "costs" and the cost of each node is the number of distinct parents (levels). Furthermore the cost of each node (and also the final total cost) is not given as input, but it is a function of the final level assignment  (schedule). So is this a different version from your original question?
Marzio De Biasi
CC BY-SA 3.0
2014-06-03T12:26:45.133Z
@Marzio: when you use unit weights, this gives the same problem as the original level assignment problem. the costs in the original problem are 1 for each level, here, it is w(v_i) for each level, so it is a more general problem.
Jonny5
CC BY-SA 3.0
2014-06-03T12:29:22.990Z
Ok! (but  the partition problem is not strongly np-hard so I think that you cannot use the same approach to prove the unit weights version). Did you check my reduction?
Marzio De Biasi
CC BY-SA 3.0
2014-06-03T12:52:56.513Z
yes, your reduction seems ok. Could it also be possible to reduce from the Partition Decision problem (sums of S1 and S2 must be equal) and creating $s$ nodes for each $s \in S$? Or is it not allowed to created this amount of nodes in a poly reduction?
Jonny5
CC BY-SA 3.0
2014-06-03T13:01:25.657Z
I think it's not possible because the partition problem is not strongly NP-complete. But perhaps you can try with the 3-PARTITION PROBLEM, which is strongly NPC (it is still NPC even if numbers are represented in unary) and end up with a reduction that is simpler than mine.
Marzio De Biasi
CC BY-SA 3.0
2014-06-03T13:04:58.783Z
good idea, I will give this a try!
Jonny5
CC BY-SA 3.0
2014-06-03T12:05:07.723Z
2014-06-03T12:05:07.723Z
Jonny5
<p>Consider the following scheduling problem:</p>

<p><strong>input:</strong> </p>

<ul>
<li>set of computations $C = \{c_1, ..., c_n\}$ </li>
<li>set of computing nodes $P = \{p_1, ..., p_n\}$</li>
<li>Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ means $c_i$ depends on/reads $c_j$ </li>
</ul>

<p><strong>output:</strong></p>

<p>Schedule S = subset of $C \times [1,n]$ where $(c_i,k)$ means that job $c_i$ will be executed in timeslot $k$
the following conditions hold:</p>

<ol>
<li>precisely one timeslot per job</li>
<li>dependencies have lower timeslots</li>
</ol>

<p>Now, we want to minimize the cost of the schedule:</p>

<ul>
<li>$cost(c_i,S) = |\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}|$
i.e. the cost of a job is the number of levels where it is read</li>
<li>$totalCost(S) = \sum_{c_i \in C} cost(c_i,S)$</li>
</ul>

<p>Hence, we want to calculate the best way of assigning the computations to timeslots, such that the number of reads are minimized. Note that the number of computing nodes is irrelevant.</p>

<p>I cannot seem to find any papers on this specific problem. Does anyone know whether this has been investigated? It seems it has to be... :) </p>

<p>Edit:</p>

<p>we can rephrase this as a graph problem:
Consider a DAG $G = (V,E)$. </p>

<p>A <strong>schedule</strong> is a mapping $S:V\rightarrow\mathbb{N}$ which assigns a number to each node, such that if $v_1$ is reachable from $v_2$, then $S(v_1) &lt; S(v_2)$.</p>

<p>Define the <strong>cost</strong> of a node $v_1$ is defined as $cost(v_1) = |\{S(v_2) \mid (v_2,v_1) \in E\}|$, i.e., the number of different numbers that are assigned to parent nodes.</p>

<p>The problem: find a schedule S that <strong>minimizes the total cost</strong> over the nodes.</p>

CC BY-SA 3.0
2014-05-23T16:59:07.513Z
If I understood correctly, here is another way to state the problem: given a DAG $D$, label the nodes with integers so that predecessors have smaller labels and the cost of a node is the number of predecessors with distinct labels?
Jukka Suomela
CC BY-SA 3.0
2014-05-26T06:25:31.540Z
actually yes, except that the cost is the number of distinct labelled successors (children). I clarified the DAG usage.
Jonny5
CC BY-SA 3.0
2014-05-26T10:42:03.860Z
Could you perhaps edit the question and rephrase it as a graph problem? It might be easier to get answers if the question is short and easy to understand.
Jukka Suomela
CC BY-SA 3.0
2014-05-26T10:46:56.183Z
What is $J$? I don't understand the cost/objective in the question.
R B
CC BY-SA 3.0
2014-05-26T10:54:05.700Z
@RB: I guess $J = C$ (i.e., the set of nodes in DAG $D$).
Jukka Suomela
CC BY-SA 3.0
2014-05-26T11:04:01.283Z
@JukkaSuomela - Then isn't this cost fixed for any scheduling algorithm? (each job costs it's out degree, and the total cost is the number of edges).
R B
CC BY-SA 3.0
2014-05-26T11:40:01.037Z
No, the cost depends on the number assigned to the computation. @JukkaSuomela: I'll try to rephrase it..
Jonny5
CC BY-SA 3.0
2014-05-26T12:48:57.093Z
@Xaero182 - even in your graph formulation I think the cost is just the degree. Since $S$ assigns a different value for each node, $|\{S(v_2) \mid (v_2,v_1) \in E\}|=d_{in}(v_1)$...
R B
CC BY-SA 3.0
2014-05-26T13:03:18.867Z
Did you mean $cost(c_i)=max\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}$ or $cost(c_i)=\sum _{\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}} k?$
R B
CC BY-SA 3.0
2014-05-26T17:13:04.090Z
@RB: In the graph formulation, the cost is the number of *distinct* labels in the set of successors. Here is a simple example. The graph consists of nodes $\{s,t,u\}$ and edges $(t,s)$ and $(u,s)$. If we use schedule $s \mapsto 1$, $t \mapsto 2$, $u \mapsto 3$, we have a feasible solution such that $cost(s) = 2, cost(t) = 0, cost(u) = 0$. However, we can do better; if we set $u \mapsto 2$, we have $cost(s) = 1$.
Jukka Suomela
CC BY-SA 3.0
2014-05-28T22:42:30.330Z
there are a zillion scheduling problems/variants in the literature & it would be nice to try to find the closest one to the problem....
vzn
<optimization><dc.distributed-comp><scheduling>
Job scheduling: minimizing number of reads
Jonny5
# Job scheduling: minimizing number of reads

(Asked by: username_0 on 2014-05-23)

Consider the following scheduling problem:

**input:**

* set of computations $C = \{c\_1, ..., c\_n\}$
* set of computing nodes $P = \{p\_1, ..., p\_n\}$
* Dependency graph $D$ between jobs (DAG) $(c\_i,c\_j)$ means $c\_i$ depends on/reads $c\_j$

**output:**

Schedule S = subset of $C \times [1,n]$ where $(c\_i,k)$ means that job $c\_i$ will be executed in timeslot $k$
the following conditions hold:

1. precisely one timeslot per job
2. dependencies have lower timeslots

Now, we want to minimize the cost of the schedule:

* $cost(c\_i,S) = |\{ k \mid (c\_j,k) \in S \wedge (c\_i, c\_j) \in D \}|$
  i.e. the cost of a job is the number of levels where it is read
* $totalCost(S) = \sum\_{c\_i \in C} cost(c\_i,S)$

Hence, we want to calculate the best way of assigning the computations to timeslots, such that the number of reads are minimized. Note that the number of computing nodes is irrelevant.

I cannot seem to find any papers on this specific problem. Does anyone know whether this has been investigated? It seems it has to be... :)

Edit:

we can rephrase this as a graph problem:
Consider a DAG $G = (V,E)$.

A **schedule** is a mapping $S:V\rightarrow\mathbb{N}$ which assigns a number to each node, such that if $v\_1$ is reachable from $v\_2$, then $S(v\_1) < S(v\_2)$.

Define the **cost** of a node $v\_1$ is defined as $cost(v\_1) = |\{S(v\_2) \mid (v\_2,v\_1) \in E\}|$, i.e., the number of different numbers that are assigned to parent nodes.

The problem: find a schedule S that **minimizes the total cost** over the nodes.

**Tags:** optimization, dc.distributed-comp, scheduling
> **Comments:**
> **username_1**: If I understood correctly, here is another way to state the problem: given a DAG $D$, label the nodes with integers so that predecessors have smaller labels and the cost of a node is the number of predecessors with distinct labels?  
> **username_0**: actually yes, except that the cost is the number of distinct labelled successors (children). I clarified the DAG usage.  
> **username_1**: Could you perhaps edit the question and rephrase it as a graph problem? It might be easier to get answers if the question is short and easy to understand.  
> **username_2**: What is $J$? I don't understand the cost/objective in the question.  
> **username_1**: @RB: I guess $J = C$ (i.e., the set of nodes in DAG $D$).  
> **username_2**: @JukkaSuomela - Then isn't this cost fixed for any scheduling algorithm? (each job costs it's out degree, and the total cost is the number of edges).  
> **username_0**: No, the cost depends on the number assigned to the computation. @JukkaSuomela: I'll try to rephrase it..  
> **username_2**: @Xaero182 - even in your graph formulation I think the cost is just the degree. Since $S$ assigns a different value for each node, $|\{S(v_2) \mid (v_2,v_1) \in E\}|=d_{in}(v_1)$...  
> **username_2**: Did you mean $cost(c_i)=max\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}$ or $cost(c_i)=\sum _{\{ k \mid (c_j,k) \in S \wedge (c_i, c_j) \in D \}} k?$  
> **username_1**: @RB: In the graph formulation, the cost is the number of *distinct* labels in the set of successors. Here is a simple example. The graph consists of nodes $\{s,t,u\}$ and edges $(t,s)$ and $(u,s)$. If we use schedule $s \mapsto 1$, $t \mapsto 2$, $u \mapsto 3$, we have a feasible solution such that $cost(s) = 2, cost(t) = 0, cost(u) = 0$. However, we can do better; if we set $u \mapsto 2$, we have $cost(s) = 1$.  
> **username_3**: there are a zillion scheduling problems/variants in the literature & it would be nice to try to find the closest one to the problem....  

---

## 3 answers

### Answer by username_4 on 2014-05-26. Score: 6

After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.

Given a 3SAT formula with $x\_1,...,x\_n$ variables and $C\_1,...,C\_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the gadget with two configurations and same cost!).

![enter image description here](https://i.sstatic.net/ptnGf.png)

Each blue horizontal line corresponds to a different schedule time ($s=1,2,...$).
On the left of the picture there is a complete assignment gadget for three variable ($x1,x2,x3$).
The *red* nodes correspond to a $true$ assignment ($+x\_i$), the *blue* nodes to a $false$ assignment ($-x\_i$). A *green* node correspond to a variable $x\_i$ and can be placed
on the same schedule time of the red or the blue node, *without afftecting the total cost* of the gadget. The three possible combinations for $x\_1$ are showed on the right. The number in the nodes represents the *cost* (the number of distinct parents). Both $x\_1 = true, x\_1 = false$ have a cost of 7 ($c=7$). Note that the last combination has a greater cost so it cannot be used.

Now we extend the assignment gadget to "simulate" the clauses of the formula.

![enter image description here](https://i.sstatic.net/pBODn.png)

First we add a *top node*, and a *mirror chain* of $3n+2$ nodes (the chain of nodes on the left of the picture). By construction some of the nodes of the mirror chain must be on the same schedule time of the $true/false$ assignments; we call them $+x'\_1, -x'\_1, +x'\_2, -x'\_2,...$ (yellow nodes of the mirror chain in the figure).
Now we add a *clause node* $C\_j$ for each clause and we force it to be at schedule time $s=1$ by adding two directed edges from the bottom of the mirror chain and assignment gadget.

We link the *clause node* to the three variables it contains (green edges in the figure), and to the corresponding positive/negative literal in the mirror chain (red edges in the figure). Finally we link the clause node to the top node using a chain of 6 *clause pegs* $P\_{j\_1},...,P\_{j\_6}$ (purple nodes in the figure).

**How it works**

The clause pegs of $C\_j$ are linked together so they must be placed at different schedule times. So the cost of $C\_j$ is greater than or equal to $6$. We can keep the cost of $C\_j$ equal to 6 if and only if the assignment corresponding to the position of the green variables nodes contained in $C\_j$ satisfies $C\_j$.

First of all note that the bottom peg $P\_{j,1}$ must be put at schedule time $s=2$ because $C\_j$ is linked to the bottom of the assignment gadget and mirror chain. So only 5 of the pegs are "free" to be assigned to greater schedule times (otherwise the cost of $C\_j$ is \geq 7$).

Now, suppose for example that $C\_1$ is $(x\_1 \lor \bar{x}\_2 \lor x\_3)$ (like in the figure). We have the green edges: $x\_1 \to C\_1, x\_2 \to C\_1, x\_3 \to C\_1$ and the red edges $+x'\_1 \to C\_1, -x'\_2 \to C\_1, +x'\_3 \to C\_1$.

Suppose that we set $x\_1 = true, x\_2 = true, x\_3=false$ then the green variable $x\_1$ will be on the same schedule time of $+x'\_1$. But $x\_2, -x'\_2$ and $x\_3, +x'\_3$ will be on different schedule times. We can put a peg on the same schedule time of $x\_1=true$, and the remaining 4 can be placed on the same schedule times of $x\_2=true, -x'\_2, +x'\_3, x\_3=false$ ("mask" them). The total cost of $C\_1$ is still 6.

But what happens if we cannot find an assignment that satisfy all clauses? Then, in at least one clause (suppose $C\_1$), the green variable nodes $x\_1=false,x\_2=true,x\_3=false$ are all on a different schedule time of the corresponding $+x'\_1, -x'\_2, +x'\_3$. So the 5 free pegs are not enough to "mask" them and the number of distinct parents of $C\_1$ increases to $7$, like in the figure below.

![enter image description here](https://i.sstatic.net/Z3wiP.png)

Note that without the pegs, the (minimum) total cost $c\_t$ of the schedule is fixed, so we can conclude that after adding the pegs, the original formula is satisfiable if and only if the total cost of the graph is less than $c\_t + 6\*m$.

> **Comments:**
> **username_5**: The induced graph on $X_1$ can be arbitrary large for example $n/2$. How do you want assign numbers in polynomial time?  
> **username_4**: @Saeed: I've switched from polynomial-time to NPC :-))) ... if you want take a look at the proof (I wrote it quickly so it can be wrong, as well).  
> **username_5**: Hi Marzio, I tried to read it but I failed. At least I didn't get why "$x_1$ will be on the same schedule time of $+x′_1$"  
> **username_5**: Also I think this sentence is not correct while the aim you want to achieve is correct: "First of all note that the bottom peg Pj,1 must be put at schedule time s=2 because Cj is linked to the bottom of the assignment gadget and mirror chain. "  
> **username_1**: What is your hunch: is there any hope that a greedy solution could be e.g. a constant-factor approximation?  
> **username_4**: @Saeed: comment1: it means that if we choose $x_1 = true$ then, by construction, the green node corresponding to $x_1$ is on the same "line" (same schedule) of the node $+ x'_1$ of the mirror change. So their contribution to the cost of $C_1$ is only 1 and it is still 1 if we place a "peg" on the same line.  
> **username_4**: @Saeed: comment2: there is a chain of 6 pegs (all linked to $C_1$) if all of them are placed above the schedule time $s=2$ then the number of parent distinct nodes of $C_1$ is $\geq 7$. If we place one of the peg at schedule time $s=2$ then the number of parent nodes of $C_1$ can be limited to $6$ (if poperly schedule the pegs and if the assignment can satisfy the clause).  
> **username_4**: @JukkaSuomela: I really don't know; perhaps there is a greedy algorithm that works going bottom up (starting from the nodes that have outdeg=0). I'll think about it.  
> **username_5**: C1: i know what does it mean but I still cannot see "why" we have to use this assignment of schedule, why any other assignment is bigger result or wrong? C2: I know what u mean and I said imho ur goal is correct but I think it was better to write something like: if s(pj1) greater than 2 then blah blahbad happens. Because before reading to the end is not clear why cj=7 is bad (ok it's easy to feel it before reading the end but it's not logical to accept it before reading to the end).  
> **username_4**: @Saeed: C1: $x_1 = true$ is only an example; by construction, the green variable node $x_1$ must be scheduled at the same time of $+x_1, +x'_1$ or at the same time of $-x_1, -x'_1$, if $x_1$ is linked to a clause $C_j$ where it appears as a positive literal, then $C_j$ is also linked (by construction) to $+x'_1$. If you schedule $x_1$ at the same time of $+x_1$ (i.e. you set it to true) then you can "mask" both $x_1, +x'_1$ with only one of the peg of $C_j$ (each peg can be viewed as a forced +1 cost for the corresponding clause).  
> **username_0**: @MarzioDeBiasi: Nice reduction! Can't you merge the assignment gadget with the mirror chain? And, what did you use to create the figures? :)  
> **username_4**: Yes, but the graph would be too confusing and I preferred to keep  the assignment part and the "simulation" of the clauses distinct. I used [yEd](http://www.yworks.com/en/downloads.html#yEd), a great tool to draw graphs quickly (though not of the same quality of those produced with TikZiT)  

---

### Answer by username_1 on 2014-05-26. Score: 3

This is a **non-answer**, but it might help to understand the question (assuming that I understood it correctly).

Here is a simple but slightly non-trivial example:

![enter image description here](https://i.sstatic.net/grCRu.png)

Here:

* input = black graph
* output = on which blue line we place each node = when to schedule each job
* costs = orange numbers = number of predecessors with different labels

Left = simple greedy solution, right = optimal solution.

---

I would not be surprised if this was NP-hard. There seem to be opportunities for designing all kinds of gadgets. For example, here is a gadget in which we have two optimal solutions—one of the sink nodes has to pay 2 units, but you can choose which one.

![enter image description here](https://i.sstatic.net/vBQKB.png)

> **Comments:**
> **username_4**: I still don't understand the problem :-S. The OP says that if $v_2 \to v_1$ then $S(v_1) < S(v_2)$, but in your (top) examples the constraint is not satisfied. Furthermore in your top two figures, the blue numbers (the legend says that is is the output) are the same. I was thinking of a greedy approach starting from the end of one of the longest path (that must have different decreasing costs) and going backward; but probably my interpretation is wrong. The question remains a mistery :-) And what is the role (if any) of P?  
> **username_1**: @MarzioDeBiasi: In my drawing, e.g. $S(v) = 3$ is denoted by placing the node $v$ on top of the blue line labelled with "3". The constraints are satisfied; all edges point from larger labels towards smaller labels.  
> **username_1**: @MarzioDeBiasi: And forget about $P$, as far as I can see, it plays no role here.  
> **username_4**: Now I see it, thanks! :-) It seems it matches my interpretation. I'll post the greedy algorithm, perhaps you scan easily check if it is wrong and find a counterexample.  

---

### Answer by username_0 on 2014-06-03. Score: 1

I found a reduction from the Partition Problem to a modified version of the proposed problem.

### Partition Problem (Optimization)

* input: set of integers S
* output: partition of S into S1 and S1 such
  that the difference of the sums of S1 and S2 is minimized:
  $$\lvert\sum\_{s\in S1}s - \sum\_{s\in S2}s\lvert.$$

This problem is NP-hard.

### Level Assignment Problem (Optimization)

* input: a DAG $G = (V,E)$, a weight function $w:V\rightarrow\mathbb{Z}$
* output: a mapping $m:V\rightarrow[1,depth(G)]$ such that:
  1. $(v1,v2) \in E \Rightarrow m(v1) > m(v2)$
  2. the following is minimized:
     $$sum\{ numlevels(v) \times w(v) \mid v \in V\},$$
     where $$numlevels(v) = |\{m(v') \mid (v',v) \in E \}|.$$

### Reduction

The reduction from the partition problem to the level assignment problem can be done as follows: for each $s\_i \in S$, create the following gadget, where the weights are indicated between brackets:

![gadget for a number si](https://i.sstatic.net/kGcZH.png)

It is easy to see that the following mappings are obligatory:

* $m(A\_i) = 1$
* $m(B\_i) = 1$
* $m(A'\_i) = 2$
* $m(B'\_i) = 3$

Hence, the only choice left is $m(v\_i)$. When choosing $m(v\_i) = 2$, this gadget will contribute $s\_i$ to the total sum. When $m(v\_i) = 3$, it will contribute $-s\_i$.

Now, after solving the level assignment problem, group the $s\_i$ in the following way:

* $S\_1 = \{s\_i \in S \mid m(v\_i) = 2\}$
* $S\_2 = \{s\_i \in S \mid m(v\_i) = 3\}$

The gadgets related to $S\_1$ will contribute positively, those to $S\_2$ negatively. Hence, we get a total cost of:
$$\sum\_{s \in S\_1} s + \sum\_{s \in S\_2} (-s) = \sum\_{s \in S\_1} s - \sum\_{s \in S\_2} s.$$

This is the function that is minimized and it corresponds to the minimization problem of the partition problem. Hence, our problem must be NP-hard as well.

Note: the partition problem has an absolute value in the function to be minimized. This is no problem, as this can be accomplished by swapping $S\_1$ and $S\_2$.

> **Comments:**
> **username_4**: I didn't read the full reduction, yet; however in the equivalent DAG formulation of your original scheduling problem there are no "weights", but only "costs" and the cost of each node is the number of distinct parents (levels). Furthermore the cost of each node (and also the final total cost) is not given as input, but it is a function of the final level assignment  (schedule). So is this a different version from your original question?  
> **username_0**: @Marzio: when you use unit weights, this gives the same problem as the original level assignment problem. the costs in the original problem are 1 for each level, here, it is w(v_i) for each level, so it is a more general problem.  
> **username_4**: Ok! (but  the partition problem is not strongly np-hard so I think that you cannot use the same approach to prove the unit weights version). Did you check my reduction?  
> **username_0**: yes, your reduction seems ok. Could it also be possible to reduce from the Partition Decision problem (sums of S1 and S2 must be equal) and creating $s$ nodes for each $s \in S$? Or is it not allowed to created this amount of nodes in a poly reduction?  
> **username_4**: I think it's not possible because the partition problem is not strongly NP-complete. But perhaps you can try with the 3-PARTITION PROBLEM, which is strongly NPC (it is still NPC even if numbers are represented in unary) and end up with a reduction that is simpler than mine.  
> **username_0**: good idea, I will give this a try!  

---

