1
$\begingroup$

Consider the following reduction: $m$-colouring to $m$-partition.

Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices into $m$ parts $\{V_1, V_2, \ldots , V_m\}$ such that at least $j$ of the edges have their endpoints in different parts of the partition?

I was able to come up with the reduction, but now I'm stuck at this question:

What I need to find is the values of $m$ where the reduction implies that $m$-Partition is NP-complete?

Improve this question
$\endgroup$
  • $\begingroup$ For what values of m is m-coloring NP-complete? What research have you done on that? $\endgroup$ – D.W.♦ Apr 26 '20 at 7:17
  • 1
    $\begingroup$ @Matthew Not quite: the problem is still NP-complete for 4 colors. When you say "a map" you mean a planar graph and that's true, but in general it's still hard. $\endgroup$ – Juho Apr 26 '20 at 9:14
  • 1
    $\begingroup$ @Matthew No, consider the complete graph on 5 vertices, or more generally any graph with a large clique. $\endgroup$ – Juho Apr 27 '20 at 4:34
  • 1
    $\begingroup$ @Matthew To blow your mind even more, they are not the same problems. A graph without a large clique can still require a lot of colors :-) Have a look at the Mycielskians. $\endgroup$ – Juho Apr 27 '20 at 8:09
  • 1
    $\begingroup$ @Matthew Do as many exercises as you can, there's no substitute for that. Play around with graphs and reductions and you will improve over time. I don't have a particular resource in mind - there's a lot of books and other material that is good. $\endgroup$ – Juho Apr 28 '20 at 7:18
1
$\begingroup$

The $1$-partition problem is trivial, since there is only one possible partition.

The $2$-partition problem is the same as MAX-CUT, which is known to be NP-complete.

For $m > 2$, the $m$-partition problem is NP-complete by reduction from $m$-coloring, which is NP-complete for that range of $m$.

Improve this answer
$\endgroup$
  • $\begingroup$ so m>=2 is your answer? $\endgroup$ – Objori Apr 26 '20 at 14:33
  • $\begingroup$ My answer is just what I wrote. $\endgroup$ – Yuval Filmus Apr 26 '20 at 14:35

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.