1
$\begingroup$

Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(P_i\times P_i)\cap E|$.

May someone please provide the name of this problem and/or references?

If $k$ is larger than or equal to the chromatic number of $G$, then the number of edges under concern is $0$. But if $k$ is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by $m=|E|$ (in the case $k=1$).

$\endgroup$
2
  • 2
    $\begingroup$ If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph". $\endgroup$ Feb 28 at 21:52
  • 1
    $\begingroup$ Thank you @JukkaSuomela, this seems like the answer I was looking for; please post it as an answer so I may accept it. $\endgroup$ Mar 1 at 8:53
3
$\begingroup$

(Copied from a comment:)

If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".

$\endgroup$
1
$\begingroup$

I think under typical terminology this would be called "Min k-Uncut" (note, Min Uncut asks for a partition into two that minimizes the number of edges not cut, and Max k-Uncut asks for a k partition maximizing the number of uncut edges). Googling seems to find some references.

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