# “Smallest” path that visits a given set of vertices

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?

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.
• OP is assuming $p$ is a constant and is asking for the node-weighted version it seems. The problem should be FPT. – Chandra Chekuri Apr 28 '18 at 1:55
• As David pointed out the problem is closely related to the Steiner tree problem. It is not hard to see that what we want is a Steiner tree $T$ in $G$ with terminal set $S = \{s,t,x_1,x_2,\ldots,x_p\}$ so that we minimize the number of non-terminal nodes in $T$. In effect this is node-weighted Steiner tree when the number of terminals in a fixed constant $p$. There is an FPT algorithm for the edge-weighted case via dynamic programming. We can use the same idea but compute shortest paths using node-weights instead of edge weights. Details are messy but should not be hard. – Chandra Chekuri Apr 28 '18 at 2:22