Skip to main content
MathOverflow

Return to Answer

Bounty Ended with 50 reputation awarded by CommunityBot
added update
Source Link
domotorp
domotorp
  • 19.1k
  • 3
  • 59
  • 128

Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem becomes $NP$-complete for general graphs, see E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis: The complexity of multiterminal cuts.

Earlier stuff: For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem becomes $NP$-complete for general graphs, see E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis: The complexity of multiterminal cuts.

Earlier stuff: For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

added that it's only for two colors
Source Link
domotorp
domotorp
  • 19.1k
  • 3
  • 59
  • 128

ThisFor two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

This can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

Source Link
domotorp
domotorp
  • 19.1k
  • 3
  • 59
  • 128

This can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.