5
$\begingroup$

Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i \mid \exists k>i: (v_j,v_k)\in A\}|$. The problem is: given a DAG, find a topological ordering with minimum cost.

In other words, for each $i$, I consider that a vertex that appeared before $i$ is pending if it still has one or more out-neighbours that did not appear yet, and I want to minimize the maximum number of pending vertices at any time.

It looks like some graph measures (say treewidth, etc.), but I didn't manage to find this in the literature. Has it been studied before?

I'd say it's almost-certainly NP-hard (although I don't have a proof)... would there be any approximation algorithm, or at least some smart heuristic?

Edit: for a little bit of context. This came up while I was trying to program a tool solving a completely unrelated string problem. To make things short: the graph models my input, and I need to compute a set of strings $\mathcal S(v)$ for each node $v$. To compute each $\mathcal S(v)$, I need to know $\mathcal S(u)$ for each node $u$ with an arc $u\rightarrow v$. In the end I'm only interested in $\mathcal S(v)$ for the targets of the graph. Now I want to improve the memory needs: the sets $\mathcal S$ are huge, so I want to keep only a minimum number of them in memory at any time: they correspond to the "pending vertices" defined above.

$\endgroup$
  • 2
    $\begingroup$ What's the context in which you ran across this? Is there a motivation or practical application? $\endgroup$ – D.W. Jul 22 '16 at 17:06
  • $\begingroup$ @DW somehow, yes... see edit $\endgroup$ – tarulen Jul 26 '16 at 11:04
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Pebble_game $\endgroup$ – domotorp Jul 26 '16 at 13:24
  • 1
    $\begingroup$ Your underlying graph problem is very close to One-Shot Black Pebbling, which I wouldn't have remembered if domotorp hadn't mentioned pebbling games. ​ The main or only part of reducing your underlying graph problem to that is removing vertices from which no targets are reachable, and then attaching [an outward edge to a new sink vertex] to each target. ​ If you need to hold S of the targets in memory the whole time (rather than processing them as you get them), then finally add a new vertex with an edge from each former-sink. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user6973 Jul 26 '16 at 13:53
  • $\begingroup$ Also, have you tried approximating the treewidth of the induced undirected graph? ​ This seems like the sort of problem that might be FPT when parameterized by pathwidth, or even treewidth. ​ ​ ​ ​ $\endgroup$ – user6973 Jul 26 '16 at 14:09
4
$\begingroup$

This problem is NP-complete, as the following reduces to it: https://cstheory.stackexchange.com/a/1936/419

The sketch of the reduction is as follows. From a set of tasks $T$ with $n$ tasks and some costs (not to be confused with your cost function!), we will make a DAG that has $N$ indegree 0 vertices (sources), and $N$ outdegree 0 vertices (sinks), where $N$ is some big ($poly(n)$ size) number to be specified later. The DAG will also have an indegree $N$ vertex that has to come right after the sinks, and, similarly, an outdegree $N$ vertex that has to come right before the sources. For each task, we have a vertex that must be between the indegree $N$ vertex and the outdegree $N$ vertex by adding an edges from and to them, respectively. This achieves that the task-vertices are not mixed with the sources and sinks.

Finally, for every task $t$ with a positive cost $c(t)$ we add $nc(t)$ edges from some sources, and for every task $t$ with a negative cost $c(t)$ we add $nc(t)$ edges to some sinks. This achieves that the edges between the tasks won't matter, only the costs will determine the thickness cost that you've defined.

I don't know anything about approximation and heuristics.

$\endgroup$
  • $\begingroup$ Thanks, nice reduction. This confirms my intuition about hardness... but I'm still looking for any positive way to approach it $\endgroup$ – tarulen Jul 26 '16 at 11:06

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.