# Proving problem NP-completeness [duplicate]

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?

## marked as duplicate by Raphael♦Nov 26 '18 at 11:15

• 1) You need to phrase the problem as a decision problem. 2) " reducing the problem to a vertex cover" -- that's the wrong direction. – Raphael Nov 23 '18 at 21:03

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.