# Clique Problem

Saw this from https://avisingh599.github.io/vision/visual-odometry-full/

A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent.

A $k$-clique in a graph is a sub-graph where the distance between any two vertices is no greater than $k$.

From CS341:

Maximum Clique (Clique)

$S⊆V$ is a clique if, ${u,v}∈E$ for all $u,v∈S$.

Input: $G=(V,E)$ and an integer $k$ Output: (the answer to the question) is there a clique in $G$ with at least $k$ vertices?

Maximum Independent Set (IS)

$S⊆V$ is an independent set if, ${u,v}∈/E$ for all $u,v∈S$.

Input: $G=(V,E)$ and an integer $k$ Output: (the answer to the question) is there an independent set in $G$ with at least $k$ vertices?

Minimum Vertex Cover (VC)

$S⊆V$ is a vertex cover if, ${u,v}∩S=∅$ for all ${u,v}∈E$.

Input: $G=(V,E)$ and an integer $k$ Output: (the answer to the question) is there a vertex cover in $G$ with at most $k$ vertices?