# Selecting one node from each group in k-partite graph

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 ?

• You'll get more attention on the Computer Science StackExchange for this I imagine. Is there always an edge between vertices of different partitions? If not then of course not every $k$-partite graph will even have an answer. Assuming you are already given the partitions then this looks like your average $\text{NP}$ problem. Otherwise you have to find them and it's going to be even harder. – wet Nov 2 '16 at 7:34

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.
I hope this helps $\ddot\smile$