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.

  • $\begingroup$ Try reduction to the subset-sum problem? $\endgroup$ – xiamx Oct 10 '14 at 17:36
  • 2
    $\begingroup$ So $G_1,G_2,\ldots,G_k$ are intended to be the connected components of the graph $G_p=(V,\:E-R)$, where $R\subseteq E$ satisfying $\lvert R\rvert=e$ is the set of removed edges? $\endgroup$ – David Eisenstat Oct 11 '14 at 2:22
  • $\begingroup$ @D.W. I have tried. Having more trouble with the cardinality term than the squaring. For the squaring, I think it might be possible to construct a graph where the cross-terms disappear in the solution by alternating positive and negative weighted edges in a chain or grid graph $\endgroup$ – Optimizer Oct 11 '14 at 16:17
  • $\begingroup$ @DavidEisenstat yes $\endgroup$ – Optimizer Oct 11 '14 at 16:18
  • $\begingroup$ @xiamx Be careful; you should reduce from a problem that is hard, and not vice versa. $\endgroup$ – Juho Oct 11 '14 at 20:34

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

  • $\begingroup$ @Optimizer, in the original problem, minimum 3-way cut, vertex has no weight. So it's not possible to restrict its input on vertex weight. On the other hand, your problem involves weighted vertex. So the above proof shows that your problem is NP-complete even if you restrict the input s.t. most verteces have zero weight. $\endgroup$ – Tianren Liu Oct 15 '14 at 14:17
  • $\begingroup$ There is no terminal in the minimum k-cut problem. Are you sure about the NP-complete of the problem you put there? $\endgroup$ – InformedA Oct 16 '14 at 1:14
  • $\begingroup$ @randomA, minimum $k$-cut problem has several variants. One variant includes $k$ terminals as part of the input, the goal is find minimum cost $k$-cut that disconnects these $k$ terminals. This variant is named as multiway cuts problem in the paper I cited. I should clarify it in my answer, thank you for your comment. $\endgroup$ – Tianren Liu Oct 16 '14 at 1:57
  • $\begingroup$ @randomA This has a good description of this version of the problem: math.mit.edu/~goemans/18434S06/multicuts-brian.pdf $\endgroup$ – Optimizer Oct 16 '14 at 9:44

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.