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

73 questions
Filter by
Sorted by
Tagged with
69 views

### Clique-problem for planar graph

I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion This follows already from Kuratowski's theorem: a clique is at ...
35 views

### Minimum unweighted anticlique (independent set) cover / partition

Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
173 views

7k 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,...
436 views

### Generalization of Subgraph Isomorphism

I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link ...
58 views

### Clique number of a graph given its order and average degree

Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$. Find the ...
122 views

### Why is EXACT-CLIQUE not in co-NP?

In my lecture I saw the problem of $\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in$G$is of order$k$}\}$ I understand this problem is obviously not in NP as we would need ...
34 views

### Best-known Boolean Circuits for Clique? [closed]

Not having received a satisfactory response to this question in math.SE, I am asking it here: In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
561 views

### Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
56 views

73 views

### Minimum number of vertices whose removal makes the graph an independent set

It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
123 views

### An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
46 views

375 views

### Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random ...
184 views

### Is $k$-CLIQUE W-hard for parameter $n - k$?

It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W-hard with respect to parameter $k$. Is it also known to W-hard (or perhaps FPT) in parameter $n - k$, ...
79 views

### Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
272 views

### Does the k-clique problem became easier on sparse graphs?

Some definitions, just to not create confusion: A sparse graph is a graph that contains a number of edges less or equal than the number of vertices. In $k$-clique problem we are given a graph and an ...
61 views

### Listing all maximal cliques with mean edge weight at least k in a weighted complete graph

Given a weighted undirected complete graph G = (V,E). I am interested in finding all maximal cliques that have mean edge weight (mean of weights of all edges in the clique) at least k. Most of the ...
63 views

### Hueristic Algorithm to find the maximum clique

Let the algorithm be defined as follows: Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every ...
152 views

### What is the exact algorithm to find maximum clique of a given unit disk graph?

A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ ...
544 views

141 views

### Colored cliques complexity

Given: graph with colored edges; list of $\alpha$ colors; list of $\epsilon$ colors; clique size $k$. Problem: Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$? ...
273 views

### Reduce Clique to Set Cover

Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to ...
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 ...
812 views

### Expected number of independent sets of size $k$ in random graph $G(n,p)$

I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is ...
### 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 ...