Find the shortest path in the graph that starts and ends in a specific node and visits all other nodes exactly once. This kind of a path is also known as a Hamiltonian cycle.

Color the nodes of a graph with as few colors as possible such that connected nodes don't have the same color.

Find a small vertex cover of a graph, a subset of vertices that contains an endpoint of all the edges.

Find a large clique in a graph, a subgraph where all vertex pairs are connected by an edge.

Partition the vertices of the graph such that the cut-set, the edges crossing the partition, have a large total weight.

Find a tree of minimum total edge weight that connects a given set of terminal vertices, optionally using additional intermediate vertices (Steiner points).

Given a weight-limited knapsack and items of various weight and value, fill up the knapsack with as much valua as possible.