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

70 questions
Filter by
Sorted by
Tagged with
26 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 ...
33 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 (...
23 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 ...
51 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 ...
89 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 ...
40 views

### Reducing CLIQUE to Super Connector problem

I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem. Regular CLIQUE problem: Input: An undirected graph $G$ and a positive integer $K$. ...
49 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 ...
158 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\}$, ...
51 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 ...
111 views

86 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 ...
63 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 ...
202 views

103 views

46 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?
155 views

121 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 ...
98 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 ...
### 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 }...
### 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 ...