bin packing problem | chromatic number problem | clique problem | crossing number problem | directed Hamiltonian cycle problem | domatic number problem | dominating set problem | feedback arc set problem | feedback vertex set problem | Hamiltonian cycle problem | Hamiltonian path problem | hitting set problem | independent set problem | knapsack problem | max cut problem | minimum cover problem | partition problem | satisfiability problem | set packing problem | set splitting problem | ... (total: 27)

The bin packing problem asks if there exists a partition of a finite set of items U into disjoint sets U_1, U_2, ..., U_k such that the sum of the sizes of the items in each U_i is B or less.

Given a graph on n vertices and a positive integer k<=n, the chromatic number problem asks if the vertices of the graph are colorable by k distinct colors in such a way that no adjacent vertices share the same color.

Given a graph and a positive integer k, the clique problem asks if the graph contain a clique of size greater or equal to k.

The crossing number problem asks if a given graph has a crossing number of less than or equal to a nonnegative integer k.

The directed Hamiltonian cycle problem asks if a given graph contains a directed Hamiltonian cycle.

Given a graph G on n vertices and a positive integer k<=n, the domatic number problem asks if the domatic number of G at least k.

Given a graph G on n vertices and a positive integer k<=n, the dominating set problem asks if there is a dominating set of size k or less for G.

Given a directed graph G with arc set A of size m and a positive integer k<=m, the feedback arc problem asks if there is a subset A'⊆A with left bracketing bar A' right bracketing bar <=k such that A' contains at least one arc from every directed cycle in G.

Given a directed graph G with vertex set V of size n and a positive integer k<=n, the feedback vertex problem asks if there is a subset V'⊆V with left bracketing bar V' right bracketing bar <=k such that V' contains at least one vertex from every directed cycle in G.

The Hamiltonian cycle problem asks if a graph contains a Hamiltonian cycle.

Does there exist a function f:V->{1, 2, ..., k} such that f(u)!=f(v) whenever {u, v} element E?

Does G contain a subset V'⊆V with left bracketing bar V' right bracketing bar >=k such that every two vertices in V' are joined by an edge in E?

Can a graph be embedded in the plane with k or fewer pairs of edges crossing one another?

Can the vertex set V of a graph G be partitioned into k'>=k disjoint sets V_1, V_2, ..., V_k' such that each V_i is a dominating set for G?

Is there a subset V'⊆V with left bracketing bar V' right bracketing bar <=k such that for all u element V - V', there is a v element V' for which {u, v} element E?

Does G contain a subset V'⊆V such that left bracketing bar V' right bracketing bar >=K and such that no two vertices in V' are joined by an edge in E?

Does C contain a subset C'⊆C with left bracketing bar C' right bracketing bar with left bracketing bar C' right bracketing bar <=k such that every element of S belongs to at least one member of C'.

Does G contain a subset V⊆V_1 and a subset E⊆E_1 such that left bracketing bar V right bracketing bar = left bracketing bar V_2 right bracketing bar , left bracketing bar E right bracketing bar = left bracketing bar E_2 right bracketing bar , and there exists a one-to-one function f:V_2->V satisfying {u, v} element E_2 iff {f(u), f(v)} element E?

Does M contain a subset M'⊆M such that left bracketing bar M' right bracketing bar = q and no two elements of M' agree in any coordinate?

Is there a subset V'⊆V with left bracketing bar V' right bracketing bar <=K such that for each edge {u, v} element E, at least one of u and v belongs to V'?

| formulation date | formulators | status bin packing problem | | | proved NP-complete chromatic number problem | | | proved NP-complete clique problem | | | proved NP-complete crossing number problem | | | proved NP-complete directed Hamiltonian cycle problem | | | proved NP-complete domatic number problem | 1975 (50 years ago) | Ernest Cockayne | Stephen Hedetniemi | proved NP-complete dominating set problem | | | proved NP-complete feedback arc set problem | | | proved NP-complete feedback vertex set problem | | | proved NP-complete Hamiltonian cycle problem | | | proved NP-complete Hamiltonian path problem | | | proved NP-complete hitting set problem | | | proved NP-complete independent set problem | | | proved NP-complete knapsack problem | | | proved NP-complete max cut problem | | | proved NP-complete minimum cover problem | | | proved NP-complete partition problem | | | proved NP-complete satisfiability problem | | | proved NP-complete set packing problem | | | proved NP-complete set splitting problem | | | proved NP-complete subgraph isomorphism problem | | | proved NP-complete subset product problem | | | proved NP-complete subset sum problem | | | proved NP-complete three-dimensional matching problem | | | proved NP-complete three-satisfiability problem | | | proved NP-complete traveling salesman problem | | | proved NP-complete vertex cover problem | | | proved NP-complete | proof date | provers chromatic number problem | 1972 (53 years ago) | Richard Karp clique problem | 1972 (53 years ago) | Richard Karp crossing number problem | 1983 (42 years ago) | Michael Garey | David S. Johnson directed Hamiltonian cycle problem | 1972 (53 years ago) | Richard Karp domatic number problem | 1976 (1 year later) (49 years ago) | Michael Garey | David S. Johnson | Robert Tarjan feedback arc set problem | 1972 (53 years ago) | Richard Karp feedback vertex set problem | 1972 (53 years ago) | Richard Karp Hamiltonian cycle problem | 1972 (53 years ago) | Richard Karp hitting set problem | 1972 (53 years ago) | Richard Karp knapsack problem | 1972 (53 years ago) | Richard Karp max cut problem | 1972 (53 years ago) | Richard Karp minimum cover problem | 1972 (53 years ago) | Richard Karp partition problem | 1972 (53 years ago) | Richard Karp satisfiability problem | 1971 (54 years ago) | Stephen Cook set packing problem | 1972 (53 years ago) | Richard Karp set splitting problem | 1973 (52 years ago) | László Lovász subgraph isomorphism problem | 1971 (54 years ago) | Stephen Cook subset product problem | 1972 (53 years ago) | Richard Karp subset sum problem | 1972 (53 years ago) | Richard Karp three-dimensional matching problem | 1972 (53 years ago) | Richard Karp three-satisfiability problem | 1971 (54 years ago) | Stephen Cook vertex cover problem | 1972 (53 years ago) | Richard Karp

NP complete problems | NP problems | mathematical problems | solved mathematics problems