Parameterized Complexity of $(A,\ell )$-Path Packing

Abstract

Given a graph $G = (V,E)$, $A \subseteq V$, and integers k and $\ell$, the $(A,\ell )$ -Path Packing problem asks to find k vertex-disjoint paths of length exactly $\ell$ that have endpoints in A and internal points in $V{\setminus }A$. We study the parameterized complexity of this problem with parameters |A|, $\ell$, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $\ell \le 3$, while it is NP-complete for constant $\ell \ge 4$. We also show that the problem is W[1]-hard parameterized by pathwidth${}+|A|$, while it is fixed-parameter tractable parameterized by treewidth${}+\ell$. Additionally, we study a variant called Short A -Path Packing that asks to find k vertex-disjoint paths of length at most $\ell$. We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or $\ell$ is a constant.

1 Introduction

Let $G = (V,E)$ be a graph and $A \subseteq V$. A path P in G with at least one edge is an A-path if the first and last vertices of P belong to A and all other vertices of P belong to $V {\setminus } A$. Given G and A, A -Path Packing is the problem of finding the maximum number of vertex-disjoint A-paths in G. The A -Path Packing problem is well studied and even some generalized versions are known to be polynomial-time solvable (see e.g., [7, 8, 17, 26, 31, 32]). Note that A -Path Packing is a generalization of Maximum Matching since they are equivalent when $A = V$.

In this paper, we study a variant of A -Path Packing that also generalizes Maximum Matching. An A-path of length $\ell$ is an $(A,\ell )$-path, where the length of a path is the number of edges in the path. Now our problem is defined as follows:

To the best of our knowledge, this natural variant of A -Path Packing was not studied in the literature. Our main motivation of studying ALPP is to see theoretical differences from the original A -Path Packing, but5r practical motivations of having the length constraint may come from some physical restrictions or some fairness requirements. Note that if $\ell = 1$, then ALPP is equivalent to Maximum Matching. Another related problem is $\ell$ -Path Partition [29, 33, 34], which asks for vertex-disjoint paths of length $\ell$ (without specific endpoints).

In the rest of paper, we assume that $k \le |A|/2$ in every instance as otherwise the instance is a trivial no-instance. The restricted version of the problem where the equality $k = |A|/2$ is forced is also of our interest as that version corresponds to a “full” packing of A-paths. We call this version Full $(A,\ell )$ -Path Packing (Full-ALPP, for short). In this paper, all our positive results showing tractability of some cases will be on the general ALPP, while all our negative (or hardness) results will be on the possibly easier Full-ALPP.

We also study a natural variant of ALPP, which we call Short A -Path Packing. The problem is defined as follows, where an $A_{\le \ell }$-path is an A-path of length at most $\ell$:

Similarly to Full-ALPP, we define Full-SAPP as the restricted version of SAPP with $k = |A|/2$.

We assume that the reader is familiar with terminologies in the parameterized complexity theory. See the textbook by Cygan et al. [11] for standard definitions.

1.1 Our Results

In summary, we show that ALPP is intractable even on very restricted inputs, while it has some nontrivial cases that admit efficient algorithms. (See Fig. 1.)

We call |A|, k, and $\ell$ the standard parameters of ALPP as they naturally arise from the definition of the problem. We determine the complexity of ALPP with respect to all standard parameters and their combinations. We first observe that Full-ALPP is NP-complete for any constant $|A| \ge 2$ (Observation 3.1) and for any constant $\ell \ge 4$ (Observation 3.2), while it is polynomial-time solvable when $\ell \le 3$ (Theorem 3.3). On the other hand, ALPP is fixed-parameter tractable when parameterized by $k + \ell$ and thus by $|A| + \ell$ as well (Theorem 3.5). We later strengthen Observation 3.2 by showing that the problem is NP-complete for every fixed $\ell \ge 4$ even on grid graphs (Theorem 5.3).

We then study structural parameters such as treewidth and pathwidth in combination with the standard parameters. We first observe that ALPP can be solved in time $n^{O(\mathsf {tw})}$ (Observation 4.1), where n and $\mathsf {tw}$ are the number of vertices and the treewidth of the input graph, respectively. Furthermore, we show that ALPP parameterized by $\mathsf {tw}+ \ell$ is fixed-parameter tractable (Observation 4.2). We finally show that Full-ALPP parameterized by $\mathsf {pw}+ |A|$ is W[1]-hard (Theorem 4.5), where $\mathsf {pw}$ is the pathwidth of the input graph.

For SAPP, a simple reduction (Lemma 6.1) will show that all our positive results on ALPP hold also on this short-path version. Although negative results cannot be translated directly, we can show the hardness of the cases where |A| or $\ell$ is a constant (Theorems 6.6 and 6.7). We leave the complexity of SAPP parameterized by $\mathsf {tw}$ unsettled.

Fig. 1

Summary of the results. An arrow $\alpha \rightarrow \beta$ indicates that there is a function f such that $\alpha \ge f(\beta )$ for every instance of ALPP. Some possible arrows are omitted to keep the figure readable. The results on the parameters marked with $*$ are explicitly shown in this paper, and the other results follow by the hierarchy of the parameters. We have a bidirectional arrow $\text {treedepth} \leftrightarrow \text {treedepth} + \ell$ because the maximum length of a path in a graph is bounded by a function of treedepth [30, Section 6.2]

2 Preliminaries

A graph $G = (V,E)$ is a grid graph if V is a finite subset of $\mathbb {Z}^{2}$ and $E = \{\{(r,c), (r',c')\} \mid |r-r'| + |c-c'| = 1\}$. From the definition, all grid graphs are planar, bipartite, and of maximum degree at most 4. To understand the intractability of a graph problem, it is preferable to show hardness on a very restricted graph class. The class of grid graphs is one of such target classes.

A tree decomposition of a graph $G = (V,E)$ is a pair $(\{X_{i} \mid i \in I\}, T=(I,F))$, where $X_{i} \subseteq V$ for each i and T is a tree such that

• for each vertex $v \in V$, there is $i \in I$ with $v \in X_{i}$;

• for each edge $\{u,v\} \in E$, there is $i \in I$ with $u, v \in X_{i}$;

• for each vertex $v \in V$, the induced subgraph $T[\{i \mid v \in X_{i}\}]$ is connected.

The width of a tree decomposition $(\{X_{i} \mid i \in I\}, T)$ is $\max _{i \in I} |X_{i}| - 1$, and the treewidth of a graph G, denoted $\mathsf {tw}(G)$, is the minimum width over all tree decompositions of G.

The pathwidth of a graph G, denoted $\mathsf {pw}(G)$, is defined by restricting the trees T in tree decompositions to be paths. We call such decompositions path decompositions. It is easy to see that pathwidth does not change significantly by subdividing some edges and attaching paths to some vertices. To be self-contained, we present a proof in the appendix (see Section A).

Lemma 2.1

If $G'$ is a graph obtained from a graph $G = (V,E)$ by subdividing a set of edges $F \subseteq E$ an arbitrary number of times, and attaching a path of arbitrary length to each vertex in a set $U \subseteq V$, then $\mathsf {pw}(G') \le \mathsf {pw}(G) + 2$.

3 Standard Parameterizations of ALPP

In this section, we completely determine the complexity of ALPP with respect to the standard parameters |A|, k, $\ell$, and their combinations. (Recall that $k \le |A|/2$.) We first observe that using one of them as a parameter does not make the problem tractable. That is, the problem remains NP-complete even if one of |A|, k, $\ell$ is a constant. We then show that the problem is tractable when $\ell \le 3$ or when $k+\ell$ is the parameter.

3.1 Intractable Cases

The first observation is that Full-ALPP is NP-complete on grid graphs even if $|A| = 2$ (and thus $k = 1$). This can be shown by an easy reduction from Hamiltonian Cycle on grid graphs [20]. This observation is easily extended to every fixed even |A| by adding dummy paths of length $\ell$ as connected components into the graph and their endpoints into A.

Observation 3.1

For every even constant $\alpha \ge 2$, Full-ALPP with $|A| = \alpha$ is NP-complete on grid graphs.

The NP-hardness of Full-ALPP for fixed $\ell \ge 4$ can be shown by an easy reduction from Path Partition [21].

Observation 3.2

For every constant $\ell \ge 4$, Full-ALPP is NP-complete.

