How to prove finding two paths that are at least k edges apart is NP-hard?

Question

Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s_1$ and $s_2$ and two end vertices $t_1$ and $t_2$ is there a path from $s_1$ to $t_1$ and $s_2$ to $t_2$ such that the closest number of edges between the two paths is at least $k$? Two paths are $k$ close if the minimum of the shortest distances between any vertex on the first path to any vertex on the second path is $k$.

I was thinking of reducing from 3SAT and letting the first path represent the variables and the second path represent the clauses, but I am unsure where to go from there.

Answer 1

You can reduce from 3SAT.

The graph has two parts. One part is the "variable" part. For each of the variables $v_1,\ldots,v_n$ there are two three vertices $v_i^+,v_i^-,v_i$, and this part consists of the following edges, for $i \in [n]$:

$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$

Here $v_0$ is a new vertex, identified with $s_1$, and $v_n$ is identified with $t_1$.

The second part is the "clause" part. For each of the clauses $C_1,\ldots,C_m$ there four vertices $w_j^1,w_j^2,w_j^3,w_j$, connected much as before, with $s_2$ and $t_2$.

We connect $v_i^b$ with $w_j^r$ via a path of length $k$ (for some large enough constant $k$) if the literal $v_i^b$ (either $v_i$ or $\overline{v_i}$, according to $b$) is the opposite of $j$'th literal in $C_j$.

Also, we take all the mindpoints of these paths, and connect all of them (making them into a clique).

We can think of an $(s_1,t_1)$-path as a truth assignment, and of an $(s_2,t_2)$-path as identifying a satisfied literal in each clause. The minimal distance is more than $k$ if this is indeed the case, and only $k$ otherwise.

You also need to verify that there is no point for the paths to cross between the parts. If only one of the paths crosses, then the two paths will be close together (at some constant distance, which for large enough $k$ will be smaller than $k$) immediately after the crossing. If both cross, then the midpoint clique will ensure that they are at distance at most 1.