On the Complexity of Secluded Path Problems

Path-finding problems are one of the most fundamental graph problems. These problems have been well studied due to their high practicality [7, 9, 3, 1]. However, in many real-world scenarios, simply finding the shortest path is not sufficient. For instance, for secure communication, one may seek a data transmission path for sensitive information that minimizes exposure to potential eavesdroppers. Similarly, in a transportation network, a convoy path that avoids potential attackers could lead to more reliable and secure traveling. In robotics, a path for a robot might need to avoid areas with high sensor noise or potential collisions. These scenarios highlight the need for path-finding problems that consider the seclusion of the path from undesirable elements.

Motivated by these applications, the Short Secluded Path problem has been well studied [2, 11, 28, 21]. A vertex subset $U\subseteq V$ is called $l$-secluded if it has at most $l$ neighbors. Formally, Short Secluded Path is defined as follows.

Short Secluded Path  Instance: An undirected graph $G=(V,E)$ where $|V|=n$ and $|E|=m$, two vertices $s,t\in V$, and two integers $k,l$. Goal: Determine whether $G$ has an $l$-secluded $s$-$t$ path of length at most $k$.

Figure 1 is an illustration of an $l$-secluded $s$-$t$ path of length at most $k$ when $l=5$ and $k=5$.¹¹1In this paper, the length of a path is defined as the number of vertices in the path. Unfortunately, Short Secluded Path is NP-complete in general since it is equivalent to $s$-$t$ Hamiltonian Path if we set $k=n$ and $l=0$. Due to the NP-hardness of $s$-$t$ Hamiltonian Path on restricted graph classes [6, 16], Short Secluded Path is NP-hard even on planar bipartite graphs of maximum degree 3, strongly chordal split graphs, and chordal bipartite graphs.

Thus, there has been considerable interest in its parameterized complexity. For the natural parameters $k$ and $l$, Luckow and Fluschnik [21] show that Short Secluded Path is W[1]-hard when parameterized by $k$, whereas it is fixed-parameter tractable (FPT) when parameterized by $k+l$. Note that the problem is para-NP-complete when parameterized by $l$ due to the hardness of $s$-$t$ Hamiltonian Path. In [28], van Bevern et al. study the fixed-parameter tractability and kernelization complexity of Short Secluded Path for structural parameters related to tree-like structures such as treewidth, vertex cover number, feedback vertex set number, and feedback edge set number. For treewidth tw, the authors presented an FPT algorithm for Short Secluded Path that runs in $2^{O(\text{tw})}{n}^{O(1)}$ time. For kernelization, the problem admits a polynomial kernel when parameterized by the combination of $k,l,$ and feedback vertex set number, and also when parameterized by feedback edge set number alone. In contrast, it does not admit a polynomial kernel when parameterized by vertex cover number, by the combination of $l$ and feedback vertex set number, or by the combination of $k,l,$ and treewidth.

In this paper, we use standard graph-theoretic notations. Let $G=(V,E)$ be an undirected graph, where $V$ is the set of vertices and $E$ is the set of edges. We let $n=|V|$ and $m=|E|$. For a positive integer $n$, let $[n]:=\{1,2,\mathrm{\cdots },n\}$

For a vertex $v\in V$, its neighborhood is $N_G(v)=\{u\in V\mid \{v,u\}\in E\}$. For a vertex subset $U\subseteq V$, $N_G(U)=\{v\in V\setminus U\mid u\in U,\{u,v\}\in E\}$ denotes the set of neighbors of $U$. For simplicity, we sometimes use $N(v)$ and $N(U)$ instead of $N_G(v)$ and $N_G(U)$. The subgraph induced by $U$ is denoted by $G[U]$.

The length of a path is defined by the number of vertices on the path. For two vertices $u,v\in V$, the shortest path distance between $u$ and $v$, denoted by $\mathrm{dist}(u,v)$, is defined as the number of edges (resp., the sum of the weights of edges) in a shortest $u$-$v$ path on unweighted graphs (resp., edge-weighted graphs). Two distinct vertices $u$ and $v$ are called twins if $N(u)\setminus \{v\}=N(v)\setminus \{u\}$. In particular, twins $u$ and $v$ are called true twins if the edge $\{u,v\}$ exists, and otherwise called false twins.

We assume that the readers are familiar with the basic notions of parameterized complexity [5].

In this section, we design an $n^{2^{O(\text{cw})}}$-time algorithm parameterized by cliquewidth for the problem of determining whether $G$ has an $s$-$t$ path $P$ of length $k$ with exactly $l$ neighbors. By solving this for each $k$ and $l$, Secluded $k$-Path and Short Secluded Path can also be solved in time $n^{2^{O(\text{cw})}}$.

