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

63 views

### Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
175 views

### Prove that “Finishing the degree in three years” problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
102 views

### Maximal cliques in a multipartite graph - efficient?

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class. Now I am looking for the optimal subset such that each of the N classes is represented exactly ...
133 views

317 views

### Understanding CLIQUE structure

I am working on the following problem: Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is ...
76 views

### Finding maximum weighted n disjoint cliques

Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations? Given a ...
407 views

114 views

187 views

### What is the relationship between minimum sized vertex covers and complete graphs?

What is the relationship between the sizes of minimum sized vertex covers and complete graphs?
227 views

In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, in polynomial time: Given any $k_0, k_1, k_2,..., k_{... 2answers 844 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$. ... 1answer 72 views ### Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not Recall the notion of NPO problem. An NPO problem is simple if the following is true:$\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$In words, given any positive integer$k$, the ... 1answer 247 views ### Reduction from Clique to something else Given$G(V,E)$and$k$. Is there a clique with size$k$? Given set$X = \{x_1,x_2,\dots,x_n \}$, and collection$A = \{A_1,A_2,...,A_n\}$of sub-sets of$X$and$k$. Are there are$k$different ... 1answer 701 views ### Number of cliques in a graph I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that? 1answer 757 views ### Reduction from Clique-6 to Clique-3 Recall that$G$has a clique of size$k$if it has a complete sub graph consisting of$k$vertices. Let us define the problem$Clique-k$as follows:$$\{ \langle G \rangle \mid G \text{ is an ... 2answers 1k views ### Prove “almost clique” is NP complete Given$G=(V,E)$, undirected graph, a group of vertices$S$is called almost clique if by adding a single edge,$S$becomes a clique. Consider the language:$L=\{\langle G,t\rangle \mid \text{the ...
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$? ...