[Solved]: Proving NP-hardness of strange graph partition problem

Problem Detail: 

I am trying to show the following problem is NP-hard.

Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph

Output: Partition of $G$, $G_p=(V,E_p)$ obtained by removing any $e$ edges from $E$ which maximizes

$$\max \sum\limits_{G_i \in \{G_1,G_2,...,G_k\}} \frac1{|G_i|}\left(\sum_{v_j \in V_i}w(v_j)\right)^{\!2},$$

where $G_p=G_1 \cup G_2 \cup \dots \cup G_k$ and elements of $G$ are disjoint.
$V_i$ is the vertex set for $G_i$ and $w(v_j)$ is the weight for vertex $v_j$

Plain English explanation: We wish to partition a graph by removing $e$ edges to maximize an objective. The objective computes for each of the resulting disjoint subgraphs the sum of the vertices for the subgraph, squares that value, and divides by the cardinality. Finally we sum this over all subgraphs.

So far I have attempted to reduce from NP-hard problems such as ratio-cut, partition (non-graph problem), and max multicut. I've also attempted to show special cases of the problem are NP-hard (less ideal). The reason I suspect this problem to be NP-hard (besides most graph partitioning problems being NP-hard) is the presence of the cardinality term and cross terms between partition weights. Any input/problem suggestions would be helpful. A NP-hard proof for any kind of specific graph would be useful.

Asked By : Optimizer

Answered By : Tianren Liu

Let's reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem. In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts).

A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s_1,s_2,s_3\in V$, find a minimum set of edges $E'\subseteq E$ such that the removal of $E'$ from $E$ disconnects each terminal $s_i$ from the others. Its decision version is to find out if it's possible to disconnect $s_1,s_2,s_3$ by removing no more than $w$ edges, where $w$ is a part of the input.

Given graph $G$, terminals $s_1,s_2,s_3$ and integer $w$, we would like to reduce the 3-way cut problem to your "strange graph partition problem". For each terminal $s_i$, we add $N$ more verteces to be its neighbors. As hinted by its name, $N$ would be a sufficiently large number. The weight of all verteces are 0 except for $s_1,s_2,s_3$, whose weights are $1,10,100$ resp. Denote this new graph by $G'$. It's obvious that $s_1,s_2,s_3$ can be disconnected by removing $w$ edges in $G$ if and only if they can be disconnected by removing $w$ edges in $G'$.

If a partition $G'_p$ of $G'$ disconnects $s_1,s_2,s_3$, its score is roughly $10101/N$, or more precisely, no less than $$\frac{10101}{N+n}$$ as the part containing $s_i$ has no more than $N+n$ verteces, where $n$ is the number of verteces in $G$. On the other hand, if a partition $G'_p$ fails to disconnect $s_1,s_2,s_3$, its score is no more than $$\frac{10060.5}{N-w}$$. When $N$ is sufficiently large, $\frac{10101}{N+n} > \frac{10060.5}{N-w}$, so $G$ can be 3-way partitioned by removing $w$ edges if and only if $G'$ has a partition removing $w$ edges, whose score is at least $\frac{10101}{N+n}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30816