# 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 sounds like a constrained submodular minimization. Unfortunately, it's not clear that the set of constraints admits an efficient solution. –  Suresh Venkat Feb 16 '14 at 8:08
My answer of $A^*$ was probably incorrect! After checking more carefully, the heuristic does not seem to be monotone. –  usul Feb 16 '14 at 23:28
Following up on Suresh's comment it is worth while to check the paper "Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions" that shows that submodular cost shortest path is hard. Maybe there are ideas there that show hardness. computer.org/csdl/proceedings/focs/2009/3850/00/… –  Chandra Chekuri Feb 17 '14 at 2:05
This problem can be rephrased as finding a caterpillar sub-graph with at most $k$ vertices that includes $s$ and $t$ on its longest path. –  Obinna Okechukwu Feb 17 '14 at 2:23
@Obinna the caterpillar sub-graph is required to be maximal in a sense, because we must include all neighbors of the longest path –  SamM Feb 17 '14 at 4:41

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.

-

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.

-

Professor Farago, this problem is NP-hard, a reduction from connected Dominating set to this problem is much easier than the reduction from MIN-SAT.

-
Can you give some details as to how this would work? When writing up my solution above, I couldn't figure out how to encode Dominating Set due to the strange $s-t$ path constraint. –  Yonatan N Mar 10 '14 at 6:13
@Yonatan N Dominating Set Problem Input: A graph $G'$ and an integer $k'$. Property: $G'$ contains a dominating set of size at most $k'$. A dominating set is a subset $C\subseteq V$ such that each vertex is either in $C$ or has a neighbor in $C$. $Dominating~Set\leqslant_m^pPath Problem$ Let $G’=G$, $k'=k$, $C=s-t~path$, $G'$ contains a dominating set of size at most $k'$ => G has an $s−t$ path such that the path touches at most $k$ vertices. –  Rupei Xu Mar 10 '14 at 7:00
You didn't specify $s$ and $t$. A length-$3n$ cycle has a dominating set size of $n$, but any $s-t$ path connecting antipodal vertices has cost exactly $1.5n$. In fact, any cost-preserving reduction (like what you tried above, setting $k'=k$) cannot work unless $NP \subseteq DTIME(n^{\log\log n})$, because dominating set has a simple $O(\log n)$ approximation algorithm while the paper linked above shows that SeculdedPath is LabelCover-hard to approximate (and so there is no $O(\log n)$ approximation unless the aforementioned complexity conjecture fails). –  Yonatan N Mar 10 '14 at 9:53
@Yonatan N, it is so enjoyable to discuss with you and happy to know so many different ideas. Yes, I didnt fix the s and t in reduction. However, in theory, dominating set and SAT are all NP-complete problems, either reduction should be equivilent, right? BTW, counting the s-t pairs of a graph can be done in polynomial time, right? correct me if you find anything wrong. Thanks. –  Rupei Xu Mar 10 '14 at 18:29
They're both NP-hard problems to solve exactly, but while one problem has a polynomial time approximation algorithm to solve it within a factor $O(\log n)$, the other is NP-hard to approximate within even $O(\log^2 n)$. Thus, any reduction from the second problem to the first must involve a change in the optimal solution cost, as otherwise the reduction plus the $O(\log n)$ approximation algorithm together yield a polynomial time algorithm for an NP-hard problem. –  Yonatan N Mar 11 '14 at 3:37