Traversing a graph with respect to some partial order

Question

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?

Answer 1

This can be formulated as an instance of integer linear programming, and then handed to an ILP solver. You could try that to see if it leads to any speedups.

The formulation: introduce zero-or-one variables $x_{v,t}$, where $x_{v,t}=1$ means that vertex $v$ was colored at time $t$. (Here $v$ ranges over vertices of the graph, and $t$ ranges over $1,2,\dots,n$, where $n$ is the number of vertices.) The precedence constraints mean that for every edge $v\to w$, we introduce an inequality

$$x_{w,t} \le x_{v,1}+x_{v,2}+\dots + x_{v,t-1}.$$

Also we require that every vertex be colored exactly once: $x_{v,1}+\dots+x_{v,n}=1$ for each $v \in V$, and you can only color one vertex at each time instant: $\sum_{v \in V} x_{v,t}=1$, for each $t=1,\dots,n$. Now the goal is to minimize the objective function

$$\Phi = \sum_{v,t} t C(v) x_{v,t},$$

which is a linear function of the variables. So, this is an ILP instance and can be fed to an off-the-shelf ILP solver.

ILP solvers incorporate a number of clever heuristics. If you're lucky, it's possible that one of them might help solve the problem faster than brute-force enumerating all valid topological sorts of the graph.

Answer 2

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)