I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated.

Problem definition

Given is a directed acyclic graph $G=(V,E)$ representing a set of computation tasks which need to be performed. Each vertex $v$ represents a single, non-divisible computation task. Each edge $e$ denotes communication between two tasks, i.e. transmission of output data from one task to another.

enter image description here

Each computation task can be executed on one of two servers: $S_A$ or $S_B$. The servers have differing architectures, so $S_A$ is able to perform some computations more efficiently than $S_B$, and vice versa. Therefore, each computation task has two values associated with it: $c_A(v)$ and $c_B(v)$, which denote the cost of executing the task on server $S_A$ and $S_B$, respectively.

Consequently, each edge $e$ has two associated values representing the data transmission cost: $t_{internal}(e)$ (both tasks executed on the same server) and $t_{external}(e)$ (the task are executed on different servers). We assume $t_{internal}(e) = 0$ (i.e. internal server communication has no significant cost). $t_{external}(e) > 0$ and is proportional to the amount of data which needs to be transmitted between the tasks. The transmission cost is symmetrical, i.e. it does not matter if we transmit the data from $S_A$ to $S_B$ or from $S_B$ to $S_A$.

enter image description here

The total cost of computation $C$ is the sum of costs of individual task executions and the costs of communication between tasks, i.e.:

$C = \sum\limits_{v \in V}c(v) + \sum\limits_{e \in E}t(e) $


Is determining the lowest-cost assignment of tasks $v$ to servers ($S_A$ and $S_B$) NP-hard?

Attempted approach

I have tried transforming the graph $G$ to a new graph $G^Z$ with doubled vertices, as shown in the picture below.

enter image description here

In the new graph, the problem is to choose one vertex from each pair ($v^A$, $v^B$) so that the total weight of edges remaining in the resulting graph would be minimal.

I have tried to find possible analogies to well-known graph theory problems (e.g. maximum independent set, vertex cover, graph partitioning, etc.). Alas, to no avail.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy