# k-Clique (Clique Problems)

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

## 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}$
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}$