NP- complete Problems with variations

K-clique                           video

•    half-clique
•   quarter-clique
•   sub-graph  isomorphism
•   Independent set                  video
•   vertex cover                       video
•   Exact Cover                       video

Hamiltonian Path                   video lecture

• Does a hamiltonian path exist in G.
• Does a hamiltonian path exist from node s to t
• k-link path 
• Hamiltonian Circuit       video

SAT Problems                    video

• TRUE-SAT
• DOUBLE-SAT
• 3SAT
• HALF-SAT
• not equal to 3SAT

Subset Sum Problem              video

• Partition                       video
• Multiset                        video

3-COLOR