patternMinor
Is the clique problem NP-complete also on bipartite or planar graphs?
Viewed 0 times
problemthegraphscliqueplanarbipartitealsocomplete
Problem
We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?
Solution
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.
(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.
Context
StackExchange Computer Science Q#6375, answer score: 6
Revisions (0)
No revisions yet.