# Deciding whether a graph contains a complete balanced bipartite graph

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.

• 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. – Mohammad Al-Turkistany Dec 18 '18 at 18:30
• @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. – Emil Jeřábek Dec 18 '18 at 21:28
• @EmilJeřábek Thank you for your feedback. – 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).
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.