# 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.

77 questions
Filter by
Sorted by
Tagged with
9k views

### Having trouble in understanding the definition of a clique

My definition says A clique is a graph that has an edge connecting every pair of vertices but as I understand, an edge connects only two vertices. Like $A-B$. If we want to connect three vertices,...
866 views

264 views

### Parameterized vertex cover on $r$-regular graphs

I am trying to solve the following exercise from this book: Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is Fixed-parameter tractable (FTP) on $r$-regular graphs for every ...
408 views

### Why doesn't greedy work for Clique?

In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). ...
3k views

### Why is Clique NP-complete while k-Clique is in P for all k?

I just stumbled upon this question here Why is the clique problem NP-complete? and I am confused by the given answer. The question about about whether $k$-clique is NP-hard for a fixed $k$ and the ...
268 views

### Implementing Nesetril and Poljak's clique detection algorithm

I want to implement the clique detection algorithm by Nesetril and Poljak described in . However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to ...
1k views

437 views

### Can I find a clique with more than 2 nodes in a bipartite graph?

As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?
2k views

### Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
346 views

### NDTM for Graph Clique Problem in poly-time

I am having a doubt. This is my NDTM algorithm: GCP(G, k): generate a list with k distinct nodes from graph G generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise check if ...
3k views

### Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
628 views

### Finding vertices of a maximum clique in polynomial time [duplicate]

Say you were given a black box that solves a clique problem in constant time. You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a ...
### Expected number of maximal cliques in $G(n,p)$
The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...