Polynomial Time Reduction

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\subseteq V$ is a clique if, $\{u,v\}\in E$ for all $u,v\in 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\subseteq V$ is an independent set if, $\{u,v\}\notin E$ for all $u,v\in 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\subseteq V$ is a vertex cover if, $\{u,v\}\cap S\ne \varnothing$ for all $\{u,v\}\in 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?