# k-Clique (Clique Problems)

Jump to navigation
Jump to search

## Description

For a constant $k \geq 3$, the $k$-Clique problem is as follows: given a graph $G = (V, E)$ on $n$ vertices, does $G$ contain $k$ distinct vertices $a_1, \ldots, a_k$ so that for every $(i, j)$, $i \neq j$, $(a_i, a_j ) \in E$? Such a $k$ node graph is called a $k$-clique.

## Related Problems

Subproblem: Exact k-Clique, Min-Weight k-Clique, Max-Weight k-Clique

Related: Enumerating Maximal Cliques, arbitrary graph, Min-Weight k-Clique, Max-Weight k-Clique

## Parameters

$n$: number of vertices

$m$: number of edges

$k$: size of clique

## Table of Algorithms

Currently no algorithms in our database for the given problem.

## Reductions TO Problem

Problem | Implication | Year | Citation | Reduction |
---|---|---|---|---|

CFG Recognition | assume: k-Clique Hypothesis then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |

RNA Folding | assume: k-Clique Hypothesis then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |

CFG Recognition | assume: k-Clique Hypothesis then: there is no $O(N^{\{3}-\epsilon}) time combinatorial algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |

RNA Folding | assume: k-Clique Hypothesis then: there is no $O(N^{\{3}-\epsilon}) time combinatorial algorithm for target for any $\epsilon > {0}$ |
2017 | https://ieeexplore.ieee.org/abstract/document/8104058 | link |

## References/Citation

https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf