Complexity Reductions
Polynomial-time mapping reductions. These transfer hardness: if A ≤p B and A is hard, so is B. They are the tool used to prove NP-completeness.
HAMPATH ≤p HAMCYCLE
Polynomial-time reduction from Hamiltonian path to Hamiltonian cycle.
HAMCYCLE ≤p HAMPATH
The reverse direction: reduce Hamiltonian cycle to Hamiltonian path by duplicating one vertex.
INDEPENDENT-SET ≤p CLIQUE
Take the complement graph: independent sets in G correspond to cliques in G̅.
CLIQUE ≤p INDEPENDENT-SET
The reverse direction via the same complement-graph construction.
Request more
Missing something? Get in touch and we'll add it.