Exercises on reductions between NP-complete problems

1. SAT $\leq$ 3-SAT
2. SAT $\leq$ DOMINATING SET
3. SAT $\leq$ SET COVERING
4. SAT $\leq$ SET SPLITTING
5. SAT $\leq$ CLIQUE
6. SAT $\leq$ 3-DIMENSIONAL MATCHING
7. SAT $\leq$ FORMULA-NO-EQUIV
8. 3-SAT $\leq$ 1-in-3-SAT
9. 3-SAT $\leq$ NOT-ALL-EQUAL-3-SAT
10. NOT-ALL-EQUAL-3-SAT $\leq$ 3-COLORABILITY
11. 3-COLORABILITY $\leq$ SAT
12. DOMINATING SET $\leq$ SAT
13. CLIQUE $\leq$ SAT
14. CLIQUE $\leq$ INDEPENDENT SET
15. CLIQUE $\leq$ INDUCED SUBGRAPH
16. CLIQUE $\leq$ VERTEX COVER
17. CLIQUE $\leq$ HALF-CLIQUE
18. VERTEX COVER $\leq$ SAT
19. VERTEX COVER $\leq$ SET COVERING
20. VERTEX COVER $\leq$ INDEPENDENT SET
21. VERTEX COVER $\leq$ DOMINATING SET
22. VERTEX COVER $\leq$ DIRECTED HAMILTONIAN CIRCUIT
23. DIRECTED HAMILTONIAN CIRCUIT $\leq$ UNDIRECTED HAMILTONIAN CIRCUIT
24. UNDIRECTED HAMILTONIAN CIRCUIT $\leq$ SAT
25. UNDIRECTED HAMILTONIAN CIRCUIT $\leq$ SPANNING SUBGRAPH
26. UNDIRECTED HAMILTONIAN CIRCUIT $\leq$ UNDIRECTED HAMILTONIAN PATH
27. UNDIRECTED HAMILTONIAN PATH $\leq$ UNDIRECTED HAMILTONIAN CIRCUIT
28. choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Seating Shy Guests
29. choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Placing Fire Extinguishers
30. choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Watching Out For Thieves
31. choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Separating Troublesome People
32. choose$\{$CLIQUE,DS,VC,3C,UHC,SAT$\}$ $\leq$ Firing Married Couples