2
$\begingroup$

Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?

For example, for the following set of edges of a graph with vertex set $\{1, 2, 3, 4, 5, 6\}$: $\{(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)\}$, one possible "maximum" partition is $\{\{1, 3, 4, 6\}, \{2, 5\}\}$ with $4$ edges between the sets $\{1, 3, 4, 6\}$ and $\{2, 5\}$.

$\endgroup$
4
$\begingroup$

If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.

Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.

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