# Minimize Cumulative Cost on Topological Sort

We are given a n-vertex DAG $$G=(V,E)$$ and also given a cost function $$c: V \rightarrow \Bbb N$$.

Given a topological sort $$S = v_1,v_2,...,v_n$$, it has associated a sorting cost $$S_c = \sum_{i=1}^{n} C(v_i)$$ where $$C(v_i)$$ is the cost of choosing $$v_i$$ at that point: i.e. the sum of the cost functions of all vertices that were candidates at the point of choosing $$v_i$$, but they weren't chosen. Obviously, precedent vertices to $$v_i$$ in $$S$$ (already chosen vertices) are not included in this sum.

The idea is to find a topological sort $$S$$ that minimizes $$S_c$$. I think its a NP-hard problem, but would there be any approximation algorithm, or at least some smart heuristic? I tried to find this exact same problem but I couldn't find it... just similar ones.

• What makes a given vertex $v$ a "candidate" at a given location $i$? Any vertex that is not yet chosen? Or maybe any vertex such that there is a topological order with the preceding $i-1$ vertices where they are, and that vertex $v$ in position $i$? (These are not the same.) Nov 5, 2021 at 13:23
• Scheduling/ordering a DAG (representing unit time jobs) on a single machine to minimize weighted completion time is NP-Hard. Here each vertex has a weight $w(v)$ and $C(v_i) = w(v_i) \cdot i$ since $i$ is the completion time of job at position $i$. Nov 5, 2021 at 13:52
• I see. (Equivalently $C(v_i)$ is the sum over the vertices $v$ not yet chosen of $c(v_i)$.) Is this single machine scheduling with precedence constraints? That problem seems to be NP hard but 2-approximable in polytime.. Nov 5, 2021 at 14:45
• A "candidate" is a vertex not yet chosen that has all its incoming vertices already in the sort at that point. So, it would be your second option. Other not-yet chosen vertex may not be a candidate because there are still other vertices that need to go first (dependency constraint) Nov 5, 2021 at 17:34
• Your objective is not very "natural" if the cost itself depends on the evolving schedule. What is the motivation? Nov 5, 2021 at 20:38