<p>This problem is in P, it can be reduced to the <a href="https://en.wikipedia.org/wiki/Minimum_cut">Minimum cut</a> problem.</p>

<p>The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$. </p>

<p>The cost of the cut from source to sink in this graph with set of vertices $S$ along with source in one side of the cut exactly corresponds to your function $C$</p>

CC BY-SA 3.0
2017-01-31T16:12:30.343Z
It is not clear what you mean by "Also add edges from i to j of cost t(i,j) from i to j." Can you expand a bit please?
holf
CC BY-SA 3.0
2017-01-31T16:31:46.327Z
Thanks for the edit. One problem: how do you prevent the source and the sink to be taken in the same component? For example, you have a graph which is reduced to an edge $e = (x,y)$ with : $t(e) = 0$, $s(x) = w(x) = 1$ and $s(y) = w(y) = 0$. The optimum here is $1$ as either we take $x$ or not, we have to pay $1$. Now, with your transformation, we can take the source, the sink and $x$ from one side and $y$ on the other. All edges crossing have weight $0$ thus the optimum here is $0$.
holf
CC BY-SA 3.0
2017-01-31T16:34:56.467Z
There is a version of minimum cut called minimum s-t cut in which explicitly specify a pair of vertices s and t, we can calculate the smallest cut such that s and t are on opposite sides. It is equivalent to finding maximum flow from s to t.
saisandeep
CC BY-SA 3.0
2017-01-31T21:14:08.697Z
Wow, thanks, indeed it seems that the problem is in P... How about if the $G$ was a DAG and instead of the $C$ sum I would like to minimize the longest path (still keeping two weight functions, weights on nodes and edges)? How does that change the problem?
marszall87
CC BY-SA 3.0
2017-01-31T22:42:25.160Z
@marszall87, that sounds like a separate question/problem.  In the Stack Exchange model, each question belongs its own question; comments aren't intended for posing new questions.   I suggest you spend some time thinking about your new problem, then if you are still stuck, post a new question (and tell us about what approaches you considered and why you rejected them, and what research you did).
D.W.
CC BY-SA 3.0
2017-01-31T15:39:36.407Z
2017-01-31T16:28:01.680Z
2017-01-31T16:28:01.680Z
saisandeep
<p>I'm trying to prove that the following optimization problem is NP-hard:</p>

<p><em>Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)$, find a subset of vertices $S \in V$ that minimizes the function $C$:</em></p>

<p>$$C = \sum_{v \notin S}{w(v)} + \sum_{v \in S}{s(v)} + \sum_{(u,v) \in E:u \in S, v \notin S}{t(u,v)} $$</p>

<p>$$w(v) \geq 0, s(v) \geq 0, t(u, v) \geq 0$$</p>

<p>In other words, I'm trying to bipartition the graph and minimize the sum of vertex weights and edge weights across the cut, but the vertex weights are different depending on which "side" of the partition they are.</p>

<p>I've tried to reduce the max-cut problem to this by somehow minimizing the complement graph, also tried the sparsest cut, but the second weight function always seems to be problematic. Obviously, assuming that $s(v) = 0$ or $s(v) = w(v)$ makes the problem trivial, so there must be some solution that I'm missing. Or maybe the problem isn't NP-hard at all?</p>

<p>Any help is appreciated :)</p>

<p><em>Edit: restrict to non-negative weights</em></p>

CC BY-SA 3.0
2017-01-31T05:22:15.353Z
Is the graph undirected?
Mikhail Rudoy
CC BY-SA 3.0
2017-01-31T09:37:23.633Z
May be related to weighted MIN-2-XOR-SAT. I do not remember any direct reference for the complexity of this problem and cannot look for it now but maybe you can. Your pb is equivalent to the following CSP: variables are $V$ and for each edge $e=(x,y)$, you have a constraint $x \oplus y = 1$ with weight $w_e=t(x,y)$. Now you have two weights for each variable $x$: $w_{x,0} = w(x)$ and $w_{x,1}=s(x)$. An assignment of the variables $\tau : V \rightarrow \{0,1\}$ have weight: $\sum_{x \in V} w_{x,\tau(x)} + \sum_{e. \tau \models e} w_e$. The goal is to minimize this weight.
holf
CC BY-SA 3.0
2017-01-31T21:15:20.810Z
@MikhailRudoy The graph in my particular application is directed but I think that it doesn't really matter in this problem.
marszall87
<graph-theory><np-hardness><optimization><proofs><partition-problem>
Proof that the graph optimization problem is NP-hard
marszall87
# Proof that the graph optimization problem is NP-hard

