1
$\begingroup$

Given an undirected graph $G=(V,E)$, the max-cut problem asks for the partition $S_1,S_2\subset V$ , s.t., the number of edges going from $S_1$ to $S_2$ are maximized.

Is it possible to maximize the sum of all edges between $S_1$ and $S_2$ at the same time we minimize the sum of internal edges in $S_1$ partition?

Improve this question
$\endgroup$
3
  • $\begingroup$ The question is unclear to me. $\endgroup$
    – Brendan McKay
    Commented Jul 30, 2022 at 12:40
  • $\begingroup$ Apparently, the problem is to find a subset $S$ of the set of vertices of graph $G$ such that the number of edges between $S$ and the complementary subset is maximal (that is, we deal with maximal cut) and the number of edges in $S$ is as small as possible. But this is what the example illustrates is not clear. $\endgroup$
    – kabenyuk
    Commented Jul 30, 2022 at 17:06
  • $\begingroup$ kabenyuk, your interpretation is correct, I will remove the figure to avoid misinterpretations. $\endgroup$
    – Weslley Lioba Caldas
    Commented Jul 31, 2022 at 14:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .