<p><strong>Edit:</strong> 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.</p>

<p>===============</p>

<p>Consider an instance of MIN-SAT, <a href="http://ndssl.vbi.vt.edu/Publications/ApproxAlgo.pdf" rel="nofollow noreferrer">which is an NP-hard problem</a>, 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.</p>

<p>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. </p>

<p>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.</p>

<p>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:</p>

<p><img src="https://i.sstatic.net/zemBV.png" alt="Construction of the hard instance"></p>

<p>(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.)</p>

<p>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</p>

<ol>
<li>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).</li>
<li>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 <em>any</em> $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).</li>
<li>Call the variable assignments corresponding to vertices that the path goes through (other than $s$ and $t$) the <em>induced assignment</em> 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.</li>
<li>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.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2014-02-17T09:32:02.250Z
2014-02-17T17:43:00.053Z
2014-02-17T17:43:00.053Z
Yonatan N
<p>This problem was studied in:</p>

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

<p><a href="http://arxiv.org/pdf/1212.6176v1.pdf">http://arxiv.org/pdf/1212.6176v1.pdf</a></p>

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

<p>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. </p>

CC BY-SA 3.0
2014-02-17T14:15:24.880Z
2014-02-17T15:46:04.200Z
2014-02-17T15:46:04.200Z
user20655
<p><strong>Instance:</strong> An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 2$.</p>

<p><strong>Question:</strong> 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.)</p>

CC BY-SA 3.0
2014-02-16T08:08:39.717Z
This sounds like a constrained submodular minimization. Unfortunately, it's not clear that the set of constraints admits an efficient solution.
Suresh Venkat
CC BY-SA 3.0
2014-02-16T23:28:38.690Z
My answer of $A^*$ was probably incorrect! After checking more carefully, the heuristic does not seem to be monotone.
usul
CC BY-SA 3.0
2014-02-17T02:05:22.093Z
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. http://www.computer.org/csdl/proceedings/focs/2009/3850/00/3850a755-abs.html
Chandra Chekuri
CC BY-SA 3.0
2014-02-17T02:23:29.047Z
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
CC BY-SA 3.0
2014-02-17T04:41:01.433Z
@Obinna the caterpillar sub-graph is required to be maximal in a sense, because we must include all neighbors of the longest path
SamM
CC BY-SA 3.0
2014-02-17T06:22:54.323Z
Yes. It also has to be maximal. I have a feeling that this is a hard problem and might be related to bin-packing in some way. I might be wrong though.
Obinna Okechukwu
<cc.complexity-theory><graph-theory><graph-algorithms>
What is the complexity of this path problem?
Andras Farago
# What is the complexity of this path problem?

(Asked by: username_0 on 2014-02-16)

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

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: This sounds like a constrained submodular minimization. Unfortunately, it's not clear that the set of constraints admits an efficient solution.  
> **username_2**: My answer of $A^*$ was probably incorrect! After checking more carefully, the heuristic does not seem to be monotone.  
> **username_3**: 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. http://www.computer.org/csdl/proceedings/focs/2009/3850/00/3850a755-abs.html  
> **username_4**: 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.  
> **username_5**: @Obinna the caterpillar sub-graph is required to be maximal in a sense, because we must include all neighbors of the longest path  
> **username_4**: Yes. It also has to be maximal. I have a feeling that this is a hard problem and might be related to bin-packing in some way. I might be wrong though.  

---

## 2 answers

### Answer by username_7 on 2014-02-17. Score: 14 | Accepted answer

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 by username_6 on 2014-02-17. Score: 10

**Edit:** Please see username_7'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](http://ndssl.vbi.vt.edu/Publications/ApproxAlgo.pdf), 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:

![Construction of the hard instance](https://i.sstatic.net/zemBV.png)

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


---

