# Tag Info

Let $G=(V,E)$ be the graph and let $S$ be the set of cities you want to visit. Since you talk about "covering" all the cities, it might be the case that you are fine with visiting cities more than once as long as all cities in $S$ are visited at least once. The problem is still NP-hard in this case (see Juho's answer), but it can be 1.5-...