In combinatorial optimization, the **set TSP**, also known as the, **generalized TSP**, **group TSP**, **One-of-a-Set TSP**, **Multiple Choice TSP** or **Covering Salesman Problem**, is a generalization of the Traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified disjoint subsets of the vertices of a graph. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore the set TSP is also NP-hard.

There is a direct reduction from set TSP to asymmetric TSP, and thus from set TSP to TSP. The idea is to arbitrarily assign a directed cycle to each set. The salesman, when visiting a vertex in some set, then walks around the cycle for free. To not use the cycle would ultimately be very costly.

### Famous quotes containing the words problem and/or set:

“The general public is easy. You don’t have to answer to anyone; and as long as you follow the rules of your profession, you needn’t worry about the consequences. But the *problem* with the powerful and rich is that when they are sick, they really want their doctors to cure them.”

—Molière [Jean Baptiste Poquelin] (1622–1673)

“Through dinner she felt a gradual icy coldness stealing through her like novocaine. She had made up her mind. It seemed as if she had *set* the photograph of herself in her own place, forever frozen into a single gesture.”

—John Dos Passos (1896–1970)