0
$\begingroup$

Given a planner graph which it's vertexes have weights and an integer, W, this graph should be partitioned into two subgraphs which sum of weights for each subgraph becomes at least W.

I wanted to show this is np hard by reduction and I have used Max cut to show that (in max cut we have a graph with weights for edges and need to partition it's vertexes into two subgraph which the sum of weights of edges between these two subgraph, becomes at least K)

I'm not sure about how to change weights of edges in max cut to weights of vertexes in the new problem, I've considered for each vertex weight the max weight of edges which it is an endpoint for, and W=K, is this correct?? if not how to consider the weights for vertexes and W?? or another problem should be used?? I appreciate if anybody guides me by the reduction.

ps: please consider that we can not use partition since it says at least W not W, or subset sum.

$\endgroup$
3
$\begingroup$

I think you can in fact do this by showing a reduction from the Partition problem, as stated by Chapichap. Recall the direction of reduction that is needed to show a problem is NP-Hard. In general, it is okay if the problem you have is harder than the problem you are using to show hardness (in this case, the partition problem). This is because the reduction would from the partition problem to the given problem. For the partition problem, if we are given a set of numbers $S$, and we want to find a partition $S_1,S_2=S\setminus S_1$, we need to show how to construct a graph $G$ and a number $W$ such that the vertices of $G$ can be partitioned as described (where the sum of weights of the vertices is at least $W$) if and only if the set $S$ can be partitioned.

Consider the following reduction: Let $G = (V,E)$ be a graph where $V=S$. That is, for each number in $S$, create a vertex in $G$. The edge set seems irrelevant here, so we can let $E=\varnothing$. The weight of each vertex is equivalent to the number in $S$ to which it corresponds. Finally, let $\lceil W=(\sum_{x\in S} x)/2\rceil$. That is, $W$ is the sum of the weights of all the elements of $S$, divided by two.

Asking for a partition in $G$ such that each partition has total weight at least $W$ means asking for each partition to contain half of the total weight of the graph. To be thorough, consider the case where $\sum_{x\in S}$ is even. Then $W$ is exactly half of the total weight of all vertices in the graph, and so for each partition to have a total weight of at least $W$, each partition must have equal weight. Thus such a partition of the vertices is equivalent to an equal-sum partition of the elements of the original set. Now, consider the case where $\sum_{x\in S}$ is odd. In such a case, $S$ has no partition such that the sum of the partitions are equal. However, the way we constructed $W$ ensures that $2W = (\sum_{x\in S})+1$ and so it is impossible to partition the graph so that each partition has total weight at least $W$ (the existence of such a partition would imply that the total weight of the graph is strictly greater than $\sum_{x\in S}$, which is impossible).

Hopefully you can see from the above that $G$ has a partition into two subgraphs such that the sum of the weights of vertices in each partition is at least $W$ if and only if the original set $S$ had a partition of its elements into two subsets such that the sums of elements in each subset are equal.

$\endgroup$
  • $\begingroup$ Thanks for your complete explanation, I think I can use restriction technique to say it is np complete and use partition problem. $\endgroup$ – NedaHn Dec 7 '17 at 19:52
0
$\begingroup$

What do edges represent in your initial graph?. I don't see why you need a graph structure to represent your problem. It may just as well be a set of numbers, which you want to partition into two subsets of weights at least $W$. Perhaps variations of the subset sum problem if some vertices have negative weights https://en.m.wikipedia.org/wiki/Subset_sum_problem Or the partition problem otherwise https://en.m.wikipedia.org/wiki/Partition_problem would be more useful for your reduction.

$\endgroup$
  • $\begingroup$ thank u but consider this problem outputs two sets of vertexes which their sum is at least W and not exactly W, how u say partition has solution by this output or about subset sum even, here there is at least, yes I have reached to partition but it says exactly not at least if it was exactly W, it would be same as partition not even harder $\endgroup$ – NedaHn Nov 6 '17 at 17:33

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.