Is it known whether the following problem is in P or is NP-complete?

Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.

  • $\begingroup$ Here is an easy polynomial time algorithm: Given $G(V, E)$, Take the complement of $E$. Then $G$ has complete $n/2×n/2$ bipartite graph iff the complement graph has two disjoint cliques of size $n/2$. This can be checked efficiently. $\endgroup$ – Mohammad Al-Turkistany Dec 18 '18 at 18:30
  • 1
    $\begingroup$ @Mohammad No, it is iff the complement graph is included in two disjoint cliques of size $n/2$. It can still be checked efficiently, but this is somewhat nontrivial to prove. It amounts to the subset-sum problem stated in Peter Taylor's answer. $\endgroup$ – Emil Jeřábek Dec 18 '18 at 21:28
  • $\begingroup$ @EmilJeřábek Thank you for your feedback. $\endgroup$ – Mohammad Al-Turkistany Dec 18 '18 at 21:52

If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which is not an edge. Then you just need to solve the partition (subset-sum) problem to group some disjoint sets into a set of size $\frac{|V|}{2}$. The union-find phase can be done in $O(V^2 \alpha(V))$ and the pseudo-polynomial algorithm for subset sum takes $O(V^2)$ so this is in P. (Thank you to those who corrected an earlier error).

In the other direction, an oracle for balanced bipartite subgraph would give a pseudo-polynomial algorithm for the partition problem.

FWIW the generalisation which takes a parameter $K$ and asks whether there's a subgraph of $G$ which is a complete $K \times K$ bipartite graph is NP-complete by reduction from CLIQUE. Hat tip to Mohammad Al-Turkistany who cited a reference which proves this even when $G$ is known a priori to be bipartite: David S. Johnson, The NP-completeness column: An ongoing guide. Journal of Algorithms, 8(3):438–448, 1987.

  • 1
    $\begingroup$ Thank you very much for your answer! If I understand correctly, your argument actually shows that my balanced complete bipartite graph problem is in P, since for this problem the complexity is measured with respect to the number of vertices in the input graph, and the pseudo-polynomial time algorithm for subset-sum runs in poly(n) time for such inputs. $\endgroup$ – Bill Dec 17 '18 at 17:41
  • $\begingroup$ Why do you say "therefore it's NP-complete but has a pseudo-polynomial time solution"? That's true of subset sum when the numbers are expressed in binary (may have large magnitude) but here they're all small. So this looks like a polynomial time algorithm, not just a pseudo-polynomial one. $\endgroup$ – David Eppstein Dec 18 '18 at 0:41

Your Answer

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

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