6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If there an is an edge from A->B, building B can be colored only after building A has been colored. 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), then the costs of coloring would be (2*1 + 1*2 + 3*3) if the ordering is (A, B, C) or (3*1 + 2*2 + 3*1) if the chosen order is (C, A, B). However, we cannot have a coloring (B, A, C) or (B, C, A) here. $\endgroup$ – Abhigyan Mehra Jul 8 '15 at 16:21
  • $\begingroup$ So if A→B and C→B, then ABC is a valid coloring? So the restriction is that if you have in-arc, at least one of your predecessors must be colored before you? $\endgroup$ – Pål GD Jul 8 '15 at 20:28
  • 1
    $\begingroup$ If I understood well, the question can be restated as : "given a DAG, find all valid topological sorts, S. Choose the one that tends to have its most costly vertices as leafs." $\endgroup$ – devoured elysium Jul 8 '15 at 21:17
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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)

|cite|improve this answer
$\endgroup$

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.