5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Chandra Chekuri Mar 1 '18 at 1:04
8
$\begingroup$

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, 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 of mine which studies the complexity of finding topological sorts that fall into fixed regular languages.)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rnbguy Apr 25 '18 at 13:32
  • 1
    $\begingroup$ 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 arxiv.org/abs/1707.04310. $\endgroup$ – a3nm Apr 27 '18 at 10:00
  • $\begingroup$ From what I understood, the decision version of the problem is NL. What if I want to compute a topological sort if any exists? $\endgroup$ – rnbguy Apr 28 '18 at 17:01
  • 1
    $\begingroup$ 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. $\endgroup$ – a3nm Apr 30 '18 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.