Complexitarium

A collection of optimization problems and their characteristics related to computational complexity theory.

Related resources

• Complexity Zoo

• Complexity Zoology Introduction

• Information System on Graph Classes and their Inclusions

• Algorithm Repository

• Complexity results for scheduling problems

• Complexity of Games

• Open Problem Garden

• Wikipedia List of NP-complete problems

• A compendium of NP optimization problems

• An Annotated List of Selected NP-complete Problems

• Graph of NP-Complete Problems

• Theoretical Computer Science on StackExchange

• Computational Complexity blog

NP-complete

• 3-Dimensional Matching
• 3-Satisfiability
• Achromatic Number
• Bin Packing
• Bounded Diameter Spanning Tree
• Clique
• Covering by Cliques
• Covering by Complete Bipartite Subgraphs
• Cubic Subgraph
• Degree Constrained Spanning Tree
• Directed Hamiltonian Circuit
• Domatic Number
• Dominating Set
• Exact Cover by 3-Sets
• Feedback Arc Set
• Feedback Vertex Set
• Graph K-Colorability
• Hamiltonian Circuit
• Hamiltonian Path
• Hitting Set
• Independent Set
• Induced Path
• Knapsack
• Longest Path
• Max Cut
• Maximum 2-Satisfiability
• Maximum Leaf Spanning Tree
• Minimum Cover
• Minimum Equivalent Digraph
• Minimum Maximal Matching
• Monochromatic Triangle
• Multiprocessor Scheduling
• Not-All-Equal 3SAT
• One-in-Three 3SAT
• Partial Feedback Edge Set
• Partition into Cliques
• Partition into Forests
• Partition into Isomorphic Subgraphs
• Partition into Perfect Matchings
• Partition into Triangles
• Partition
• Path Graph Completion
• Satisfiability
• Set Packing
• Traveling Salesman
• Uniconnected subgraph
• Vertex Cover