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

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

Parameters

n: number of vertices

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