We omit the proof as we later strengthen Observation 3.2 to hold on grid graphs (see Sect. 5). Note that the condition $\ell \ge 4$ in the statement above is tight as the problem is polynomial-time solvable when $\ell \le 3$ (see Theorem 3.3).

3.2 Tractable Cases

Theorem 3.3

If $\ell \le 3$, then ALPP can be solved in time $O(\sqrt{n} \cdot m)$, where n and m are the numbers of vertices and edges, respectively.

Proof

Let $(G,A,k,\ell )$ with $G = (V,E)$ be an instance of ALPP with $\ell \le 3$. We reduce, in linear time, the problem to the maximum cardinality matching problem on graphs with O(|V|) vertices and O(|E|) vertices. This proves the theorem since the maximum cardinality matching problem can be solved in time $O(\sqrt{n} \cdot m)$ [28].

If $\ell = 1$, then the problem is equivalent to the maximum cardinality matching problem on G[A]. Assume that $\ell = 2$. We reduce this case to the case of $\ell = 3$. We can assume that G[A] and $G[V {\setminus } A]$ do not contain any edges as such edges are not included in any (A, 2)-path. The new instance $(G',A,k,3)$ is constructed by adding a true twin $v'$ to each vertex $v \in V {\setminus } A$; i.e., $V(G') = V \cup \{v' \mid v \in V {\setminus } A\}$ and $E(G') = E \cup \{\{v,v'\} \mid v \in V {\setminus } A \} \cup \{\{u,v'\} \mid u \in A, v \in V {\setminus } A, \{u,v\} \in E\}$. Clearly, (G, A, k, 2) is a yes-instance if and only if so is $(G',A,k,3)$.

For the case of $\ell = 3$, we construct an auxiliary graph $G' = (A \cup V_{1} \cup V_{2}, E_{A,1} \cup E_{1,2} \cup E_{2,2})$ as follows (see Fig. 2):

$$\begin{aligned} V_{i}&= \{v_{i} \mid v \in V {\setminus } A\} \text { for } i \in \{1,2\}, \\ E_{A,1}&= \{\{u, v_{1}\} \mid u \in A, \; v \in V {\setminus } A, \; \{u,v\} \in E\}, \\ E_{1,2}&= \{\{v_{1}, v_{2}\} \mid v \in V\}, \\ E_{2,2}&= \{\{u_{2},v_{2}\} \mid u,v \in V {\setminus } A, \; \{u,v\} \in E\}. \end{aligned}$$

We show that (G, A, k, 3) is a yes-instance if and only if $G'$ has a matching of cardinality $k + |V {\setminus } A|$.

Fig. 2

The construction of $G'$ (right) from G (left)

To prove the only-if direction, let $P_{1}, \dots , P_{k}$ be k vertex-disjoint (A, 3)-path in G. We set $M = M_{A,1} \cup M_{1,2} \cup M_{2,2}$, where

$$\begin{aligned} M_{A,1}&= \{\{u, v_{1}\} \in E_{A,1} \mid \text {edge } \{u,v\} \text { appears in some } P_{i}\}, \\ M_{1,2}&= \{\{v_{1}, v_{2}\} \in E_{1,2} \mid \text {vertex } v \text { does not appear in any } P_{i}\}, \\ M_{2,2}&= \{\{u_{2},v_{2}\} \in E_{2,2} \mid \text {edge } \{u,v\} \text { appears in some } P_{i}\}. \end{aligned}$$

Since the (A, 3)-paths $P_{1}, \dots , P_{k}$ are pairwise vertex-disjoint, M is a matching. We can see that $|M| = k + |V {\setminus } A|$ as $|M_{2,2}| = k$ and $|M_{A,1}| + |M_{1,2}| = |V_{1}| = |V {\setminus } A|$.

To prove the if direction, assume that $G'$ has a matching of size $k+|V {\setminus } A|$. Let M be a maximum matching of $G'$ that includes the maximum number of vertices in $V_{1} \cup V_{2}$ among all maximum matchings of $G'$. We claim that M actually includes all vertices in $V_{1} \cup V_{2}$. Suppose to the contrary that $v_{1}$ or $v_{2}$ is not included in M for some $v \in V {\setminus } A$. Now, since M is maximum, exactly one of $v_{1}$ and $v_{2}$ is included in M.

Case 1: $v_{1} \in V(M)$ and $v_{2} \notin V(M)$. There is a vertex $u \in A$ such that $\{u, v_{1}\} \in M$. The set $M - \{u, v_{1}\} + \{v_{1}, v_{2}\}$ is a maximum matching that uses more vertices in $V_{1} \cup V_{2}$ than M. This contradicts how M was selected.

Case 2: $v_{1} \notin V(M)$ and $v_{2} \in V(M)$. There is a vertex $w_{2} \in V_{2}$ such that $\{v_{2}, w_{2}\} \in M$. The edge set $M' := M - \{v_{2}, w_{2}\} + \{v_{1}, v_{2}\}$ is a maximum matching that uses the same number of vertices in $V_{1} \cup V_{2}$ as M. Since $M'$ is maximum and $w_{2}$ is not included in $M'$, the vertex $w_{1}$ has to be included in $M'$, but such a case leads to a contradiction as we saw in Case 1.

Now we construct k vertex-disjoint (A, 3)-paths from M as follows. Let $\{u_{2}, v_{2}\} \in M \cap E_{2,2}$. Since M includes all vertices in $V_{1}$, it includes edges $\{u_{1}, x\}$ and $\{v_{1}, y\}$ for some $x, y \in A$. This implies that G has an (A, 3)-path (x, u, v, y). Let $(x', u', v', y')$ be the (A, 3)-path constructed in the same way from a different edge in $M \cap E_{2,2}$. Since M is a matching, these eight vertices are pairwise distinct, and thus (x, u, v, y) and $(x', u', v', y')$ are vertex-disjoint (A, 3)-paths. Since $|M| \ge k + |V {\setminus } A|$ and each edge in $E_{A,1} \cup E_{1,2}$ uses one vertex of $V_{1}$, M includes at least k edges in $E_{2,2}$. By constructing an (A, 3)-path for each edge in $M \cap E_{2,2}$, we obtain a desired set of k vertex-disjoint (A, 3)-paths. $\square$

In their celebrated paper on Color-Coding [1], Alon, Yuster, and Zwick showed the following result.

Proposition 3.4

([1, Theorem 6.3]) Let H be a graph on h vertices with treewidth t. Let G be a graph on n vertices. A subgraph of G isomorphic to H, if one exists, can be found in time $O(2^{O(h)} \cdot n^{t+1} \log n)$.

By using Proposition 3.4 as a black box, we can show that ALPP parameterized by $k + \ell$ is fixed-parameter tractable.

Theorem 3.5

ALPP on n-vertex graphs can be solved in $O(2^{O(k \ell )} n^{6} \log n)$ time.

Proof

Let $(G,A,k,\ell )$ be an instance of ALPP. Observe that the problem ALPP can be seen as a variant of the Subgraph Isomorphism problem as we search for $H = k P_{\ell +1}$ in G as a subgraph with the restriction that each endpoint of $P_{\ell +1}$ in H has to be mapped to a vertex in A, where $P_{\ell +1}$ denotes an $(\ell +1)$-vertex path (which has length $\ell$) and $k P_{\ell +1}$ denotes the disjoint union of k copies of $P_{\ell +1}$. We reduce this problem to the standard Subgraph Isomorphism problem [18].

Let $G'$ and $H'$ be the graphs obtained from G and H, respectively, by subdividing each edge once. The graphs $G'$ and $H' = k P_{2\ell + 1}$ are bipartite. We then construct $G''$ from $G'$ by attaching a triangle to each vertex in A; that is, for each vertex $u \in A$ we add two new vertices v, w and edges $\{u,v\}$, $\{v,w\}$, and $\{w,u\}$. Similarly, we construct $H''$ from $H'$ by attaching a triangle to each endpoint of each $P_{2\ell +1}$. Note that $|V(G'')| \in O(n^{2})$, $|V(H'')| = k(2 \ell + 1)$, and $\mathsf {tw}(H'') = 2$. Thus, by Proposition 3.4, it suffices to show that $(G,A,k,\ell )$ is a yes-instance of ALPP if and only if $G''$ has a subgraph isomorphic to $H''$.

To show the only-if direction, assume that G has k vertex-disjoint $(A,\ell )$-paths $P_{1}, \dots , P_{k}$. In $G''$, for each $P_{i}$, there is a unique path $Q_{i}$ of length $2\ell$ plus triangles attached to the endpoints; that is, $Q_{i}$ consists of the vertices of $P_{i}$, the new vertices and edges introduced by subdividing the edges in $P_{i}$, and the triangles attached to the endpoints of the subdivided path. Furthermore, since the paths $P_{i}$ are pairwise vertex-disjoint, the subgraphs $Q_{i}$ of $G''$ are pairwise vertex-disjoint. Thus, $G''$ has a subgraph isomorphic to $H'' = \bigcup _{1 \le i \le k} Q_{i}$.

To prove the if direction, assume that $G''$ has a subgraph X isomorphic to $H''$. Let $R_{1}, \dots , R_{k}$ be the connected components of X. Each $R_{i}$ is isomorphic to a path of length $2\ell$ with a triangle attached to each endpoint. Let $u, v \in V(R_{i})$ be the degree-3 vertices of $R_{i}$. Since $G''$ is obtained from the triangle-free graph $G'$ by attaching triangles at the vertices in A, we have $u, v \in A$. Since the u-v path of length $2\ell$ in $R_{i}$ is obtained from a u-v path of length $\ell$ in G by subdividing each edge once, the graph $G[V(R_{i}) \cap V(G)]$ contains an $(A,\ell )$-path. Since $V(R_{1}), \dots , V(R_{k})$ are pairwise disjoint, G contains k vertex-disjoint $(A,\ell )$-paths. $\square$

4 Structural Parameterizations

In this section, we study structural parameterizations of ALPP. First we present XP and FPT algorithms parameterized by $\mathsf {tw}$ and $\mathsf {tw}+ \ell$, respectively. As the techniques are rather standard in the field, we only sketch the high-level ideas of the algorithms.

The XP-time algorithm parameterized by $\mathsf {tw}$ is a standard dynamic-programming over a tree decomposition. We first compute a nice tree decomposition of width $O(\mathsf {tw})$ using known algorithms [4, 6, 23] and then solve the problem in a bottom-up manner. The DP table for each bag stores the existence of a partial solution for all possible ways of the intersection between the bag and the partial solution. Since a bag intersects at most $O(\mathsf {tw})$ vertex-disjoint $(A,\ell )$-paths, it is straightforward to see that the table size can be bounded by $(|A| \cdot \ell )^{O(\mathsf {tw})}$ and that we can compute all entries of the tables for all bags in time polynomial in the total table size. As |A| and $\ell$ are at most n, the total running time is $n^{O(\mathsf {tw})}$.

Observation 4.1

ALPP can be solved in time $n^{O(\mathsf {tw})}$, where n is the number of vertices.

The FPT algorithm parameterized $\mathsf {tw}+ \ell$ is achieved by expressing the problem in the monadic second-order logic ($\hbox {MSO}_{{2}}$) on graphs. It is known that given an n-vertex graph of treewidth w and assignments to some free variables of an $\hbox {MSO}_{{2}}$ formula $\varphi$, one can find in time $O(f(|\varphi | + w) \cdot n)$, where f is some computable function, an assignment to the rest of free variables that satisfies $\varphi$ and maximizes a given linear function in the sizes of the free variables of $\varphi$ [2, 4, 10]. It is straightforward to express in $\hbox {MSO}_{{2}}$ a formula $\varphi _{\ell }(X,Y)$ with two free variables X and Y such that

• the length of $\varphi _{\ell }(X,Y)$ depends only on $\ell$, and

• when we assign a vertex set A to X and an edge set F to Y, G models $\varphi _{\ell }(X,Y)$ if and only if G has vertex-disjoint $(A,\ell )$-paths formed by F.

We assign the terminal vertex set A in the input of ALPP to the variable X, and maximize the size of the edge set F assigned to Y. As mentioned above, this can be done in time $O(f(|\varphi _{\ell }| + w) \cdot n)$ for n-vertex graphs of treewidth at most w, where f is some computable function.

Observation 4.2

ALPP parameterized by $\mathsf {tw}+ \ell$ is fixed-parameter tractable.

Now we show that Full-ALPP is W[1]-hard parameterized by pathwidth (and hence also by treewidth), even if we also consider |A| as an additional parameter. We present a reduction from a W[1]-complete problem k-Multi-Colored Clique (k-MCC) [15], which goes through an intermediate version of our problem. Specifically, we will consider a version of Full-ALPP with the following modifications: the graph has (positive integer) edge weights, and the length of a path is the sum of the weights of its edges; the set A is given to us partitioned into pairs indicating the endpoints of the sought A-paths; for each such pair the value of $\ell$ may be different.

More formally, Extended-ALPP is the following problem: we are given a graph $G=(V,E)$, a weight function $w :E \rightarrow \mathbb {Z}^+$, and r triples $(s_1,t_1,\ell _1)$, $\ldots$, $(s_r,t_r,\ell _r) \in V \times V \times \mathbb {Z}^+$, where all $s_{i}, t_{i} \in V$ are distinct. We are asked if there exists a set of r vertex-disjoint paths in G such that for each $i \in [r]$¹, the ith path in this set has $s_i$ and $t_i$ as its endpoints and the sum of the weights of its edges is $\ell _{i}$. We first show that establishing that this variation of the problem is hard implies also the hardness of Full-ALPP.

Lemma 4.3

There exists an algorithm which, given an instance of Extended-ALPP on an n-vertex graph G with r triples and maximum edge weight W, constructs in time polynomial in $n+W$ an equivalent instance $(G',A,|A|/2,\ell )$ of Full-ALPP with the properties: (i) $|A|=2r$, (ii) $\mathsf {pw}(G')\le \mathsf {pw}(G)+2$.

Proof

First, we simplify the given instance of Extended-ALPP by removing edge weights: for every edge $e=\{u,v\}\in E(G)$ with $w(e)>1$, we remove this edge and replace it with a path from u to v with length w(e) going through new vertices (in other words, e has been subdivided $w(e)-1$ times). It is not hard to see that we have an equivalent instance of Extended-ALPP on the new graph, which we call $G_1$, where the weight of all edges is 1 and $|V(G_1)| \le n^{2} \cdot W$. We now give a polynomial-time reduction from this new instance of Extended-ALPP to Full-ALPP.

Let $p=|V(G_1)|$ and $\ell = 2 p^{2}$. For each $i\in [r]$ we do the following: we construct a new vertex $s_i'$ and connect it to $s_i$ using a path of length $p^{2} + ip$ going through new vertices; we construct a new vertex $t_i'$ and connect it to $t_i$ using a path of length $p^{2}-ip -\ell _i$ through new vertices. (Note that $p^{2}-ip -\ell _{i} > 0$ since $p \ge n \ge 2$, $i \le n/2$, and $\ell _{i} < n$.) We set A to contain all the vertices $s_i', t_i'$ for $i\in [r]$. This completes the construction and it is clear that $|A|=2r$, the new graph $G'$ has order at most $2p^{3} \le 2 n^{6} \cdot W^{3}$ and can be constructed in time polynomial in $n+W$.

We claim that the new graph $G'$ has |A|/2 vertex-disjoint $(A,\ell )$-paths if and only if the Extended-ALPP instance of $G_1$ has a positive answer. Indeed, if there exists a collection of r vertex-disjoint paths in $G_1$ such that the i-th path has endpoints $s_i,t_i$ and length $\ell _i$, we add to this path the paths from $s_i'$ to $s_i$ and from $t_i$ to $t_i'$ and this gives a path of length $\ell = 2p^{2}$ with endpoints in A. Observe that all these paths are vertex-disjoint, so we obtain a yes-certificate of Full-ALPP. For the converse direction, suppose that $G'$ has a set $\mathcal {A}$ of |A|/2 vertex-disjoint $(A,\ell )$-paths. The set $\mathcal {A}$ does not contain a path with endpoints $s_{i}'$ and $s_{j}'$ since such a path has length at least $2p^{2} + (i+j) p + 1 > \ell$. Furthermore, a path in $\mathcal {A}$ cannot connect some $s_{i}'$ and $t_{j}'$ with $i > j$ since the length of such a path is at least $2p^{2} + (i-j)p-\ell _j +1 > \ell$. Since $A = \{s_{i}' \mid i \in [r]\} \cup \{t_{i}' \mid i \in [r]\}$, we can conclude that each path P in $\mathcal {A}$ connects $s_{i}'$ and $t_{i}'$ for some i, and the subpath of P connecting $s_{i}$ and $t_{i}$ has length $2p^{2} - (p^{2} + ip) - (p^{2} - ip - \ell _{i}) = \ell _{i}$. We therefore obtain a solution to the Extended-ALPP instance.

Finally, observe that the only modifications we have done on G is to subdivide some edges and to attach paths to some vertices. By Lemma 2.1, the pathwidth is increased only by at most 2. $\square$

We can now reduce the k-MCC problem to Extended-ALPP.

Lemma 4.4

There exists a polynomial-time algorithm which, given an instance of k-MCC on a graph G with n vertices, produces an equivalent instance of Extended-ALPP on a graph $G'$, with $r \in O(k^2)$ triples, $\mathsf {pw}(G') \in O(k^2)$, and maximum edge weight $W \in n^{O(1)}$.

