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.

$\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.

$\endgroup$
  • 3
    $\begingroup$ You don't even really need a clever algorithm for it (or at least to see it's in P). Kuratowksi's theorem immediately shows that the graph can't have a clique of size bigger than $4$, so we can just try everything and even this stupid approach is still polynomial. If you want to actually implement an algorithm of course, you'd want to be much more sensible. $\endgroup$ – Luke Mathieson Oct 29 '12 at 22:16
  • $\begingroup$ Yes, that is true. $\endgroup$ – Juho Oct 29 '12 at 22:35

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.