0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – wet Nov 2 '16 at 7:34
0
$\begingroup$

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$

$\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.