Proof

We are given a graph $G = (V,E)$ with V partitioned into k sets $V_{1}, \dots , V_{k}$, and are asked for a clique of size k that contains one vertex from each set. To ease notation, we will assume that n is odd and $|V_{i}|=n$ for $i \in [k]$ (so the graph has kn vertices in total) and that the vertices of $V_{i}$ are numbered $1, \dots , n$. We define two lengths $L_{1} = (k+1)(n-1)$ and $L_{2} = 60 n^{6}$.

For $i\in [k]$ we construct a vertex-selection gadget as follows (see Fig. 3): we make n paths of length k, call them $P_{i,j}$, where $j \in [n]$. Let $a_{i,j}$ and $b_{i,j}$ be the first and last vertices of path $P_{i,j}$, respectively. We label the remaining vertices of the path $P_{i,j}$ as $x_{i, j, i'}$ for $i' \in \{1, \dots , k\} {\setminus } \{i\}$ in some arbitrary order. Then for each $j \in [n-1]$ we connect $a_{i,j}$ to $a_{i,j+1}$ and $b_{i,j}$ to $b_{i,j+1}$. All edges constructed so far have weight 1. We set $s_{i} = a_{i,1}$ and $t_{i} = a_{i,n}$. We add to the instance the triple $(s_{i},t_{i},L_{1})$.

Fig. 3

An example of the vertex-selection gadget for $n=9$, $k=4$, and $i=2$

We now need to construct an edge-verification gadget as follows (see Fig. 4): for each $i_{1}, i_{2} \in [k]$ with $i_{1} < i_{2}$, we construct three vertices $s_{i_1,i_2}$, $t_{i_1,i_2}$, $p_{i_1,i_2}$. For each edge e of G between $V_{i_{1}}$ and $V_{i_{2}}$, we do the following: suppose e connects vertex $j_{1}$ of $V_{i_{1}}$ to vertex $j_{2}$ of $V_{i_{2}}$. We add the following four edges:

• 1. An edge from $s_{i_1,i_2}$ to $x_{i_1, j_1, i_2}$. This edge has weight $L_{2}/4 + j_{1} n^{4} + j_{2} n^{2}$.

• 2. An edge from $x_{i_1,j_1,i_2}$ to $p_{i_1,i_2}$. This edge has weight $L_2/4$.

• 3. An edge from $p_{i_1,i_2}$ to $x_{i_2,j_2,i_1}$. This edge has weight $L_2/4$.

• 4. An edge from $x_{i_2,j_2,i_1}$ to $t_{i_1,i_2}$. This edge has weight $L_{2}/4 - j_{1} n^{4} - j_{2} n^{2}$.

We call the edges constructed in the above step heavy edges, since their weight is close to $L_2/4$. We add the $k(k-1)/2$ triples $(s_{i_1,i_2}, t_{i_1,i_2}, L_2)$ to the instance, for all $i_1,i_2\in [k]$, with $i_1< i_2$.

Fig. 4

An example of the edge-verification gadget for $V_{i_{1}}$ and $V_{i_{2}}$ ($i_{1} < i_{2}$). In this example, there are exactly three edges between $V_{i_{1}}$ and $V_{i_{2}}$

Note that in the above description we have created some parallel edges, for example from $s_{i_1,i_2}$ to $x_{i_1,2j_1,i_2}$ (if the vertex $j_1$ of $V_{i_1}$ has several neighbors in $V_{i_2}$). This can be avoided by subdividing such edges once and assigning weights to the new edges so that the total weight stays the same. For simplicity we ignore this detail in the remainder since it does not significantly affect the pathwidth of the graph (see Lemma 2.1). This completes the construction.

Let us now prove correctness. First assume that we have a k-multicolored clique in G, encoded by a function $\sigma :[k] \rightarrow [n]$, that is, $\sigma (i)$ is the vertex of the clique that belongs in $V_i$. For the i-th vertex-selection gadget we have the triple $(s_i,t_i,L_1)$. We construct a path from $s_i$ to $t_i$ by traversing the paths $P_{i,j}$ for $j \in [n] {\setminus } \{\sigma (i)\}$ in the increasing order of j and by appropriately using the “horizontal” edges connecting adjacent paths. See Fig. 5. The path has length $L_{1}$: we have traversed $n-1$ paths $P_{i,j}$ with $j \ne \sigma (i)$, each of which has k edges; we have also traversed $n-1$ horizontal edges connecting adjacent paths. The total length is therefore, $(n-1)k + n-1 = L_{1}$. In this way we have satisfied all the k triples $(s_i,t_i,L_1)$ and have not used the vertices $x_{i,\sigma (i),i'}$ for any $i'\ne i$.

Consider now a triple $(s_{i_1,i_2}, t_{i_1,i_2},L_2)$, for $i_1<i_2$. Because we have selected a clique, there exists an edge between vertex $\sigma (i_1)$ of $V_{i_1}$ and $\sigma (i_2)$ of $V_{i_2}$. For this edge we have constructed four edges in our new instance, linking $s_{i_1,i_2}$ to $t_{i_1,i_2}$ with a total weight of $L_2$. We use these paths to satisfy the $k\atopwithdelims ()2$ triples $(s_{i_1,i_2},t_{i_1,i_2},L_2)$. These paths are disjoint from each other: when $i_1<i_2$, $x_{i_1,\sigma (i_1),i_2}$ is only used in the path from $s_{i_1,i_2}$ to $t_{i_1,i_2}$ and when $i_1>i_2$, $x_{i_1,\sigma (i_1),i_2}$ is only used in the path from $s_{i_2,i_1}$ to $t_{i_2,i_1}$. Furthermore, these paths are disjoint from the paths in the vertex-selection gadgets, as we observed that $x_{i,\sigma (i),i'}$ are not used by the path connecting $s_i$ to $t_i$. We thus have a valid solution. See Fig. 5.

Fig. 5

Construction of paths from $\sigma$

For the converse direction, suppose we have a valid solution for the Extended-ALPP instance. First, consider the path connecting $s_i$ to $t_i$. This path has length $L_1$, therefore it cannot be using any heavy edges, since these edges have cost at least $L_2/4-n^{5}-n^{3}>L_{1}$. Inside the vertex-selection gadget, the path may use either all of the edges of a path $P_{i,j}$ or none. Let us now see how many $P_{i,j}$ are unused. First, a simple parity argument shows that the number of paths traversed in the $a_{i,j}\rightarrow b_{i,j}$ direction is equal to those traversed in the opposite direction, so the total number of used paths is even. Since we have an odd number of paths in total (as n is odd), at least one path is not used. We conclude that exactly one $P_{i,j}$ is not used, otherwise the path from $s_i$ to $t_i$ would be too short. Let $\sigma (i)$ be defined as the index j such that the internal vertices of $P_{i,j}$ are not used in the $s_i\rightarrow t_i$ path of the solution. We define a clique in G by selecting for each i the vertex $\sigma (i)$.

Let us argue why this set induces a clique. Let $j_1,j_2$ be the vertices selected in $V_{i_1},V_{i_2}$ respectively, with $i_1<i_2$, and consider the triple $(s_{i_1,i_2},t_{i_1,i_2},L_2)$. This triple must be satisfied by a path that uses exactly four heavy edges, since each heavy edge has weight at least $L_{2}/5 + n^{6}$ and at most $L_{2}/3 - 3n^{6}$, and all other edges together have weight smaller than $n^{3}$. Hence, every such path is using at least two internal vertices of some $P_{i,j}$ because every heavy edge is incident on such a vertex. By our previous reasoning, the paths that satisfy the $(s_i,t_i,L_1)$ triples have used all such vertices except for one path $P_{i,j}$ for each i. There exist therefore exactly $k(k-1)$ such vertices available, so each of the $k(k-1)/2$ triples $(s_{i_1,i_2}, t_{i_1,i_2}, L_2)$ has a path using exactly two of these vertices. Hence, each such path consists of four heavy edges and no other edges.

Such a path must therefore be using one edge incident on $s_{i_1,i_2}$, one edge incident on $t_{i_1,i_2}$ and two edges incident on $p_{i_1,i_2}$. The used edge incident on $s_{i_1,i_2}$ must have as other endpoint $x_{i_1,2j_1,i_2}$, which implies that its weight is $L_2/4+j_{1}n^{4}+j_{2}'n^{2}$, for some $j_2'$. Similarly, the edge incident on $t_{i_1,i_2}$ must have weight $L_2/4-j_{1}'n^{4}-j_{2}n^{2}$, as its other endpoint is necessarily $x_{i_2,2j_2,i_1}$. We conclude that the only way that the length of this path is $L_2$ is if $j_1=j_1'$ and $j_2=j_2'$. Therefore, we have an edge between the two selected vertices, and as a result a k-clique.

To conclude we observe that deleting the $3 \cdot \left( {\begin{array}{c}k\\ 2\end{array}}\right)$ vertices $s_{i_1,i_2}$, $p_{i_1,i_2}$, $t_{i_1,i_2}$ disconnects the graph into components that correspond to the vertex gadgets with some paths attached. By Lemma 2.1, each such component has pathwidth at most 4 as it can be seen as a graph obtained from a subdivision of the $2 \times n$ grid by attaching paths to some vertices. As a result the whole graph has pathwidth $3 \cdot \left( {\begin{array}{c}k\\ 2\end{array}}\right) + 4$. $\square$

Theorem 4.5

Full-ALPP is W[1]-hard parameterized by $\mathsf {pw}+|A|$.

Proof

We compose the reductions of Lemmas 4.3 and 4.4. Starting with an instance of k-MCC with n vertices this gives an instance of Full-ALPP with $n^{O(1)}$ vertices, $|A|=O(k^2)$, and pathwidth $O(k^2)$. $\square$

5 Hardness on Grid Graphs

In this section, we show that for every constant $\ell \ge 4$, Full-ALPP is NP-complete on grid graphs. We first reduce Planar Circuit SAT to Full-ALPP on planar bipartite graphs of maximum degree at most 4. We then modify the instance by subdividing edges and adding terminal vertices in an appropriate way, and have an equivalent instance on grid graphs.

The input of Circuit SAT is a Boolean circuit with a number of inputs and one output. The question is whether the circuit can output true by appropriately setting its inputs. Circuit SAT is NP-complete since CNF SAT [9] can be seen as a special case. When the underlying graph of the circuit is planar, the problem is called Planar Circuit SAT. Using planar crossover gadgets [27], we can show that Planar Circuit SAT is NP-complete. Furthermore, since NOR gates can replace other gates such as AND, OR, NOT, NAND, and XOR without introducing any new crossing, we can conclude that Planar Circuit SAT having NOR gates only is NP-complete.

Let $I = (G, A, \ell )$ be an instance of Full-ALPP with $G = (V,E)$. Let $\psi$ be a mapping that assigns each $e \in E$ an $(A,\ell )$-path in G, and $\psi (E) = \{\psi (e) \mid e \in E\}$. We say that $\psi$ is a guide to I if every set of |A|/2 vertex-disjoint $(A,\ell )$-paths, if any exists, is a subset of $\psi (E)$. When a guide is given additionally to an instance of Full-ALPP, we call the problem Guided Full-ALPP. Observe that a guide to an instance is not a restriction but just additional information.

Lemma 5.1

For every fixed $\ell \ge 4$, Guided Full-ALPP is NP-complete on planar bipartite graphs of maximum degree at most 4.

Proof

Given a planar circuit with only NOR gates, we construct an equivalent instance of Guided Full-ALPP with the fixed $\ell$. We only need input gadget, output gadget, split gadget, NOR gadget, and a way to connect the gadgets. See Fig. 6 for the high-level idea of the reduction.

Fig. 6

A planar circuit and the corresponding ALPP instance (simplified). The vertices in $V {\setminus } A$ are omitted. The connection pairs are marked with dashed rectangles

The general ideas of our gadgets are as follows. The key ingredient is a cycle of length $2p\ell$ for some p in which every $\ell$th vertex belongs to A. We call such a cycle a basic cycle. There are exactly two ways to pack p vertex-disjoint $(A,\ell )$-paths into a basic cycle of length $2p\ell$, and each of the packings corresponds to the true or false signal passing through the corresponding part of the circuit. Our gadgets mostly consist of basic cycles and they intersect in such a way that an $(A,\ell )$-path using an edge in a basic cycle cannot use any edge in another basic cycle. This can be guaranteed if two basic cycles intersect at a vertex whose distances from A in the two basic cycles are of different parities. In this way, the choice for one basic cycle propagates to other basic cycles. The NOR gadgets are little more complicated as they involve self-intersecting cycles, but the general idea is the same.

We explicitly present the gadgets for the cases $\ell = 4$ and $\ell = 5$. For even (resp. odd) $\ell > 5$, the gadgets can be obtained from the one for $\ell = 4$ (resp. $\ell = 5$) by subdividing $\lfloor \ell /2 \rfloor - 2$ times each edge incident to a vertex in A.

Connections between gadgets We first explain how the gadgets are connected. Each gadget has one or three pairs of vertices that are shared with other gadgets. We call them connection pairs. All those vertices belong to the terminal set A. In the figures, we draw each connection pair so that the two vertices are next to each other vertically and mark them with a dashed rectangle. If the $(A,\ell )$-paths using the vertices of a connection pair are going to the positive direction, then we interpret it as that a true signal is sent via the connection pair. If the paths are going to the negative direction, then the connection pair is carrying a false signal. (See Fig. 7.) Note that our reduction below forces the paths at each connection pair to proceed in the same direction.

Fig. 7

$(A,\ell )$-paths at a connection pair. We draw an $(A,\ell )$-path as a gray bar

Fig. 8

The input gadgets. The black vertices belong to A and the white vertices belong to $V {\setminus } A$

Input gadgets The input gadget is simply a path of length $3\ell$, where the endpoints form its unique connection pair. See Fig. 8. For a full $(A,\ell )$-path packing, we only have two options. One corresponds to true input (Fig. 8c) and the other to false input (Fig. 8d).

Output gadgets The output gadget consists of two paths of length $\ell$, where its unique connection pair includes one endpoint from each path. See Fig. 9. To have a full packing, the input to this gadget has to be true.

Fig. 9

The output gadgets

Split gadgets To simulate the split of a wire depicted in Fig. 10, the split gadget consists of three paths of length $3\ell$, each of which is identical to the input gadget, and a cycle of length $10\ell$ that synchronizes the three paths. See Fig. 11. To have a full $(A,\ell )$-path packing, there are only two ways to pack $(A,\ell )$-paths into a split gadget. Figure 12 shows the two ways: one on the left corresponds to a split of a true signal, and the other a split of a false signal.

Fig. 10

Splitting a wire in a circuit

Fig. 11

The split gadgets

Fig. 12

The possible $(A,\ell )$-path packings of the split gadget

NOR gadgets Recall that NOR stands for “NOT OR” and that the output y of a NOR gate is true if and only if both inputs $x_{1}$ and $x_{2}$ are false. The NOR gadgets are given in Fig. 13. The structure of the gadget is rather involved. It has three connection pairs, two for the inputs and one for the output, and the endpoints of each pair are connected by a path of length $5\ell$. Additionally, there is a long self-intersecting cycle that somehow entangles the inputs and the output. There are only four ways to fully pack $(A,\ell )$-paths into a NOR gadget, and each packing corresponds to a correct behavior of a NOR gate (see Fig. 14). To see the correctness of Fig. 14, it is important to observe that in the NOR gadgets for even $\ell$, there are some $(A,\ell )$-paths that are never used in a full $(A,\ell )$-path packing. For example, the $(A,\ell )$-path with endpoints $v_{1}$ and $v_{2}$ in Fig. 13a is such a path. In a full $(A,\ell )$-path packing, $w_{2}$ has to be an endpoint of an $(A,\ell )$-path either with $w_{1}$ or $w_{3}$. Hence, if we use the $(A,\ell )$-path with endpoints $v_{1}$ and $v_{2}$, then one of $u_{1}$ and $u_{2}$ cannot belong to any $(A,\ell )$-path in the packing.

Fig. 13

The NOR gadgets

Fig. 14

The possible $(A,\ell )$-path packings of the NOR gadget

Guides The guide $\psi (e)$ for each $e \in E$ can be easily set from Figs. 8c, d, 9c, 12a, b, 14a–d. For each edge e, the unique gray bar that includes the edge represents the $(A,\ell )$-path $\psi (e)$.

Correctness The correctness of each gadget implies the correctness of the whole reduction. Thus, it suffices to show that the output of the reduction is planar bipartite graph of maximum degree at most 4. The resultant graph clearly has maximum degree 4 and is planar. To see that the graph is bipartite, consider a 2-coloring of a gadget, which is not the output gadget. If $\ell$ is even, then all vertices in the connection pairs have the same color. If $\ell$ is odd, then each upper vertex of a connection pair in the figures has the same color, and the other vertices in the connection pairs have the other color. Therefore, the entire graph is 2-colorable. $\square$

Let $(G,A,\ell ,\psi )$ be an instance of Guided Full-ALPP with $G = (V,E)$. For $e = \{v,w\} \in E$, we denote by $d_{e}$ the length of the subpath of $\psi (e)$ starting at v, passing w, and reaching an endpoint of $\psi (e)$. Let $G_{e}$ be the graph obtained from G by subdividing e, $2\ell$ times. Let $P_{e}$ be the v-w path of length $2\ell +1$ in $G_{e}$ corresponding to e. We set $A_{e} = A \cup \{x_{0}, x_{1}\}$, where $x_{0}$ and $x_{1}$ are the vertices that have distance $d_{e}$ and $d_{e} + \ell$ from v in $P_{e}$, respectively. (See Fig. 15.)

Fig. 15

Subdividing e and introducing two new terminals ($\ell = 4$)

For each edge h of $G_{e}$, we set $\psi _{e}(h) = \psi (h)$ if h is not contained in the path $P_{\psi (e)}$ of length $3\ell$ that corresponds to $\psi (e)$. If h is contained in $P_{\psi (e)}$, then we set $\psi _{e}(h)$ to the unique $(A,\ell )$-path in $P_{\psi (e)}$ that contains h. Observe that $\psi _{e}$ is a guide to $(G_{e}, A_{e}, \ell )$. Furthermore, $(G,A,\ell ,\psi )$ and $(G_{e},A_{e},\ell , \psi _{e})$ are equivalent (see Fig. 16): if $\psi (e)$ is used in a full $(A,\ell )$-path packing of G, then we use two $(A,\ell )$-paths in $P_{\psi (e)}$; otherwise we use the middle $(A,\ell )$-path in $P_{\psi (e)}$ connecting two new terminals.

Observation 5.2

$(G,A,\ell ,\psi )$ and $(G_{e},A_{e},\ell , \psi _{e})$ are equivalent instances of Guided Full-ALPP.

Fig. 16

Equivalence of $(G,A,\ell ,\psi )$ and $(G_{e},A_{e},\ell , \psi _{e})$

Now we are ready to prove the main theorem of this section.

Theorem 5.3

For every constant $\ell \ge 4$, Full-ALPP is NP-complete on grid graphs.

Proof

We reduce Guided Full-ALPP on planar bipartite graphs of maximum degree at most 4 for fixed $\ell \ge 4$ (which is NP-complete by Lemma 5.1) to Full-ALPP on grid graphs for the same $\ell$. Let $(G,A,\ell ,\psi )$ be an instance of Guided Full-ALPP, where $G = (V,E)$ is a planar bipartite graph of maximum degree at most 4.

A rectilinear embedding of a graph is a planar embedding into the $\mathbb {Z}^{2}$ grid such that

• each vertex is mapped to a grid point;

• each edge $\{u,v\}$ is mapped to a rectilinear path between u and v consisting of vertical and horizontal segments connecting grid points;

• the rectilinear paths corresponding to two different edges may intersect only at their endpoints.

Every planar graph of maximum degree at most 4 has a rectilinear embedding, and a rectilinear embedding of area at most $(n+1)^{2}$ can be computed in linear time [25], where n is the number of vertices.

Let $R_{1}$ be a rectilinear embedding of G with area at most $(n+1)^{2}$. By multiplying each coordinate in the embedding by $2\ell$, we obtain an enlarged rectilinear embedding $R_{2}$ of G. Let U be one color class of a 2-coloring of G. Now, for each $v \in U$, we locally modify $R_{2}$ around the grid point $(x_{v}, y_{v})$ corresponding to v as illustrated in Fig. 17. We denote by $R_{3}$ the locally modified embedding.

Fig. 17

Local modification around v. The grid point of v is moved to $(x_{v} + 1, y_{v})$

From $R_{3}$, we construct a new graph $G'$ and its rectilinear embedding $R'$ by inserting degree-2 vertices at each intersection point of a grid point and the inner part of a rectilinear path corresponding to an edge. Clearly, $G'$ is a grid graph. Let $e \in E$ and $\lambda _{e}$ be the (geometric) length of the rectilinear path in $R_{1}$ corresponding to e. Then the rectilinear path in $R_{3}$ corresponding to e has length $2 \ell \cdot \lambda _{e} + 1$. Therefore, $G'$ is the graph obtained from G by subdividing each edge e, $2 \ell \cdot \lambda _{e}$ times. By Observation 5.2, we can easily compute $A'$ and $\psi '$ such that $(G,A,\ell ,\psi )$ is equivalent to $(G',A',\ell ,\psi ')$. Finally, from the definition of a guide to an instance of Full-ALPP, $(G',A',\ell ,\psi ')$ is equivalent to $(G',A',\ell )$. As everything in this reduction can be done in time polynomial, the theorem holds. $\square$

6 Short A-Paths

As mentioned before, the positive results on ALPP presented so far can be translated to the ones on SAPP by the following lemma.

Lemma 6.1

Given an instance $(G,A,k,\ell )$ of SAPP where G has n vertices and m edges, one can compute an equivalent instance $(G',A,k,\ell )$ of ALPP in $O(m n^{2})$ time, where $G'$ has $O(m n^{2})$ vertices and edges, and $\mathsf {tw}(G') \le \mathsf {tw}(G) + 1$.

Proof

We construct $G' = (V',E')$ from $G = (V,E)$ by replacing each edge $\{u,v\} \in E$ with $\ell$ new u–v paths of lengths $1, 2, \dots , \ell$. (See Fig. 18.) We call these paths (including the one of length 1) the detours of $\{u,v\}$. Clearly, $|V'|, |E'| \in O(m n^{2})$, and $G'$ can be constructed in time linear in $|V'| + |E'|$.

Fig. 18

The construction of $G'$ (right) from G (left) when $\ell = 3$

To bound the treewidth of $G'$, observe that $G'$ can be seen as a graph obtained from G by attaching triangles to edges, and then by subdividing some edges. Such operations preserve the treewidth unless G is a forest. (If G is a forest, then the treewidth increases by 1.) To see this, let $\{u,v\}$ be the target edge of one of such operations. Let w be the new vertex introduced by the operation. Every tree decomposition $\mathcal {T}$ of the original graph has a bag B including both u and v since $\{u,v\}$ is an edge of the original graph. We add to $\mathcal {T}$ a new bag $B' = \{u,v,w\}$ adjacent only to B. Clearly, the obtained decomposition is a tree decomposition of the graph obtained by the operation, and its width is the maximum of $|B'|-1$ and the width of $\mathcal {T}$.

Now assume that $(G,A,k,\ell )$ is a yes instance of SAPP, and let $P_{1}, \dots , P_{k}$ be vertex-disjoint $A_{\le \ell }$-paths in G. For each $i \in [k]$, let $\ell _{i}$ be the length of $P_{i}$. We construct an $(A,\ell )$-path $P_{i}'$ in G from $P_{i}$ by replacing an arbitrary edge $\{u,v\}$ in $P_{i}$ with its detour of length $\ell - \ell _{i} + 1$. Since $P_{1}, \dots , P_{k}$ are vertex-disjoint and the detours are internally vertex-disjoint, the $(A,\ell )$-paths $P_{1}', \dots , P_{k}'$ are vertex-disjoint.

Conversely, assume that $(G',A,k,\ell )$ is a yes instance of ALPP, and let $P_{1}', \dots , P_{k}'$ be vertex-disjoint $(A,\ell )$-paths in $G'$. Note that each $P_{i}'$ is a concatenation of some detours. We obtain an $A_{\le \ell }$-path $P_{i}$ in G by replacing all detours in $P_{i}'$ with the original edges in G. Since $P_{1}', \dots , P_{k}'$ are vertex-disjoint and $V(P_{i}) \subseteq V(P_{i}')$ for each $i \in [k]$, the $A_{\le \ell }$-paths $P_{1}, \dots , P_{k}$ are vertex-disjoint. $\square$

By Lemma 6.1, Theorems 3.3 and 3.5, Observations 4.1 and 4.2 imply the following positive results on SAPP.

Corollary 6.2

If $\ell \le 3$, then SAPP can be solved in polynomial time.

Corollary 6.3

SAPP parameterized by $k + \ell$ is fixed-parameter tractable.

Corollary 6.4

SAPP can be solved in time $n^{O(\mathsf {tw})}$.

Corollary 6.5

SAPP parameterized by $\mathsf {tw}+ \ell$ is fixed-parameter tractable.

On the other hand, the negative results on ALPP cannot be directly translated to the one on SAPP. We here prove the hardness of the cases with constant $|A| \ge 4$ or with constant $\ell \ge 4$. Note that SAPP with $k=1$ (or $|A| = 2$) is polynomial-time solvable because it reduces to the all-pairs shortest path problem. We leave the complexity of SAPP parameterized by $\mathsf {tw}$ unsettled.

Theorem 6.6

For every even constant $\alpha \ge 4$, Full-SAPP with $|A| = \alpha$ is NP-complete.

Proof

Since the problem is clearly in NP, we present a reduction from the following NP-complete problem 2D1SP [13]. Given a graph $G = (V,E)$ and two terminal pairs $(s_{1},t_{1})$ and $(s_{2},t_{2})$, the problem 2D1SP asks whether there exist two vertex-disjoint paths $P_{1}$ from $s_{1}$ to $t_{1}$ and $P_{2}$ from $s_{2}$ to $t_{2}$, where $P_{1}$ is asked to be a shortest $s_{1}$–$t_{1}$ path in G. We reduce 2D1SP to Full-SAPP with $|A| = 4$. (We can extend this to any even $\alpha = |A|$ by adding dummy components.)

Let $n = |V|$ and $\ell = 5n-1$. Let $\ell _{1}$ be the shortest path distance between $s_{1}$ and $t_{1}$ in G. We add four vertices $s_{1}'$, $t_{1}'$, $s_{2}'$, and $t_{2}'$ to G. We add a path of length 3n between $s_{1}$ and $s_{1}'$, a path of length $2n-\ell _{1}-1$ between $t_{1}$ and $t_{1}'$, a path of length 2n between $s_{2}$ and $s_{2}'$, and a path of length 2n between $t_{2}$ and $t_{2}'$. We call the obtained graph $G'$ and set $A = \{s_{1}', t_{1}', s_{2}', t_{2}'\}$.

Assume that G has a shortest $s_{1}$–$t_{1}$ path $P_{1}$ and a (not necessarily shortest) $s_{2}$–$t_{2}$ path $P_{2}$ vertex-disjoint from $P_{1}$. For each $i \in \{1,2\}$, we extend $P_{i}$ to a path $P_{i}'$ between $s_{i}'$ and $t_{i}'$ by adding the unique paths between $s_{i}'$ to $s_{i}$ an $t_{i}$ to $t_{i}'$. The length of $P_{1}'$ is $3n + \ell _{1} + (2n-\ell _{1}-1) = \ell$ and the length of $P_{2}'$ is $2n + \Vert P_{2}\Vert + 2n \le \ell$, where $\Vert P_{2}\Vert$ is the length of $P_{2}$.

Conversely, assume that $G'$ has two vertex-disjoint $A_{\le \ell }$-paths $P_{1}'$ and $P_{2}'$. Without loss of generality, we can assume that one of the endpoints of $P_{1}'$ is $s_{1}'$. Then we can see that the other endpoint of $P_{1}'$ is $t_{1}'$ since the distance between $s_{1}'$ and the vertices $s_{2}'$ and $t_{2}'$ is at least $3n + 2n > \ell$. Let $P_{1}$ be the subpath of $P_{1}'$ that connects $s_{1}$ and $t_{1}$. Now the length of the $A_{\le \ell }$-path $P_{1}'$ is $3n + \Vert P_{1}\Vert + (2n-\ell _{1}-1) \le \ell$, and thus $\Vert P_{1}\Vert \le \ell _{1}$. Hence $P_{1}$ is a shortest path between $s_{1}$ and $t_{1}$ in G. Let $P_{2}$ be the subpath of $P_{2}'$ that connects $s_{2}$ and $t_{2}$. Since $P_{1}'$ and $P_{2}'$ are vertex-disjoint, so are $P_{1}$ and $P_{2}$. $\square$

Theorem 6.7

For every constant $\ell \ge 4$, Full-SAPP is NP-complete.

Proof

We show the NP-hardness of Full-SAPP with constant $\ell \ge 4$ by a reduction from a variant of 3-Sat with the following restrictions: (1) each clause is a disjunction of two or three literals, and (2) each variable occurs exactly twice as a positive literal and exactly once as a negative literal. We call this variant 3-Sat($2, 1$). It is known that 3-Sat($2, 1$) is NP-complete [16].

Let $(U, \mathcal {C})$ be an instance of 3-Sat($2, 1$) with the variables $U = \{u_{1}, \dots , u_{n}\}$ and the clauses $\mathcal {C} = \{C_{1}, \dots , C_{m}\}$. If the positive literal of $u_{i}$ appears in $C_{p}$ and $C_{q}$ with $p < q$, then we say that the first occurrence of $u_{i}$ is in $C_{p}$ and the second is in $C_{q}$.

For each $i \in [n]$, we construct the variable gadget for $u_{i}$ as follows (see Fig. 19 (left)). Take three paths of length $\ell$ from $s_{i}^{1}$ to $t_{i}^{1}$, from $s_{i}^{2}$ to $t_{i}^{2}$, and from $\overline{s}_{i}$ to $\overline{t}_{i}$. We call these paths vertical. Add three paths of length $\ell -1$ from $s_{i}^{1}$ to the neighbor of $\overline{t}_{1}$, from $s_{i}^{2}$ to the neighbor of $t_{i}^{1}$, and from $\overline{s}_{i}$ to the neighbor of $t_{i}^{2}$. Now these paths together with the edges incident to $t_{i}^{1}$, $t_{i}^{2}$, and $\overline{t}_{i}$ form three paths of length $\ell$ from $s_{i}^{1}$ to $\overline{t}_{1}$, from $s_{i}^{2}$ to $t_{i}^{1}$, and from $\overline{s}_{i}$ to $t_{i}^{2}$. We call these paths slanted. For $j \in \{1,2\}$, we call the vertex of distance 2 from $t_{i}^{j}$ on the corresponding vertical path $x_{i}^{j}$. We call the vertex of distance 2 from $\overline{t}_{i}$ on the corresponding slanted path $\overline{x}_{i}$.

For each $C \in \mathcal {C}$, we construct the clause gadget for C as follows (see Fig. 19 (right)). Assume that C includes c literals. Take two vertices $s_{C}$ and $t_{C}$ and then add c internally disjoint paths of length $\ell$ between $s_{C}$ and $t_{C}$. We bijectively map the neighbors of $t_{C}$ to the literals in C. For each neighbor v of $t_{C}$, if v is mapped to the jth positive occurrence of $u_{i}$, then we identify v with $x_{i}^{j}$ in the variable gadget for $u_{i}$. Similarly, if v is mapped to the negative occurrence of $u_{i}$, then we identify v with $\overline{x}_{i}$.

We call the constructed graph G and set $A = \{s_{i}^{1}, s_{i}^{2}, \overline{s}_{i}, t_{i}^{1}, t_{i}^{2}, \overline{t}_{i} \mid i \in [n]\} \cup \{s_{C}, t_{C} \mid C \in \mathcal {C}\}$. This completes the construction. We show that $(U, \mathcal {C})$ is a yes instance of 3-Sat($2, 1$) if and only if $(G,A,|A|/2, \ell )$ is a yes instance of Full-SAPP.

Fig. 19

The variable gadget (left) and the clause gadget (right)

To show the only-if direction, assume that there is a truth assignment to the variables in U that satisfies $\mathcal {C}$. For each variable $u_{i} \in U$, if $u_{i}$ is set to be true, then we take the slanted paths in the variable gadget for $u_{i}$; otherwise, we take the vertical paths. Since the variable gadgets are vertex-disjoint, the paths taken so far are vertex-disjoint. Then for each clause $C \in \mathcal {C}$, let l be a literal in C that set to be true. Observe that the neighbor, say $v_{l}$, of $t_{C}$ mapped to l is not used in the paths selected in the variable gadgets. Thus we can take the $s_{C}$–$t_{C}$ path passing through $v_{l}$. Since all paths selected have length $\ell$ and all vertices in A are used as endpoints of the selected path, $(G,A,|A|/2, \ell )$ is a yes instance of Full-SAPP.

To prove the if direction, assume that there is a set of |A|/2 vertex-disjoint $A_{\ell }$-paths $\mathcal {P}$ in G. First observe that for each $C \in \mathcal {C}$, $t_{C}$ is the only vertex distance at most $\ell$ from $s_{C}$: for each neighbor v of $t_{C}$, the distance from $s_{C}$ to v is $\ell - 1$, and the distance from v to any vertex in $A {\setminus } \{s_{C}, t_{C}\}$ is at least $\min \{2,\ell -2\} \ge 2$. Thus, for each $C \in \mathcal {C}$, there is a path in $\mathcal {P}$ that has $s_{C}$ and $t_{C}$ as its endpoints. Next we claim that for each variable $u_{i} \in U$, either all vertical paths or all slanted paths in the variable gadget for $u_{i}$ are selected into $\mathcal {P}$. To see this, observe that $\{\overline{t}_{i}, t_{i}^{1}\}$ (resp. $\{t_{i}^{1}, t_{i}^{2}\}$, $\{t_{i}^{2}, \overline{t}_{i}\}$) is the set of vertices in $A {\setminus } \{s_{C}, t_{C} \mid C \in \mathcal {C}\}$ that are distance at most $\ell$ from $s_{i}^{1}$ (resp. $s_{i}^{2}$, $\overline{s}_{i}$). Therefore, if we pick a vertical (resp. slanted) path in a variable gadget, then we have to take all vertical (resp. slanted) paths in that variable gadget. We now construct a truth assignment to U by setting $u_{i}$ true if and only if $\mathcal {P}$ includes the slanted paths in the variable gadget for $u_{i}$. For $C \in \mathcal {C}$, let $P \in \mathcal {P}$ be the path connecting $s_{C}$ and $t_{C}$. Let l be the literal in C corresponding to the neighbor of $t_{C}$ on P. If l is a positive literal of a variable $u_{i}$, then $\mathcal {P}$ includes the slanted paths in the variable gadget for $u_{i}$, and thus $u_{i}$ is set to be true. If l is a negative literal of $u_{i}$, then $\mathcal {P}$ includes the vertical paths in the variable gadget for $u_{i}$, and thus $u_{i}$ is set to be false. In both cases, l is true and C is satisfied. $\square$

7 Concluding Remarks

In this paper, we have introduced a new problem $(A,\ell )$ -Path Packing (ALPP) and showed tight complexity results. One possible future direction would be the parameterization by clique-width $\mathsf {cw}$, a generalization of treewidth (see [19]). In particular, we ask the following two questions.

• Does ALPP admit an algorithm of running time $O(n^{\mathsf {cw}})$?

• Is ALPP fixed-parameter tractable parameterized by $\mathsf {cw}+ \ell$?

We also considered a variant of the problem which we call $A_{\le \ell }$ -Path Packing (SAPP). We showed that results similar to the ones on ALPP hold also on SAPP, but we were not able to determine the complexity parameterized by treewidth. We left the following question on SAPP.

• Is SAPP W[1]-hard parameterized by $\mathsf {tw}$, $\mathsf {tw}+ k$, or $\mathsf {tw}+ |A|$?

Another interesting direction on ALPP (and on SAPP) would be a systematic study on restricted graph classes. A special case of ALPP have been studied on important graph classes as the 2-fixed-endpoint Hamiltonian path problem (2HP), where we are given two vertices s and t and asked whether there is a Hamiltonian path from s to t. Clearly, 2HP is equivalent to ALPP with $A = \{s,t\}$ and $\ell = n-1$. The complexity of 2HP on interval graphs was asked in 1993 [12] and is still open (see [24]). It is known that 2HP is polynomial-time solvable on proper interval graphs [3]. It is natural to expect that with its full generality, ALPP would be intractable on those graph classes.

A Proof of Lemma 2.1

In this section, we prove Lemma 2.1 stating that: if $G'$ is a graph obtained from a graph $G = (V,E)$ by subdividing a set of edges $F \subseteq E$ an arbitrary number of times, and attaching a path of arbitrary length to each vertex in a set $U \subseteq V$, then $\mathsf {pw}(G') \le \mathsf {pw}(G) + 2$.

To this end, we use a characterization of pathwidth in terms of the following search game. We are given a graph $G = (V,E)$ with all edges contaminated. The goal in this game is to clear all edges. In each turn, we can place a searcher on a vertex or remove a searcher from a vertex. An edge is cleared by having searchers on both endpoints. A cleared edge is immediately recontaminated when a removal of a searcher results in a path not passing through any searchers from the edge to a contaminated edge. The minimum number of searchers needed to clear all edges of G is the node search number, and we denote it by $\mathsf {ns}(G)$. It is known that $\mathsf {ns}(G) = \mathsf {pw}(G)+1$ for every graph G [5, 14, 22].

Lemma A.1

(Folklore) Let $G = (V,E)$ be a graph. If $G'$ is a graph obtained from G by subdividing a set of edges $F \subseteq E$ an arbitrary number of times, then $\mathsf {pw}(G') \le \mathsf {pw}(G) + 2$.

Proof

Let $p = \mathsf {pw}(G) + 1$. Since $\mathsf {ns}(G) \le p$, there is a sequence S of placements and deletions of searchers to clear all edges of G using at most p searchers. To clear all edges of $G'$, we extend S as follows. For each placement of a searcher on a vertex $v \in V$, we insert, right after this placement, a subsequence that clears all paths corresponding to the edges between v and its neighbors having searchers on them at this point. This can be done with two extra searchers that clear the paths one-by-one. The extra searchers are deleted in the end of the subsequence, and thus we only need two extra searchers in total. This implies that $\mathsf {pw}(G') = \mathsf {ns}(G')-1 \le \mathsf {ns}(G)+1 = \mathsf {pw}(G) + 2$. $\square$

Lemma A.2

(Folklore) If $G'$ is a graph obtained from a graph $G = (V,E)$ by attaching a path of arbitrary length to each vertex in a set $U \subseteq V$, then $\mathsf {pw}(G') \le \mathsf {pw}(G) + 1$.

Proof

We assume that $E \ne \emptyset$ since otherwise the statement is clearly true. There is a sequence S of placements and deletions of searchers to clear all edges of G using at most $p = \mathsf {pw}(G) + 1$ searchers. To clear all edges of $G'$, we extend S as follows. Using two searchers, we first clear the paths attached to the isolated vertices in U (if such exist). We then replace each placement of a searcher on a non-isolated vertex $u \in U$ with a subsequence that clears the path $P = (u,p_{1},p_{2},\dots ,p_{q})$ attached to u. This can be done with two searchers by first placing a searcher on $p_{q}$, then placing a searcher on $p_{q-1}$, deleting a searcher on $p_{q}$, placing a searcher on $p_{q-2}$, and so on. At the end of the subsequence, u has a searcher on it and all other vertices in P do not have searchers. We need only one extra searcher in total. Hence, $\mathsf {pw}(G') = \mathsf {ns}(G')-1 \le \mathsf {ns}(G) = \mathsf {pw}(G) + 1$. $\square$

In the proofs of Lemmas A.1 and A.2, we show that search sequences for the original graph can be “locally” extended for the new graph by using one or two temporal searchers. Thus we obtain Lemma 2.1 as the combined version of the lemmas.