Selecting one node from each group in k-partite graph

Question

I have a k-partite directed graph. I want to pick one subgraph with k-vertices where each vertex of this subgraph is exactly one vertex from one of the k parts and I want this subgraph to have the minimum sum of weights on the edges. Is there a known algorithm to solve this problem ?

Answer 1

You can reduce vertex cover to your problem. Take an arbitrary graph $G = (V,E)$ and construct graph $G'= (V', E', w')$ where \begin{align} V' &= V\times\{0,1\} \cup \{2\} \\ E' &= \Big\{\big\{(v_1,0),(v_2,0)\big\}\ \Big|\ \{v_1,v_2\} \in E\Big\} \cup \Big\{(2,v)\ \Big|\ v \in V\Big\} \\ w'\Big(\big\{v_1',v_2'\}\Big) &= \begin{cases}1 &\text{ for }v_1 = 2 \lor v_2 = 2 \\|V|^2 &\text{ otherwise}\end{cases} \end{align}

This graph is $|V| + 1$-partie and the idea is that we take two copies of $V$ so that $(v,x)$ means $v$ is in the cover for $x=1$. The additional vertex "$2$" provides an incentive to make the cover as small as possible, while and edge between "off" vertices penalizes heavily any edge that wouldn't be covered.

This proves your problem is NP-hard. Of course, you could solve it by a brute-force approach, but it will take an exponential time.

I hope this helps $\ddot\smile$