Our algorithm is based on dynamic programming on a cliquewidth expression tree of $G$. It is known that for a graph $G$ with cliquewidth $\text{cw}(G)$, a $(2^{\text{cw}(G)+1}-1)$-expression tree $𝒯$ with $O(n)$ nodes can be computed in $O(n^3)$ time [25, 24, 17]. For our algorithm, we must distinguish the source $s$ and target $t$. We achieve this by assigning them two new, unique labels. We can thus assume that we are given an $r$-expression tree $𝒯$ with $r\le 2^{\text{cw}(G)+1}+1$ where $s$ is assigned label $r-1$ and $t$ is assigned label $r$.

For a given expression tree $𝒯$, we execute dynamic programming in a bottom-up manner, from the leaves to the root. For each node $\mu$ in $𝒯$, let $G_{\mu }=(V_{\mu },E_{\mu })$ be the labeled subgraph associated with $\mu$. The DP table at each node $\mu$ stores boolean values for states defined by a tuple of parameters. A state corresponds to the properties of a set $𝒫$ of vertex-disjoint paths within $G_{\mu }$, denoted by ${𝒫}_{\mu }$. Intuitively, each path in ${𝒫}_{\mu }$ represents a sub-path of a potential solution in $G_{\mu }$, i.e., an $s$-$t$ path of length $k$ with $l$ neighbors. Thus, the DP state needs to track the number of vertices of the solution, the number of their neighborhoods, the number of other vertices, and the number of sub-paths with respect to the labels of the endpoints. The information on endpoint labels of sub-paths is used when merging sub-paths at a join node. We use the notation $V({𝒫}_{\mu })$ as a shorthand for ${\bigcup }_{P\in {𝒫}_{\mu }}V(P)$, the set of all vertices in any path in ${𝒫}_{\mu }$. The parameters in our DP state are defined as follows:

• $\mathrm{■}$

  For each label $i\in \{1,\mathrm{\dots },r\}$:

  • –

    $x_i^{\mu }$: the number of vertices in $V({𝒫}_{\mu })$ with label $i$.

  • –

    $y_i^{\mu }$: the number of vertices in $N(V({𝒫}_{\mu }))\cap V_{\mu }$ with label $i$.

  • –

    $z_i^{\mu }$: the number of vertices with label $i$ in $V_{\mu }$ that belong to neither $V({𝒫}_{\mu })$ nor its neighborhood.

• $\mathrm{■}$

  For each pair of labels $i,j$ with $1\le i\le j\le r$:

  • –

    $p_{ij}^{\mu }$: the number of paths in ${𝒫}_{\mu }$ having one endpoint with label $i$ and the other with label $j$.

We call $(x_1^{\mu },\mathrm{\dots },x_r^{\mu })$ the solution count vector, $(y_1^{\mu },\mathrm{\dots },y_r^{\mu })$ the neighborhood count vector, $(z_1^{\mu },\mathrm{\dots },z_r^{\mu })$ the remaining vertex count vector, and $(p_{11}^{\mu },\mathrm{\dots },p_{rr}^{\mu })$ the path count vector, respectively. The DP entry ${\mathrm{DP}}_{\mu }[(x_1^{\mu },\mathrm{\dots },x_r^{\mu }),(y_1^{\mu },\mathrm{\dots },y_r^{\mu }),(z_1^{\mu },\mathrm{\dots },z_r^{\mu }),(p_{11}^{\mu },\mathrm{\dots },p_{rr}^{\mu })]$ is a boolean value. It is true if and only if there exists a set of vertex-disjoint paths ${𝒫}_{\mu }$ in $G_{\mu }$ that satisfies all of the following conditions:

1. 1.

   For each label $i$, the number of vertices in $V({𝒫}_{\mu })$ with label $i$ is exactly $x_i^{\mu }$, i.e., $|V({𝒫}_{\mu })|={\sum }_{i=1}^r{x}_i^{\mu }$.

2. 2.

   For each label $i$, the number of vertices in the neighborhood $N(V({𝒫}_{\mu }))\cap V_{\mu }$ with label $i$ is exactly $y_i^{\mu }$, i.e., $|N(V({𝒫}_{\mu }))|={\sum }_{i=1}^r{y}_i^{\mu }$.

3. 3.

   For each label $i$, the number of vertices with label $i$ in $V_{\mu }$ that belong to neither $V({𝒫}_{\mu })$ nor its neighborhood is exactly $z_i^{\mu }$, i.e., $|V_{\mu }\setminus (V({𝒫}_{\mu })\cup N(V({𝒫}_{\mu })))|={\sum }_{i=1}^r{z}_i^{\mu }$.

4. 4.

   For each pair of labels $(i,j)$, the number of paths in ${𝒫}_{\mu }$ with endpoints labeled $i$ and $j$ is exactly $p_{ij}^{\mu }$.

