Theoretical Computer Science
- cc.complexity-theory graph-theory graph-algorithms
- Updated Sat, 25 Jun 2022 18:11:45 GMT
-
What is the complexity of this path problem?
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.)
Solution
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.