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.
More coming soon
3SAT ≤p CLIQUE, VERTEX-COVER, and more on the way.
Want a specific reduction added? Request it by email at contact@csvisualizer.com.