(Asked by: username_0 on 2017-01-30)

I'm trying to prove that the following optimization problem is NP-hard:

*Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)$, find a subset of vertices $S \in V$ that minimizes the function $C$:*

$$C = \sum\_{v \notin S}{w(v)} + \sum\_{v \in S}{s(v)} + \sum\_{(u,v) \in E:u \in S, v \notin S}{t(u,v)} $$

$$w(v) \geq 0, s(v) \geq 0, t(u, v) \geq 0$$

In other words, I'm trying to bipartition the graph and minimize the sum of vertex weights and edge weights across the cut, but the vertex weights are different depending on which "side" of the partition they are.

I've tried to reduce the max-cut problem to this by somehow minimizing the complement graph, also tried the sparsest cut, but the second weight function always seems to be problematic. Obviously, assuming that $s(v) = 0$ or $s(v) = w(v)$ makes the problem trivial, so there must be some solution that I'm missing. Or maybe the problem isn't NP-hard at all?

Any help is appreciated :)

*Edit: restrict to non-negative weights*

**Tags:** graph-theory, np-hardness, optimization, proofs, partition-problem

> **Comments:**
> **username_1**: Is the graph undirected?  
> **username_2**: May be related to weighted MIN-2-XOR-SAT. I do not remember any direct reference for the complexity of this problem and cannot look for it now but maybe you can. Your pb is equivalent to the following CSP: variables are $V$ and for each edge $e=(x,y)$, you have a constraint $x \oplus y = 1$ with weight $w_e=t(x,y)$. Now you have two weights for each variable $x$: $w_{x,0} = w(x)$ and $w_{x,1}=s(x)$. An assignment of the variables $\tau : V \rightarrow \{0,1\}$ have weight: $\sum_{x \in V} w_{x,\tau(x)} + \sum_{e. \tau \models e} w_e$. The goal is to minimize this weight.  
> **username_0**: @MikhailRudoy The graph in my particular application is directed but I think that it doesn't really matter in this problem.  

---

## 1 answers

### Answer by username_3 on 2017-01-31. Score: 9 | Accepted answer

This problem is in P, it can be reduced to the [Minimum cut](https://en.wikipedia.org/wiki/Minimum_cut) problem.

The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$.

The cost of the cut from source to sink in this graph with set of vertices $S$ along with source in one side of the cut exactly corresponds to your function $C$

> **Comments:**
> **username_2**: It is not clear what you mean by "Also add edges from i to j of cost t(i,j) from i to j." Can you expand a bit please?  
> **username_2**: Thanks for the edit. One problem: how do you prevent the source and the sink to be taken in the same component? For example, you have a graph which is reduced to an edge $e = (x,y)$ with : $t(e) = 0$, $s(x) = w(x) = 1$ and $s(y) = w(y) = 0$. The optimum here is $1$ as either we take $x$ or not, we have to pay $1$. Now, with your transformation, we can take the source, the sink and $x$ from one side and $y$ on the other. All edges crossing have weight $0$ thus the optimum here is $0$.  
> **username_3**: There is a version of minimum cut called minimum s-t cut in which explicitly specify a pair of vertices s and t, we can calculate the smallest cut such that s and t are on opposite sides. It is equivalent to finding maximum flow from s to t.  
> **username_0**: Wow, thanks, indeed it seems that the problem is in P... How about if the $G$ was a DAG and instead of the $C$ sum I would like to minimize the longest path (still keeping two weight functions, weights on nodes and edges)? How does that change the problem?  
> **username_4**: @username_0, that sounds like a separate question/problem.  In the Stack Exchange model, each question belongs its own question; comments aren't intended for posing new questions.   I suggest you spend some time thinking about your new problem, then if you are still stuck, post a new question (and tell us about what approaches you considered and why you rejected them, and what research you did).  

---

