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

74 questions
Filter by
Sorted by
Tagged with
132 views

### Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
99 views

### NP-hardness of finding almost cliques

Here's a problem that came up when organizing a party: You need to place $n$ guests in tables of size 10. Each guest has a list of $m$ other guests they'd like to have in their table. Find a seating ...
442 views

### Reduce $\sqrt{n}$-CLIQUE to CLIQUE

Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem \{ \langle G, c \rangle \mid G \text{ has a clique of size }...
235 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 ...
377 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.). ...
2k 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 ...
261 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 ...
899 views

375 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 ...
325 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 ...
516 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 ...