4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xyguo Apr 28 '18 at 1:54
  • $\begingroup$ OP is assuming $p$ is a constant and is asking for the node-weighted version it seems. The problem should be FPT. $\endgroup$ – Chandra Chekuri Apr 28 '18 at 1:55
  • 4
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Apr 28 '18 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.