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

Improve this question
$\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$
    – Jukka Suomela
    Feb 28, 2021 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$
    – Matthieu Latapy
    Mar 1, 2021 at 8:53

2 Answers 2

Reset to default
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".

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.