The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### Having trouble in understanding the definition of a clique

Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct vertices in $C$ are connected by a ...
• 874

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

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "...
• 7,565
Accepted

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

When $c > \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$). When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the ...
• 278k
Accepted

### Why is Clique NP-complete while k-Clique is in P for all k?

The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time ...
• 278k
Accepted

### Is this clique algorithm in polynomial time correct or might it have another time complexity?

Your analysis of the time complexity is wrong. Specifically this statement: In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at. In fact ...
• 29.6k
Accepted

### Prove that "max independent set is larger than max clique" is NP-Hard

To prove the NP-hardness of the problem B under the polynomial-time many-one reduction, we can reduce from the maximum independent set problem. We are given a graph of size $n$ and an integer $k$, to ...
• 2,872
Accepted

### Prove "almost clique" is NP complete

You can reduce to this from $CLIQUE$. Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n +2}\}$ and connecting them with all of $G$'s vertices but ...
• 742
Accepted

### Number of cliques in a graph

I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique). For the number of maximal cliques, ...
• 16.7k
Accepted

### CLIQUE $\leq_p$ SAT

There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $G = (V,E)$, and interested in a $k$-clique. We will have $k|V|$ variables $x_{iv}$, ...
• 278k
Accepted

### Reduction from Clique-6 to Clique-3

Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a ...
• 278k

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

The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, ...
• 278k
Accepted

### If the Clique-k Problem is in P, why not Clique as well?

It's a matter of logical quantifiers. Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ ...
• 14.6k
Accepted

### Why doesn't greedy work for Clique?

Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex ...
• 278k

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

I believe this is FPT. FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the ...
Accepted

### Determining the minimum number of edges to add to a graph to obtain a clique of size $k$

The problem is called Defective $k$-Clique [Yu et al., Bioinformatics (2006)]. The optimization problem is: Problem: Defective $k$-Clique Input: A graph $G$ and $k \in \mathbb{N}$. Output: The ...
• 16.7k

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

The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n > 1$) is equal to $n-1$. It is easier to understand using the fact that minimum vertex covers correspond to the ...
• 9,857
Accepted

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

Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all ...
• 278k
Accepted

• 278k