3
$\begingroup$

We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?

$\endgroup$
6
$\begingroup$

In a bipartite graph there can be no clique of size three. Not much of a problem that is left I guess?

(edit) Sorry, that was too fast, I realize thanks to comment by Nicholas below. To make up for it I googled a reference.

The maximum edge biclique problem is NP-complete by Ren*e Peeters. Discrete Applied Mathematics 131 (2003) 651 – 654

(ps) So I understand that my answer relates to a question that changes the types of graphs we are looking for, kind of bipartite cliques, whereas the other answer restricts the set of graphs we are looking in to planar. In planar graphs cliques can have size at most four, thanks to Kuratowski.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I would imagine the OP wants to restrict to finding subgraphs of the form $K_{n,n}$ for the bipartite case. $\endgroup$ – Nicholas Mancuso Oct 29 '12 at 21:39
  • $\begingroup$ Note that the referenced paper investigates the problem that asks for at least $k$ edges. They state that you look for bicliques with at least $k$ nodes, the problem is in P. $\endgroup$ – Raphael Feb 17 '14 at 13:18
4
$\begingroup$

For planar graphs, the problem is in $\mathsf{P}$. This follows already from Kuratowski's theorem: a clique is at most of size 4. The naive algorithm can just check every combination.

For a more clever algorithm, see Norishige Chiba and Takao Nishizeki, Arboricity and Subgraph Listing Algorithms, SIAM Journal on Computing 14(1): 210–223, 1985.

| cite | improve this answer | |
$\endgroup$

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.