0
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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$.
Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – pcpthm
    Dec 25, 2022 at 8:23
  • $\begingroup$ 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. $\endgroup$
    – pcpthm
    Dec 25, 2022 at 8:30
  • $\begingroup$ @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). $\endgroup$
    – Nathaniel
    Dec 25, 2022 at 10:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – pcpthm
    Dec 25, 2022 at 12:23
  • $\begingroup$ Ah that's right, there was an ambiguity in my answer, sorry about that. $\endgroup$
    – Nathaniel
    Dec 25, 2022 at 12:40

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.