I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated.Problem definitionGiven 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.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$. 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) $QuestionIs determining the lowest-cost assignment of tasks $v$ to servers ($S_A$ and $S_B$) NP-hard?Attempted approachI have tried transforming the graph $G$ to a new graph $G^Z$ with doubled vertices, as shown in the picture below.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.
NP-hardness of tasks graph assignment to two heterogenous servers
cc.complexity theory;graph theory;np hardness;optimization