Traversing a graph with respect to some partial order Recently I was faced with the following Graph traversal problem:
"Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented by edges in the DAG. If there is an edge from A->B, this would mean building B can only be colored after building 'A' has been colored. Also given is an array which provides the initial cost of coloring each building (vertex) in the graph. The actual cost of coloring a building 'v' is I(v) * C(v), where 'I(v)' is the number of buildings colored before 'v' plus '1' and C(v) is its initial cost of coloring provided in the array. Find the minimum actual cost of coloring all the buildings in the graph."

If there an is an edge from A->B, building B can be colored only after building A has been colored. Of course, there can be multiple routes to B in the graph, for instance from A->B and C->B. In this case if the provided array is (2,1,3) for coloring (A, B, C), and we choose to color building in the order of (A, B, c) then total cost = 1*C(A) + 2*C(B) + 3*C(C) = 1*2 + 2*1 + 3*3 = 13. However we cannot have an ordering where B is colored first.

I came up with a brute force solution to this problem. Topological sorting might help, but I couldn't really figure out how. Any suggestions?
This is a job-shop scheduling problem, known as $1|\textrm{prec},p_i=1|\Sigma w_i C_i$. It is $NP$-complete.

Lenstra, J.K. and Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. In Operations Research, vol. 26, pp. 22-35 (1978)

Sadly the paper is not open-access. They show $NP$-hardness by reduction from Linear Arrangement (also known as Graph Bandwidth)