<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2018-04-28T01:54:53.530Z
This is easier than the Steiner tree problem as p (the number of terminals) is constant in my problem. I know a dynamic programming algorithm that solves the Steiner tree problem in time exponential in p.  But I don’t think that algorithm can be adopted here.
xyguo
CC BY-SA 3.0
2018-04-28T01:55:28.980Z
OP is assuming $p$ is a constant and is asking for the node-weighted version it seems. The problem should be FPT.
Chandra Chekuri
CC BY-SA 3.0
2018-04-28T02:22:51.910Z
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
CC BY-SA 3.0
2018-04-28T01:37:10.273Z
2018-04-28T01:37:10.273Z
David Eppstein
<p>I use <em>smallest</em> rather than <em>shortest</em> to distinguish between the shortest path problem. The problem is as follows:</p>

<blockquote>
  <p>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 <strong>set</strong> of visited vertices is minimized. Here we can assume $p$ is a constant, and the path needs not to be simple.</p>
</blockquote>

<p>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.</p>

<p>However, because we don't require the path to be simple, I'm not sure whether the shortest path is equivalent to the <em>smallest</em> 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. </p>

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

<ds.algorithms><graph-algorithms>
"Smallest" path that visits a given set of vertices
xyguo
# "Smallest" path that visits a given set of vertices

(Asked by: username_0 on 2018-04-28)

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?

**Tags:** ds.algorithms, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2018-04-28. Score: 3

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.

> **Comments:**
> **username_0**: This is easier than the Steiner tree problem as p (the number of terminals) is constant in my problem. I know a dynamic programming algorithm that solves the Steiner tree problem in time exponential in p.  But I don’t think that algorithm can be adopted here.  
> **username_2**: OP is assuming $p$ is a constant and is asking for the node-weighted version it seems. The problem should be FPT.  
> **username_2**: 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.  

---

