Given a graph $G$ and a number of node sets, each consisting a number of nodes in $G$. The question is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the problem degenerates to the classic Travel Salesman Problem. Therefore, the problem is NP-hard. The question I'd like to pose here is how to design a PTAS.

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the problem degenerates to the classic travelling salesman problem. Therefore, the problem is NP-hard. The question I'd like to pose here is how to design a polynomial-time approximation scheme.

Given a graph $G$ and a number of node sets, each consisting a number of nodes in $G$. The question is to find the shortest path passing at least one node in each node set. If each node set consists of only one node, the problem degenerates to the classic Travel Salesman Problem. Therefore, the problem is NP-hard. The question I'd like to pose here is how to design a PTAS.

Given a graph $G$ and a number of node sets, each consisting a number of nodes in $G$. The question is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the problem degenerates to the classic Travel Salesman Problem. Therefore, the problem is NP-hard. The question I'd like to pose here is how to design a PTAS.