2
$\begingroup$

Let $G = (V, E, W)$ be a weighted graph with positive and negative weights. I would like to find the set of vertices $V^\prime$ such that the sum of the weights of the edges that they share is the maximum you can get from $G$. I suspect that this is an NP-complete problem, so my question is whether this can be reduced to a known NP-complete problem. Since $V^\prime$ does not necessarily have to be the minimum subset that satisfies the constraint, I think I can't use the solutions for the vertex/set cover problems, so any ideas would be welcome.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

An easier problem to use would be max clique. We do the transformation as follows. We take the graph that we wish to find the max clique in and give all edges in it weight 1, and for all non edges we give weight (-)infinity (or if you dont like infinity an arbitrarily large number based on the number of edges total, negative enough so that if one is picked the total will always be negative). This problems solution will give us a clique since the negative infinity weight will prevent selecting anything that does not have edges between them for the solution. This clique is also the largest, as a larger clique would have a larger edge sum and we assume this algorithm returned the largest edge sum. This is therefor at least as hard as solving max clique, which is NP complete.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry, but I don't see it fully. If I give all edges in the graph weight 1, how can I know the previous (positive or negative) weights they had? I mean, I have to get the subgraph with the largest weight sum, so I think I'm missing something. $\endgroup$
    – Cromack
    Commented Jan 18, 2017 at 8:03
  • $\begingroup$ @Cromack To do a reduction and, prove np-completeness, you need to show that if you have some algorithm that solves your problem, then you can take another specific problem, transform the problem in polynomial time, then use your algorithm to solve the other problem. This shows that solving your problem is a least as hard as solving the other one, since your problem can be used to solve the other one. There are no weights in max clique so no information to preserve, so we create a set of weights (and in this case extra edges with really bad weights). $\endgroup$
    – lPlant
    Commented Jan 18, 2017 at 14:51

Your Answer

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

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