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

79 questions
Filter by
Sorted by
Tagged with
843 views

### reducing $CLIQUE$ from decision to search problem

consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ G is a graph containing a clique of size at least k } \right\}$$ Suppose there's a polynomial time algorithm for $CLIQUE$. ...
193 views

### Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph [closed]

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
47 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 ...
28 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 ...
227 views

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

### Solving distance-d independent set in a simple way

I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). ...
65 views

### Is $\frac{n}{3}$-CLIQUE NP-complete?

Consider the problem $\frac{n}{3}$-CLIQUE: determining whether a graph contains a clique with at least $n/3$ vertices. I want to prove it is NP-complete using a polynomial transformation from CLIQUE. ...
201 views

### Max clique in interval graph

According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. ...
184 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 ...
58 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 ...
34 views

### Question about the lower bound for $k \times k$-clique (under ETH) shown in “Slightly Superexponential Parameterized Problems”

I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it: First question: The paper gives a proof of the following statement Theorem ...
115 views

### CLIQUE $\leq_p$ SAT

i'm trying to reduce CLIQUE to SAT: Given: Graph G=(Vertices V, Edges E) and $k \in \mathbb{N}$ Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (...
31 views

### Algorithm to compute partitions of a graph in N cliques

does anyone know of an efficient algorithm to compute the partition of a graph in N cliques? Notice that N is the number of the cliques and not the size of them. I have heard of the 2 cliques ...
246 views

### Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
485 views

### Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
1k views

### What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia): ...
55 views

596 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 ...
68 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 ...
241 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 ...
36 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-...
1k 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 ...
65 views

104 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[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
161 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-...
47 views

479 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 ...
242 views

### Is $k$-CLIQUE W[1]-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[1]-hard with respect to parameter $k$. Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, ...
95 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 ...
437 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 ...
75 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 ...
69 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 ...
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$ ...