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?

  • $\begingroup$ 1) You need to phrase the problem as a decision problem. 2) " reducing the problem to a vertex cover" -- that's the wrong direction. $\endgroup$ – 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.

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.

  • $\begingroup$ Welcome, and thanks for taking the time to answer! Note that we have compiled some reference questions that cover, in breadth and depth, some problems learners of CS frequently run into. You may want to check that list in order to avoid wasting time on writing the n+1-th answer re-hashing the same thing. $\endgroup$ – Raphael Nov 26 '18 at 11:19

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