Week 13 - NP-complete problems

The following problems are known to be NP-complete:

• Lectures
  • SAT problem - SAT is NP-complete
  • k-SAT - k-SAT is NP-complete for k greater than or equal to 3
  • Independent set of a given size - Independent set of a given size is NP-complete
  • Clique of a given size problem - Clique of a given size problem is NP-complete
  • Vertex cover of a given size - Vertex cover of a given size is NP-complete
  • k-colourings problem (graphs) - The k-colourings problem is NP-complete
  • Knapsack-search - Knapsack-search is NP-complete
  • Subset-sum problem - Subset-sum problem is NP-complete
• Book
  • Traveling salesman problem (search) - ???
  • Rudrata cycle problem - ???
  • Balanced cut problem - ???