<p>I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from standard min, max cut problems. I have searched for a suitable algorithm for several days but with no success. Maybe someone can give a suggestion or at least come up with a standard name for such problem?</p>

<p>The problem is as follows:</p>

<p><strong>Input:</strong> Undirected graph $V$ with vertex weights $u_i$ and edge weights $w_{ij}$.</p>

<p><strong>Output:</strong> Graph partition in two components $S_1$ and $S_2$ to minimize the following:<br>
$$\max((\sum_{i\in S_1}u_i-\sum_{i,j\in S_1}w_{ij}), (\sum_{i\in V-S_1}u_i-\sum_{i,j\in V-S_1}w_{ij})) $$<br>
Basically, if we define $weight$ of a component as the sum of weights of its vertices minus the sum of weights of its edges, then I would like to find a pair of components such that a maximal weight out of the two components is minimal over all possible pairs. The edges between two components are removed.</p>

<p>Here is an example of possible graph partition (there may be several). The numbers mean the weights:<br>
<a href="https://i.sstatic.net/EkDEN.png" rel="noreferrer"><img src="https://i.sstatic.net/EkDEN.png" alt="Possible partition of a weighted graph"></a>
Thanks in advance for suggestions!</p>

CC BY-SA 3.0
2016-04-04T18:40:07.510Z
Your problem is NP-hard.  Hint: reduce from Partition to the special case of your problem with $w_{ij}=0$.
Neal Young
CC BY-SA 3.0
2016-04-04T18:58:35.157Z
@NealYoung do you mean to prove NP-hardness by reducing to the special case? That's true, I agree. But I hoped for some heuristic algorithm or at least something better than brute force...
Kirill
CC BY-SA 3.0
2016-04-04T21:43:12.470Z
Yes.  As for heuristics, maybe integer linear programming?  (You can modify the reduction above to show that deciding whether there is solution of cost zero is NP-hard, so, unless P=NP, there is no poly-time algorithm with multiplicative-approximation guarantee.)
Neal Young
<cc.complexity-theory><graph-theory><partition-problem>
Graph partition with weighted vertices and edges
Kirill
# Graph partition with weighted vertices and edges

(Asked by: username_0 on 2016-04-04)

I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from standard min, max cut problems. I have searched for a suitable algorithm for several days but with no success. Maybe someone can give a suggestion or at least come up with a standard name for such problem?

The problem is as follows:

**Input:** Undirected graph $V$ with vertex weights $u\_i$ and edge weights $w\_{ij}$.

**Output:** Graph partition in two components $S\_1$ and $S\_2$ to minimize the following:  
$$\max((\sum\_{i\in S\_1}u\_i-\sum\_{i,j\in S\_1}w\_{ij}), (\sum\_{i\in V-S\_1}u\_i-\sum\_{i,j\in V-S\_1}w\_{ij})) $$  
Basically, if we define $weight$ of a component as the sum of weights of its vertices minus the sum of weights of its edges, then I would like to find a pair of components such that a maximal weight out of the two components is minimal over all possible pairs. The edges between two components are removed.

Here is an example of possible graph partition (there may be several). The numbers mean the weights:  
[![Possible partition of a weighted graph](https://i.sstatic.net/EkDEN.png)](https://i.sstatic.net/EkDEN.png)
Thanks in advance for suggestions!

**Tags:** cc.complexity-theory, graph-theory, partition-problem
> **Comments:**
> **username_1**: Your problem is NP-hard.  Hint: reduce from Partition to the special case of your problem with $w_{ij}=0$.  
> **username_0**: @NealYoung do you mean to prove NP-hardness by reducing to the special case? That's true, I agree. But I hoped for some heuristic algorithm or at least something better than brute force...  
> **username_1**: Yes.  As for heuristics, maybe integer linear programming?  (You can modify the reduction above to show that deciding whether there is solution of cost zero is NP-hard, so, unless P=NP, there is no poly-time algorithm with multiplicative-approximation guarantee.)  

---

## 0 answers

