8
$\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?

Improve this question
$\endgroup$
1
  • 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
    Commented Mar 1, 2018 at 1:04

1 Answer 1

Reset to default
9
$\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.)

Improve this answer
$\endgroup$
4
  • $\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
    Commented Apr 25, 2018 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$
    – Antoine Amarilli 'a3nm'
    Commented Apr 27, 2018 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
    Commented Apr 28, 2018 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$
    – Antoine Amarilli 'a3nm'
    Commented Apr 30, 2018 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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