<p>Your problem is NP-hard. I show this by a reduction from the <em>shuffle problem</em>: given words $w, w_1, \ldots, w_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (aka "shuffle") of $w_1, \ldots, w_n$. This problem is NP-hard: see Warmuth &amp; Haussler, <em><a href="https://www.sciencedirect.com/science/article/pii/0022000084900187" rel="noreferrer">On the complexity of iterated shuffle</a></em>, JCSS, 1984, Theorem 3.1.</p>

<p>Given an instance $w, w_1, \ldots, w_n$ of this problem, and writing $l_i := |w_i|$ for all $1 \leq i \leq n$, we build the DAG $G$ as a union of path graphs $L_1, \ldots, L_n$, where each $L_i$ for $1 \leq i \leq n$ has $l_i$ vertices written $v^i_1, \ldots, v^i_{l_i}$. Now, we define the cost function $f$ as follows: for each $1 \leq i \leq n$ and $1 \leq j \leq l_i$, for each $1 \leq k \leq |w|$, we set $f(v^i_j, k)$ to be $0$ if the $j$-th character of $w_i$ is the same as the $k$-th character of $w$, and $1$ otherwise.</p>

<p>This reduction is clearly in PTIME, and it is clear that the minimum cost of a topological sort is 0 iff there is an interleaving of the path graphs realizing exactly the word $w$, showing that the reduction is correct.</p>

<p>(Shameless ad: If you're interested in NP-hard variants of topological sorting, you may be interested about a <a href="https://arxiv.org/abs/1707.04310" rel="noreferrer">recent preprint</a> of mine which studies the complexity of finding topological sorts that fall into fixed regular languages.)</p>

CC BY-SA 3.0
2018-04-25T13:32:19.027Z
I am curious. Does the complexity change when n is bounded or fixed? Say, for n = 2, that is given, w, w1, w2, is the problem NP-hard?
rnbguy
CC BY-SA 3.0
2018-04-27T10:00:14.137Z
If your question is about the shuffle problem, then it is tractable (in NL) when $n$ is constant. Essentially, you just do a dynamic algorithm on the strings. A generalization of this is shown as Proposition C.2 of https://arxiv.org/abs/1707.04310.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2018-04-28T17:01:43.537Z
From what I understood, the decision version of the problem is NL. What if I want to compute a topological sort if any exists?
rnbguy
CC BY-SA 3.0
2018-04-30T09:40:26.010Z
I think the computation version should clearly be in PTIME by reconstructing the topological sort from the dynamic programming algorithm in the usual way (like in the algorithm to compute the Levenshtein distance). Probably this also shows that it can be implicitly computed in NL (you don't have time to write the whole sort but you can compute any bit of the output in NL), though there may be some technicalities.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2018-02-28T18:32:23.940Z
2018-02-28T18:32:23.940Z
Antoine Amarilli 'a3nm'
<p>We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ordering is $\sum_{i=1}^n c(v_i,i)$.</p>

<p>Is finding the minimum cost topological ordering NP-hard?</p>

CC BY-SA 3.0
2018-03-01T01:04:58.827Z
Scheduling unit time jobs with weights and precedence constraints to minimize weighted completion time on a single machine is NP-Hard. The scheduling problem is a special case of your problem where $c(v_i,i) = w(v_i) i$.
Chandra Chekuri
<ds.algorithms><directed-acyclic-graph><topological-sorting>
Minimum cost topological ordering
Chao Xu
# Minimum cost topological ordering

(Asked by: username_0 on 2018-02-28)

We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v\_1,\ldots,v\_n$, the cost of the ordering is $\sum\_{i=1}^n c(v\_i,i)$.

Is finding the minimum cost topological ordering NP-hard?

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

> **Comments:**
> **username_1**: Scheduling unit time jobs with weights and precedence constraints to minimize weighted completion time on a single machine is NP-Hard. The scheduling problem is a special case of your problem where $c(v_i,i) = w(v_i) i$.  

---

## 1 answers

### Answer by username_2 on 2018-02-28. Score: 9 | Accepted answer

Your problem is NP-hard. I show this by a reduction from the *shuffle problem*: given words $w, w\_1, \ldots, w\_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (aka "shuffle") of $w\_1, \ldots, w\_n$. This problem is NP-hard: see Warmuth & Haussler, *[On the complexity of iterated shuffle](https://www.sciencedirect.com/science/article/pii/0022000084900187)*, JCSS, 1984, Theorem 3.1.

Given an instance $w, w\_1, \ldots, w\_n$ of this problem, and writing $l\_i := |w\_i|$ for all $1 \leq i \leq n$, we build the DAG $G$ as a union of path graphs $L\_1, \ldots, L\_n$, where each $L\_i$ for $1 \leq i \leq n$ has $l\_i$ vertices written $v^i\_1, \ldots, v^i\_{l\_i}$. Now, we define the cost function $f$ as follows: for each $1 \leq i \leq n$ and $1 \leq j \leq l\_i$, for each $1 \leq k \leq |w|$, we set $f(v^i\_j, k)$ to be $0$ if the $j$-th character of $w\_i$ is the same as the $k$-th character of $w$, and $1$ otherwise.

This reduction is clearly in PTIME, and it is clear that the minimum cost of a topological sort is 0 iff there is an interleaving of the path graphs realizing exactly the word $w$, showing that the reduction is correct.

(Shameless ad: If you're interested in NP-hard variants of topological sorting, you may be interested about a [recent preprint](https://arxiv.org/abs/1707.04310) of mine which studies the complexity of finding topological sorts that fall into fixed regular languages.)

> **Comments:**
> **username_3**: I am curious. Does the complexity change when n is bounded or fixed? Say, for n = 2, that is given, w, w1, w2, is the problem NP-hard?  
> **username_2**: If your question is about the shuffle problem, then it is tractable (in NL) when $n$ is constant. Essentially, you just do a dynamic algorithm on the strings. A generalization of this is shown as Proposition C.2 of https://arxiv.org/abs/1707.04310.  
> **username_3**: From what I understood, the decision version of the problem is NL. What if I want to compute a topological sort if any exists?  
> **username_2**: I think the computation version should clearly be in PTIME by reconstructing the topological sort from the dynamic programming algorithm in the usual way (like in the algorithm to compute the Levenshtein distance). Probably this also shows that it can be implicitly computed in NL (you don't have time to write the whole sort but you can compute any bit of the output in NL), though there may be some technicalities.  

---

