Consider the following problem:

Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the following:

number of black edges with both endpoints in $W$ + number of white edges with at most one endpoint in $W$

What is the complexity of this problem? Is there a polynomial time algorithm (exact or approximate) for the problem? Could this problem be reduced to any classic Thoeretical CS problem, like the Max-Cut?

  • 1
    $\begingroup$ If I understand the problem correctly, it is equivalent to finding in a bipartite graph $G=(A \cup B, E)$ (induced by the white edges only) a subset W with $|W \cap A|=x$ and $|W \cap B|=y(=k-x)$ that maximizes the quantity $q=xy-2|E(W)|$. Therefore asking for a solution with value $q \geqslant \frac{k^2}{4}$ boils down to finding a (k/2,k/2)-independent set which is NP-hard, and even W[1]-hard parameterized by $k$. $\endgroup$ – Edouard Bonnet Feb 24 '16 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.