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?