The problem of finding the minimum edge deletion partitioning (minimizing the sum of weights of monochromatic edges) in a planar graph with arbitrary integer edge weights is NP-hard.

Reasoning:

The problem can be rephrased as maximizing the sum of weights of edges crossing the vertex partition (since the total edge weight is fixed, minimizing monochromatic edges is equivalent to maximizing c...

Short answer Your problem is exactly the weighted correlation clustering objective on a (not necessarily complete) graph: you want to find a partition of the vertices so as to maximize agreements, where an agreement is “put endpoints together” on a negative-weight edge and “put endpoints apart” on a positive-weight edge. Formally, if we let A be the total weight of agreements A = sum_{e=(u,v), w(e...

First, I recall that for general graphs, this probl...

Minimum Edge Deletion Partitioning of a Planar Graph - Time Complexity Analysis

This problem is about coloring vertices of a planar graph to minimize the sum of weights of monochromatic edges, where edge weights can be positive or negative.

Complexity Analysis

The problem is NP-hard for planar graphs with arbitrary edge weights.

I can prove this by reducing from the Maximum Cut proble...

Here is a brief summary of what is known once you recognize that your problem

Minimize  ∑_{uv∈E} w(uv)·[color(u)=color(v)]
over all vertex‐partitions (with arbitrarily many parts)

is nothing but the weighted “minimum‐disagreement” or correlation–clustering objective on a planar graph. In the general (non-planar) world this is already NP-hard; one needs to check whether planarity mak...

What you are looking at is exactly the (weighted) correlation–clustering / multicut problem:

• For every edge e let x(e)=1 if its two endpoints end up in different colour classes (“the edge is cut”) and x(e)=0 otherwise.
• Your objective
min ∑{e monochromatic} w(e)
is the same as
max ∑{e cut} w(e) ,
because ∑_{e∈E}w(e) is a constant.
• The vector x has to b...

This is an interesting variant of the minimum edge deletion partitioning problem restricted to planar graphs. Let me analyze this problem systematically.

Problem Analysis

The problem asks us to partition the vertices of a planar graph to minimize the total weight of monochromatic edges (edges within the same partition). This is equivalent to maximizing the weight of edges between different pa...

An excellent question! This problem delves into a classic graph partitioning problem and how its complexity can change dramatically with structural constraints like planarity.

Let's break down the problem and connect it to well-known problems in graph theory and complexity.

1. Reformulating the Problem

Your problem is: Given: A planar graph and a weight function $w:E \rightarr...

The optimisation task you describe is exactly the (weighted) 0-/∞ version of

  Correlation-Clustering (also called Multicut, Cluster-Editing without edge insertions, or   Minimum Disagreement).

Instance  A graph G=(V,E) with an integral weight w(e) on every edge.

Solution  A partition Π of V (equivalently: a colouring with an arbitrary number of colours).

Cost
 cost(Π)=Σe∈E w(e)  if the tw...