Reduction and NPC

Concepts

Clique - a subgraph in which there exists an edge between every pair of vertices
Independent set - a set of vertices in the graph in which none of two are adjacent
Vertex cover - a set of vertices in which every edge in the graph is incident to at least one vertex in the set

Polynomial time reducible

Consider problem $A$ and $B$

• There exists a function $f$ that runs in polynomial time
• $f$ can map every instance $I_A$ of $A$ to an instance $I_B$ of $B$ to $I_B$

• $I_A$ is a "yes" iff $I_B$ is a "yes"

• $A \leq_p B$ means that A is polynomial time reducible to $B$

• $\leq_p$ is a transitive relationship

  • e.g. If $A\leq_p B$, $B\leq_p C$ then $A\leq_p C$

NP

• A problem is in NP if each of its "yes" instance has a concise proof that can be verified in polynomial time

NP-complete

• A problem $A$ is NP-complete if every problem in NP can be reduced to $A$ in polynomial time
• If two problems are both NP-complete then they can be reduced to each other
• If a problem is NP-complete, a polynomial algorithm would implie $NP=P$ since every problem in NP can be reduced to the NPC problem
• Every problem in NP is also NPC by transitivity