<p><em>(not quite an answer, but too long for a comment)</em></p>

<p>Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize</p>

<p>\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]</p>

<p>Collecting terms, your goal is then to minimize</p>

<p>\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]</p>

<p>Setting $w&#39;_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)</p>

CC BY-SA 3.0
2012-03-20T05:42:48.957Z
2012-03-20T05:42:48.957Z
Suresh Venkat
<p>I think <a href="http://en.wikipedia.org/wiki/Cut_%28graph_theory%29#Sparsest_cut" rel="nofollow">Sparsest cut</a> or edge expansion, is good enough for you, because deals with both edges and nodes. The task is to find a cut, with $S\subset V$, $|S|\leq {|V|\over2}$ in one part such that:</p>

<p>$$\alpha(G) = \min \{ {E(S,S^c)\over |S|}\}$$</p>

<p>is minimized over all possible set of $S$.</p>

<p>You may look at <a href="http://www.sciencedirect.com/science/article/pii/0166218X9090133W" rel="nofollow">Sparsest cut and bottlenecks in graphs</a> by Matula,Shahrokhi for proof of NP-Hardness (proof is by using max cut).</p>

<p>Also P. Bonsmaa et al, shown that it's NP-Hard <a href="http://www.sciencedirect.com/science/article/pii/S1570866711001110" rel="nofollow">even in uniform case</a> (means all edges are of weight $1$).</p>

CC BY-SA 3.0
2012-03-19T09:16:56.590Z
2014-03-19T13:04:18.863Z
2014-03-19T13:04:18.863Z
Saeed
<p>I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?</p>

<p>Thank you very much</p>

<p>Here's an example problem: </p>

<p><strong>Input</strong>: directed graph with vertex weights $u_i$ and arcs weights $w_{ij}$.</p>

<p><strong>Output</strong>: a subset S of V to maximize the sum of the following things:</p>

<ol>
<li><p>$\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)</p></li>
<li><p>$\sum_{|{i,j} \cap S| = 1} w_{ij}u_j$: the sum over all cut edges of product of  arc weight and the weight of the destination vertex. </p></li>
</ol>

CC BY-SA 3.0
2012-03-19T05:20:05.237Z
Might help to give a specific problem: there are specific transformation that might apply, but it's hard to say without looking at an actual problem.
Suresh Venkat
CC BY-SA 3.0
2012-03-19T09:15:34.040Z
For many problems, there are easy reductions from graphs with weighted vertices and edges to graphs with just weighted vertices, or to graphs with just weighted edges.  For minimum (s,t)-cuts, this is a standard homework exercise.
Jeffε
CC BY-SA 3.0
2012-03-20T05:23:50.480Z
Is there any motivation for this (somewhat strange) cost function ? just wondering.
Suresh Venkat
<cc.complexity-theory><graph-theory>
Graph partition optimization with weights on edges and vertices
john
# Graph partition optimization with weights on edges and vertices

(Asked by: username_0 on 2012-03-19)

I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?

Thank you very much

Here's an example problem:

**Input**: directed graph with vertex weights $u\_i$ and arcs weights $w\_{ij}$.

**Output**: a subset S of V to maximize the sum of the following things:

1. $\sum\_{i, j \in S} w\_{ij} + \sum\_{i,j \in V - S} w\_{ij}$ (arc weights inside each side)
2. $\sum\_{|{i,j} \cap S| = 1} w\_{ij}u\_j$: the sum over all cut edges of product of arc weight and the weight of the destination vertex.

**Tags:** cc.complexity-theory, graph-theory
> **Comments:**
> **username_1**: Might help to give a specific problem: there are specific transformation that might apply, but it's hard to say without looking at an actual problem.  
> **username_2**: For many problems, there are easy reductions from graphs with weighted vertices and edges to graphs with just weighted vertices, or to graphs with just weighted edges.  For minimum (s,t)-cuts, this is a standard homework exercise.  
> **username_1**: Is there any motivation for this (somewhat strange) cost function ? just wondering.  

---

## 2 answers

### Answer by username_1 on 2012-03-20. Score: 4

*(not quite an answer, but too long for a comment)*

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum\_{(i,j) \in E} w\_{ij}$. Now your goal is to maximize

\[ W - \sum\_{|\{i,j\} \cap S| = 1} w\_{ij} + \sum\_{|\{i,j\} \cap S| = 1} w\_{ij}u\_j\]

Collecting terms, your goal is then to minimize

\[ \sum\_{|\{i,j\} \cap S| = 1} w\_{ij} (u\_j - 1)\]

Setting $w'\_{ij} = w\_{ij}(u\_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)


---

### Answer by username_3 on 2012-03-19. Score: 3

I think [Sparsest cut](http://en.wikipedia.org/wiki/Cut_%28graph_theory%29#Sparsest_cut) or edge expansion, is good enough for you, because deals with both edges and nodes. The task is to find a cut, with $S\subset V$, $|S|\leq {|V|\over2}$ in one part such that:

$$\alpha(G) = \min \{ {E(S,S^c)\over |S|}\}$$

is minimized over all possible set of $S$.

You may look at [Sparsest cut and bottlenecks in graphs](http://www.sciencedirect.com/science/article/pii/0166218X9090133W) by Matula,Shahrokhi for proof of NP-Hardness (proof is by using max cut).

Also P. Bonsmaa et al, shown that it's NP-Hard [even in uniform case](http://www.sciencedirect.com/science/article/pii/S1570866711001110) (means all edges are of weight $1$).


---

