“Smallest” path that visits a given set of vertices

Question

I use smallest rather than shortest to distinguish between the shortest path problem. The problem is as follows:

Given a directed graph $G=(V,E)$, two vertices $s$ and $t$, and a set of $p$ vertices $x_1,x_2,\ldots, x_p$. The goal is to find a $s-t$ path which visits all of $x_1,\ldots, x_p$, such that the size of the set of visited vertices is minimized. Here we can assume $p$ is a constant, and the path needs not to be simple.

At first I thought this is the same as "shortest path that visits a certain set of vertices" problem, and I know this problem can be reduced to the TSP problem. Since $p$ is a constant, I can enumerate all possible visiting orders of $x_1,\ldots,x_p$ and compute the union of the shortest paths between consecutive vertices in each order.

However, because we don't require the path to be simple, I'm not sure whether the shortest path is equivalent to the smallest path desired by the problem. I feel that it's possible to find a path which is long in the sense that some vertices of it are visited many times, but small in the sense that the number of all unique vertices are small. But till now I don't find such an example.

Although I don't have an algorithm, I believe the problem is polytime solvable. Any suggestions?

Answer 1

So you want to find the smallest set $S$ of vertices that can be used for a walk containing $s$, $t$, and the vertices $x_i$, from $s$ to $t$. In the undirected case this can be simplified to: you want to find the smallest set $S$ of vertices containing $s$, $t$, and $x_i$ such that $S$ is connected.

This is the graph Steiner tree problem and is NP-hard. You are looking at the directed case, but making this problem directed cannot make it easier, so it remains NP-hard. The reduction from the undirected case is: replace each undirected edge by two directed edges, one in each direction.