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


This problem was studied in:

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

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.

External Links

External links referenced by this document: