4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Is the graph undirected? $\endgroup$
    – Mikhail Rudoy
    Jan 31, 2017 at 5:22
  • $\begingroup$ 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. $\endgroup$
    – holf
    Jan 31, 2017 at 9:37
  • $\begingroup$ @MikhailRudoy The graph in my particular application is directed but I think that it doesn't really matter in this problem. $\endgroup$
    – marszall87
    Jan 31, 2017 at 21:15

1 Answer 1

Reset to default
9
$\begingroup$

This problem is in P, it can be reduced to the 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$

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – holf
    Jan 31, 2017 at 16:12
  • $\begingroup$ 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$. $\endgroup$
    – holf
    Jan 31, 2017 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – saisandeep
    Jan 31, 2017 at 16:34
  • $\begingroup$ 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? $\endgroup$
    – marszall87
    Jan 31, 2017 at 21:14
  • $\begingroup$ @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). $\endgroup$
    – D.W.
    Jan 31, 2017 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.