Is there an algorithm to minimize working set during a topological traversal?

Question

I have a dependency graph of tasks, which forms a DAG. I'm looking for an algorithm to calculate the optimal topological traverse to minimize the "working set". Specifically, I define the current working set as the set of nodes which have been visited, and which have at least one outgoing edge which is untraversed.

Even more useful would be an algorithm to calculate the optimal topological traversal which minimizes the number of cache evictions, given a fixed size cache for the working set.

Is there an algorithm to calculate this topological traversal? I can do it greedily from the topological ordering, but suspect that's suboptimal.

Answer 1

Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs.

We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph, whose pathwidth we want to compute. Now create an directed graph $H$, with vertex $v'$ for each vertex $v$ of $G$. For each edge $(u, v)$ of $G$, create a vertex $e_{(u,v)}$ and directed edges $(v', e_{(u,v)}'), (u', e_{(u,v)}')$.

Now consider a topological ordering of $H$. Define the corresponding sequence of working sets as $X_1, \ldots, X_p$. We prove that $X_1, \ldots, X_p$ is a path-decomposition of $G$. The working sets include only vertices of type $v'$, because the other vertices do not have outgoing edges. The working sets by definition satisfy the intersection property $i \le j \le k \rightarrow X_i \cap X_k \subseteq X_j$. If there is an edge $(u, v)$ in $G$, then there are edges in $H$ from both $v'$ and $u'$ to $e_{(u,v)}'$ so there must be a working set $X_i$ with $v', u' \in X_i$. Therefore each edge is a subset of some bag of the path decomposition and therefore $X_1, \ldots, X_p$ is a path decomposition of $G$.

We can also show that any path-decomposition of $G$ corresponds to a topological ordering of $H$ (consider the elimination ordering of the underlying interval graph). $\square$

For positive results, I would suggest at looking at some analogies of pathwidth for DAGs in literature. With a quick search I found the notions of directed pathwidth and DAG-width, but seems that they are not relevant here as they are trivial for DAGs.