For convenience, if a set ${𝒫}_{\mu }$ of paths is empty, $|V({𝒫}_{\mu })|=0$. In this case, its neighborhood is also empty, and this corresponds to the state where $x_i^{\mu }=y_i^{\mu }=p_{ij}^{\mu }=0$ for all $i,j$.

From these definitions, $0\le x_i^{\mu },y_i^{\mu },z_i^{\mu },p_{ij}^{\mu }\le n$ for all parameters. Thus, the size of the DP table at each node is bounded by $n^{O(r^2)}$. As initialization, we set all entries of the DP tables to false.

The existence of a solution in the original graph $G$ is determined by checking the DP table of the root node, $\gamma$. A key observation is that an $s$-$t$ path of length $k$ with $l$ neighbors exists if and only if there exists a path $P$ whose endpoints are labeled by $r-1$ and $r$ in $G_{\gamma }$ satisfying $|V(P)|=k,|N(V(P))|=l$, and $|V_{\gamma }\setminus (V(P)\cup N(V(P)))|=n-k-l$. Note that $s$ and $t$ have the unique labels $r-1$ and $r$, respectively. Therefore, an $s$-$t$ path of length $k$ with $l$ neighbors exists if and only if and only if ${\mathrm{DP}}_{\gamma }[(x_1^{\gamma },y_1^{\gamma },z_1^{\gamma }),\mathrm{\cdots },(x_r^{\gamma },y_r^{\gamma },z_r^{\gamma }),(p_{11}^{\gamma },\mathrm{\cdots },p_{rr}^{\gamma })]=\text{true}$ at the root node $\gamma$ such that:

• $\mathrm{■}$

  $x_{r-1}^{\gamma }=x_r^{\gamma }=1$,

• $\mathrm{■}$

  $y_{r-1}^{\gamma }=y_r^{\gamma }=0$,

• $\mathrm{■}$

  $z_{r-1}^{\gamma }=z_r^{\gamma }=0$,

• $\mathrm{■}$

  ${\sum }_{i=1}^r{x}_i^{\gamma }=k$,

• $\mathrm{■}$

  ${\sum }_{i=1}^r{y}_i^{\gamma }=l$,

• $\mathrm{■}$

  ${\sum }_{i=1}^r{z}_i^{\gamma }=n-k-l$,

• $\mathrm{■}$

  $p_{(r-1)r}^{\gamma }=1$, and

• $\mathrm{■}$

  $p_{ij}^{\gamma }=0$ for $i,j(i\le j)$ except $i=r-1$ and $j=r$.

In the following, we describe the recursive formulas for updating the DP table at each node of the expression tree. The updates for introduce, union, and relabel nodes are relatively straightforward, while the update at a join node is the most challenging part. Intuitively, our DP state tracks, for each label, the number of vertices in the solution, their neighborhoods, and the other vertices, as well as the number of vertex-disjoint paths distinguished by their endpoint labels. For an introduce node, which adds a single labeled vertex, we only need to generate the initial states corresponding to this new vertex, forming a trivial path of length one, or being an isolated vertex not part of the solution. For a union node, which combines two disjoint subgraphs, the new DP table is computed by merging states from its two children. As no edges are added between the subgraphs, paths from each part remain separate. Thus, for any pair of valid states (one from each child), we can compute the resulting state’s parameters by simple addition. The update for a relabel node that changes label $i$ to $j$ is also based on addition: for each state, the counts associated with label $i$ are consolidated into the counts for label $j$.

The main challenge lies with the join node, which adds edges between all vertices of label $i$ and all vertices of label $j$. These new edges may connect multiple existing paths into longer ones. Therefore, the core of the update is to iterate through all valid states of the child node and, for each state, enumerate all feasible ways that the paths can be connected. Although the number of ways to connect paths can be large, it can be shown that this process can be handled in time $n^{O(r^2)}$. The running time for a join node is determined by iterating through all possible resulting states. Since the size of the DP table is $n^{O(r^2)}$, and we must process each state from the child’s table, the update at a join node can be performed in time $n^{O(r^2)}$. As the expression tree has $O(n)$ nodes, the total running time is dominated by the join operations, yielding $n^{O(r^2)}=n^{2^{O(\text{cw}(G))}}$. The details of the algorithm are provided in the appendix.

By applying Theorem 6 for each $k,l$, we can also solve Secluded $k$-Path and Short Secluded Path.

In this section, we propose a fixed-parameter algorithm for Short Secluded Path parameterized by neighborhood diversity, which runs in ${\text{nd}}^{O({\text{nd}}^2)}{n}^{O(1)}$ time. To show this, we first provide a fixed-parameter algorithm for $s$-$t$ $k$-Path by neighborhood diversity.

In this section, we design a $2^{O({\text{tc}}^2)}{n}^{O(1)}$-time algorithm for Short Secluded Path and Secluded $k$-Path parameterized by twin cover number.

In this section, we study the computational complexity of Shortest Secluded Path.