# Searching for the largest bipartite subgraph

OpenAI's Chat-GPT told me:

There is no known exact algorithm for finding the largest bipartite subgraph in a graph in polynomial time. This problem is generally believed to be NP-hard, which means that there is no known polynomial-time algorithm for solving it.

Is this correct?

The problem of finding a largest bipartite subgraph of a graph is equivalent to the maximum cut problem. Karp proved NP-completeness of this problem.

That is, this problem is proven NP-hard, not "believed to be NP-hard." I suggest you use ChatGPT as hints for more research, and not take responses as is. They are often confident-sounding but very wrong.

Garey and Johnson (Computers and intractability) states that the subgraph isomorphism problem is $$\mathsf{NP}$$-complete, and contains several special cases, like Clique, Complete bipartite, Hamiltonian cycle or Hamiltonian path.

If you could find the largest bipartite subgraph, you could find the largest complete bipartite subgraph, so yes, that's true.

To find the largest complete bipartite subgraph in a bipartite graph $$G = (X\sqcup Y, E)$$:

• construct $$G' =(X\sqcup Y, E')$$ where $$E' = \{\{x, y\}\mid x\in X, y\in Y \text{ and }\{x, y\}\notin E\}$$;
• find a maximum matching in $$G'$$;
• find a minimum vertex cover in $$G'$$ using König's theorem;
• the complement of that vertex cover is a maximum complete bipartite subgraph in $$G$$.
• This is the opposite direction. Finding a complete bipartite subgraph is a special case of the more-general subgraph isomorphism, that means "(finding a largest complete bipartite subgraph is NP-hard) then (subgraph isomorphism is NP-hard)", not the other way. Dec 25, 2022 at 8:23
• Also, I don't follow the second paragraph. A largest bipartite subgraph is not a largest complete bipartite subgraph in general. The largest bipartite subgraph of $C_6$ is itself but it is not a complete bipartite graph. Dec 25, 2022 at 8:30
• @pcpthm I was just quoting the book that states that those special cases are also $\mathsf{NP}$-complete. Also, the largest complete bipartite subgraph is always a subgraph of the largest bipartite subgraph. Given a bipartite graph, you can find its largest complete bipartite subgraph in polynomial time (using a matching). Dec 25, 2022 at 10:45
• I guess we are confused by the definition of "subgraph". I assumed this definition en.wikipedia.org/wiki/Glossary_of_graph_theory#subgraph but you seem to use en.wikipedia.org/wiki/Induced_subgraph definition. Dec 25, 2022 at 12:23
• Ah that's right, there was an ambiguity in my answer, sorry about that. Dec 25, 2022 at 12:40