What is the complexity of this path problem?

Question

Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$.

Question: Does there exist an $s-t$ path in $G$, such that the path touches at most $k$ vertices? (A vertex is touched by the path if the vertex is either on the path, or has a neighbor on the path.)

Answer 1

This problem was studied in:

Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Secluded Connectivity Problems. ESA 2013: 301-312.

http://arxiv.org/pdf/1212.6176v1.pdf

They called it secluded path problem. It's indeed NP-hard, and the optimization version has no constant-factor approximation.

The motivation the authors provide is a setting where the information is sent over the path, and only the neighbors and the nodes in the path can see it. The goal is to minimize the exposure.

Answer 2

Edit: Please see user20655's answer below for a reference to a paper already proving the hardness of this problem. I will leave my original post in, in case anyone wants to see this alternate proof.

===============

Consider an instance of MIN-SAT, which is an NP-hard problem, consisting of variables $X = \{x_1, x_2, \cdots\, x_n\}$ and clauses $C = \{c_1, c_2, c_3, \cdots\}$. We will reduce this to your path problem.

We will have two vertices for each $x_i$ (one for the negated form and one for the unnegated) and one vertex for each $c_i$. Further, letting $m = 2n+|C|$, we will have $m$ vertices $p_1, p_2, \cdots, p_{m}$ for padding.

Roughly speaking, we will construct a graph where the optimal solution will be to build a path from $s$ to $t$ using the $x_i$s and $\bar{x_i}$s as intermediate nodes. The cost of this path will be exactly the $c_j$s that the path we chose would satisfy if we were to turn it into an assignment. The $p_i$s are just there to prevent the optimal solution from being able to cheat by short-cutting through any of the $c_j$s.

Connect $x_i$ to any clause $c_j$ in which $x_i$ appears and $\overline{x_i}$ to any clause $c_j$ in which $\overline{x_i}$ appears. To force an assignment of the variables, we make a diamond ladder-like structure, where $x_i$ and $\overline{x_i}$ are both connected to each of $x_{i+1}$ and $\overline{x_{i+1}}$. $s$ is connected to both $x_1$ and $\overline{x_1}$ and $t$ is connected to both $x_n$ and $\overline{x_n}$. Finally, each $c_i$ is connected to all padding variables $p_j$. I don't have my go-to software for graph drawing handy, so here is an (extremely) crudely-drawn diagram of this construction:

(Note that the $\{P_i\}$ cloud here is just a big set of vertices, and each thick edge from $c_j$ to this cloud represents $c_j$ being connected to each vertex in this set.)

The claim is that in the optimal solution for the min-touching path problem, the number of vertices that will touch the path is $Q + 2n + 2$, where $Q$ is the optimal solution to the MIN-SAT instance. This is because

1. The path needs to start at $s$ and end at $t$, and the best way to do this without collecting all padding vertices is to keep going from $y_i \in \{x_i, \overline{x_i}\}$ to $y_{i+1} \in \{x_{i+1}, \overline{x_{i+1}}\}$ without ever collecting both $x_i$ and $\overline{x_i}$ for any $i \in 1, \cdots, n$ (this is intuitive, as deleting one of the two options from any variable chosen twice yields a valid path with cost no larger than had we kept both in).
2. There is a solution of cost at most $m+2$ that goes $s, x_1, x_2, \cdots, x_n, t$, collecting nothing outside of $s$, $t$, $\{x_i\}$, $\{\overline{x_i}\}$, and $\{c_i\}$. Since any $s-t$ path that gets any padding must contain at least $s$, $t$, some $c_i$, some $x_i$ and $x_j$, and all of $\{p\}$, it has a cost of $\geq m+5$, so it is suboptimal. Thus, the optimal solution does not touch any of the padding vertices, so the path must proceed as outlined in part (1).
3. Call the variable assignments corresponding to vertices that the path goes through (other than $s$ and $t$) the induced assignment of the path. A vertex $c_j$ is touched iff the induced assignment of the path would satisfy clause $c_j$. Conversely, an assignment of the variables that satisfies $Q$ clauses can be transformed into a path that touches exactly $Q$ of the $c_j$s by looking at the path that induces said assignment.
4. Every $x_i$ and $\overline{x_i}$ touches this path, as well as both $s$ and $t$. Together, these contribute $2n + 2$ to the total cost. The rest comes from the $c_i$ that are touched, at a cost of $Q$ in the optimal solution.

Thus, we can check if the MIN-SAT instance has a solution of cost $\leq k$ if the graph we construct has a cost of $\leq k + 2n + 2$ in an instance of your path problem. In particular, we can do this via a Karp-reduction. Thus, the problem as stated is NP-hard.