This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in Garey & Johnson (1979).
Graphs and hypergraphs
Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. Facebook or LinkedIn).
- NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.[3]: ND2
- Feedback vertex set[2][3]: GT7
- Feedback arc set[2][3]: GT8
- Graph coloring[2][3]: GT4
- Graph homomorphism problem[3]: GT52
- Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.[3]: GT11, GT12, GT13, GT14, GT15, GT16, ND14
- Grundy number of a directed graph.[3]: GT56
- Hamiltonian completion[3]: GT34
- Hamiltonian path problem, directed and undirected.[2][3]: GT37, GT38, GT39
- Induced subgraph isomorphism problem
- Graph intersection number[3]: GT59
- Longest path problem[3]: ND29
- Maximum bipartite subgraph or (especially with weighted edges) maximum cut.[2][3]: GT25, ND16
- Maximum common subgraph isomorphism problem[3]: GT49
- Maximum independent set[3]: GT20
- Maximum Induced path[3]: GT23
- Minimum maximal independent set a.k.a. minimum independent dominating set[4]
- NP-complete special cases include the minimum maximal matching problem,[3]: GT10 which is essentially equal to the edge dominating set problem (see above).