patternMinor
Finding partition with maximum number of edges between sets
Viewed 0 times
numberpartitionmaximumedgeswithbetweenfindingsets
Problem
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\}$.
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\}$.
Solution
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.
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.
Context
StackExchange Computer Science Q#114754, answer score: 4
Revisions (0)
No revisions yet.