<p>If the vertex pair <span class="math-container">$(u, v)$</span> is not in <span class="math-container">$E$</span> 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 <span class="math-container">$\frac{|V|}{2}$</span>. The union-find phase can be done in <span class="math-container">$O(V^2 \alpha(V))$</span> and the pseudo-polynomial algorithm for subset sum takes <span class="math-container">$O(V^2)$</span> so this is in P. (Thank you to those who corrected an earlier error).</p>

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

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

CC BY-SA 4.0
2018-12-17T17:41:40.057Z
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.
Lior Gishboliner
CC BY-SA 4.0
2018-12-18T00:41:05.990Z
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.
David Eppstein
CC BY-SA 4.0
2018-12-17T11:08:20.067Z
2018-12-18T22:36:18.723Z
2018-12-18T22:36:18.723Z
Peter Taylor
<p>Is it known whether the following problem is in P or is NP-complete?</p>

<p>Problem: given an input graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices, decide whether <span class="math-container">$G$</span> contains a complete <span class="math-container">$n/2 \times n/2$</span> bipartite graph. </p>

CC BY-SA 4.0
2018-12-18T18:30:32.403Z
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
CC BY-SA 4.0
2018-12-18T21:28:20.640Z
@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
CC BY-SA 4.0
2018-12-18T21:52:42.750Z
@EmilJeřábek Thank you for your feedback.
Mohammad Al-Turkistany
<cc.complexity-theory>
Deciding whether a graph contains a complete balanced bipartite graph
Lior Gishboliner
# Deciding whether a graph contains a complete balanced bipartite graph

(Asked by: username_0 on 2018-12-17)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: @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 username_3's answer.  
> **username_1**: @EmilJeřábek Thank you for your feedback.  

---

## 1 answers

### Answer by username_3 on 2018-12-17. Score: 5 | Accepted answer

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 [username_1](//cstheory.stackexchange.com/users/495) 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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  

---

