Proving problem NP-completeness [duplicate]

Question

I am studying computational complexity and i am trying to solve this problem. We are given a (non-bipartite) complete graph:

G = (V, W, E)

where the vertices can be divided in two classes V and W and the edges between any two vertices are weighted either 1 or 0.
w(x, y) = {0, 1} ∀ x, y ∊ V ∪ W

We need to:

• calculate a subset I ⊆ V ∪ W that maximizes the sum of the weights of the edges that link the elements of I, divided by the I cardinality.
  max(1 / |I| ∑ w(x, y) ∀ x, y ∊ I)

• The calculated subset I must have the same number of vertices of V and W.
  |I ∩ V| = |I ∩ W|

I would need to prove that this problem is NP-complete.

I have thought about reducing the problem to a vertex cover, removing the incident vertices to a 0 edge, but that would compromise the optimal solution. And even considered this, i have found many difficulties trying to figure out a optimal certifier for the algorithm, which would prove the problem to be at least NP. Any clues on a strategy to follow?

Answer 1

First, when doing complexity analysis, we usually think in terms of decision problems, i.e. the answer must be yes or no, and here you have an optimisation problem. This is why you are struggling to find a certificate here. If you reformulate your problem as a decision problem with an additional parameter $k$, and the question become "Is there a subset I such that the sum (...) Is greater than k ?", You will easily find the certificate : the list of the vertices in I, you can polynomially check that there are as many elements of V and W, and that the sum has the desired property.

Second, it seems like your are trying to reduce your problem to VERTEX-COVER. However, we already know that's possible because VC is NP-complete. To show that your problem is NP-Hard, you have to reduce a NP hard problem to it.

Finally, the reduction : maybe something from VERTEX-COVER will work : take an instance with a graph G=(V,E), make it complete by adding edges and put their weight to 0 (then your problem will not "try" to get them). If you find a clever way to divide V into V and W, the reduction might work. However, it seems to me that VERTEX-COVER does not have a condition on sets and partitions, and you might have more luck with Subset-sum or 2-partition.

Edit : after a bit of thinking, If you make 2 copies of G (one becomes your V and the other W), and complete it with 0-weighted edges, you juste have to find the correct value for k... I think that's not too far.

I hope that helps.