Polynomial-Time Reducible

To show a problem is NP complete (not easy), you may show that a known NP complete problem reduces into the given problem

$Y{\le }_{p}X\wedge Y\text{ is NP complete}\to Y\text{ is NP complete}$

• Reads that if $Y$ is polynomial reducible/transformable to $X$ and $Y$ is NP complete, then Y must be NP complete
• Proof by contradiction:
  • Assume $Y$ isn’t NP complete with the above givens
  • Then we could solve $X$ in polynomial time by solving $Y$ and then reducing it to $X$, which contradicts the fact that $X$ is NP complete

$Y$	$X$	$X{\le }_{p}Y$ too?	Description
Maximum Clique Problem	Maximum Independent Set Problem	Yes	Invert all edges/non-edges in $O(n^2)$ time
Maximum Independent Set Problem	Vertex Cover Problem	Yes	Take set of nodes that aren’t in VC as MIS
Vertex Cover Problem	Efficient Recruiting Problem	Yes	From $G(V,E)$, let edges represent sports and nodes counselors