# Maximum size-k cut

Here's my problem,

Problem: Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and maximize the total weight of edges crossing the cut $S$.

This is a real world problem in Genetics. With the number of vertices, $|V|$, about 1,600, and $k$ about 15.

Each vertices in $G$ is a person, and edges are how much two people are related (kinship coefficient). We want to pick people to do a full genome (DNA) sequence so that we maximize the amount of DNA shared between the selected people and the rest of the pedigree, but we also don't want to spend money to sequence every people.

Approximation algorithm is okay.

Do you know any algorithm or paper that might help me with this problem?

• A $1/2$ approximation is known. See a previous question on this topic.cstheory.stackexchange.com/questions/3593/… Commented Aug 29, 2015 at 3:33
• I ended up implementing Discrete Random Greedy because it gives a good approximation factor, pretty easy to implement than others and also because it's not too slow. I was considering the Local search algorithm but it would be too slow since it has $$O(n^k)$$. Commented Aug 30, 2015 at 13:42