# Questions tagged [clique]

A clique is a subset of the vertices of a graph such that every pair of vertices in the subset is connected by an edge.

123 questions
Filter by
Sorted by
Tagged with
294 views

277 views

### Fast $k$-clique checking algorithm?

I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$? Obviously, answering this question is a NP-Complete problem. I am no ...
• 121
1 vote
53 views

### Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?

Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k? Is it correct to say that it doesn't exist because clique is ...
25 views

• 127
68 views

### Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
• 128
99 views

### On Tarjan's paper "Finding a Maximum Clique"

In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here. In the second page ...
• 153
170 views

### What is the complexity of k-clique problem with a predetermined vertex in the solution?

Clique (from WikiPedia): Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. K-Clique ...
• 87
1 vote
39 views

• 364