- cc.complexity-theory graph-theory graph-algorithms
- Updated Sat, 25 Jun 2022 18:11:45 GMT

**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.)

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.