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$
$\endgroup$
3
-
$\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-TurkistanyDec 18, 2018 at 18:30
-
2$\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řábekDec 18, 2018 at 21:28
-
$\begingroup$ @EmilJeřábek Thank you for your feedback. $\endgroup$– Mohammad Al-TurkistanyDec 18, 2018 at 21:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$ Dec 17, 2018 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$ Dec 18, 2018 at 0:41