Parameterized Complexity of Directed Traveling Salesman Problem

We initiate the systematic study of the parameterized complexity of DTSP and its generalizations focusing on structural parameters. In particular, we concentrate on parameters measuring the structure of the underlying undirected graph of the input. We aim to fill the apparent gap in knowledge and address the lack of fpt-algorithms.

First, we revisit the standard parameterization, i.e., the parameterization by the solution size. The budget bounds the number of edges in the solution, hence also the number of vertices visited, and in particular the size of $W$ (for any yes-instance of DTSP and DsTSP) Thus for these problems, the known single exponential algorithms [9, 36] and subexponential algorithm for planar graphs [47] show that the problem is FPT w.r.t. the budget $b$. For DWRP the situation is not as straightforward. Nevertheless, we show the following result.¹¹1Proofs of statements marked with ($\star$) can be found in the full version.

Next we turn to the structural parameters (see Figure 1 for an overview). The result of Marx et al. [48] shows that DTSP is already W[1]-hard w.r.t. distance to graphs of pathwidth $3$, i.e., for graphs with rather restricted structure. In fact, as we show in the full version, this holds also for unweighted graphs. Therefore, in search for fpt-algorithms for the problems, the structure of the graph after removal of parameter many vertices or edges should be more restricted than having pathwidth $3$. Our first positive result is w.r.t. the feedback edge number, i.e., the minimum number of edges that needs to be removed to obtain a forest.

Then, we present our main algorithmic result, showing that DWRP is FPT w.r.t. vertex integrity. Recall that vertex integrity allows, roughly speaking, to delete parameter many vertices so as to obtain a graph with connected components of parameter size.

The algorithm first guesses a part of the solution ensuring its connectivity and then employs a well structured ILP ($N$-fold IP [41]) to find the cheapest way to complete the initial guess into a solution.

We also show that, while the problems are probably not FPT w.r.t. treewidth alone, they are FPT w.r.t. treewidth combined with the bound on the number of visits to every city.

This means that all considered problems are in XP w.r.t. treewidth and, hence, w.r.t. all structural parameters considered in this paper.

We complement the positive results by showing that DWRP is W[1]-hard w.r.t. distance to constant treedepth, i.e., if the input graph becomes of constant treedepth after deleting parameter many vertices.

Note that this result is incomparable to that of Marx et al. [48] in that it holds for a more restricted graph class, while it only applies to a more general problem.

Another popular formulation of (Directed) TSP is that the input graph is complete and, thus, we are given a matrix of weights for all ordered pairs of vertices. Since this matrix is asymmetric for the case of directed graphs, the directed variant of TSP is often called Asymmetric TSP (ATSP). It is easy to switch from graph $G$ to a complete graph on the same set of vertices by performing the so called metric closure, i.e., assigning the edge $(u,v)$ of the complete graph the weight given by distance from vertex $u$ to vertex $v$ in the graph $G$. The weights obtained this way satisfy triangle inequality. Whenever this is the case, there is no reason to revisit any vertex, as it cannot make the tour shorter. However, if the matrix is not required to satisfy the triangle inequality, it makes a difference whether visiting a vertex more than once is allowed or not (single visit version).

For the single visit version with general matrices a folklore result shows that it cannot be approximated within any polynomial factor, unless P=NP [20]. For undirected case with triangle inequality it was know that there is $\frac{3}{2}$-approximation since 1976 [18], which was later improved [33, 49, 50] up to the currently best known factor $1.4$ [52] for the graphic case, where the weights originate from the distances in an unweighted graph. However, for the directed case, it was long open, whether a constant factor approximation exists for matrices satisfying the triangle inequality [4, 6]. Constant-factor approximation algorithms appeared only recently, first for unweighted directed graphs [54], later for general distances [55], with the currently best approximation factor being $22+\epsilon$ for any $\epsilon >0$ [56]. The best known lower bound on the approximability is $\frac{75}{74}$ [39].

It is surprising, given the lack of parameterized analysis for the problem, that there are several studies concerning parameterized approximation algorithm for DTSP. First, Böckenhauer [15] considered (undirected) TSP with deadlines on the latest time to visit some of the vertices and showed a $2.5$-approximation algorithm in $k!\cdot n^{O(1)}$ time, where $k$ is the number of deadlines, and complemented that by several innaproximability results. The main result of the already mentioned paper of Marx et al. [48] is a polynomial-time constant-factor approximation for DTSP in nearly embeddable graphs, where both the factor and the time depend on the actual parameters of the class of graphs considered. Bonnet et al. [17] provided a $(\log r)$-approximation for ATSP in $2^{O(\frac{n}{r})}$ time for any $r$. Behrendt et al. [8] considered the case that there are few edges with (significantly) asymmetric costs and presented a $2.5$-approximation parameterized by the vertex cover number of the graph formed by such edges and a $3$-approximation parameterized by the minimum number of asymmetric edges in a minimum arborescence of the graph.

Further results are known for a variant of DWRP where the waypoints have a prescribed order [1] and for the undirected case [3].

Another studied variant of DTSP is the Many-visit TSP, where each vertex has a prescribed number of visits and the task is to find a closed walk which visits each vertex exactly the given number of times. After a significant effort, an algorithm was found for the problem that is exponential only in the number of vertices, i.e., independent of the demands which can be huge [11, 42]. The problem was recently studied from parameterized perspective [45] under the name Connected Flow. Here only a subset of vertices has a prescribed number of visits, the other vertices can be visited arbitrary number of times (or not visited at all) and edges have capacities (as in DWRP). They showed that the problem is para-NP-hard w.r.t. number of vertices with demand even in unweighted graph, while FPT w.r.t. this parameter, if there are no capacities. Further, they gave a polynomial kernel w.r.t. vertex cover number, an $n^{O(\mathrm{tw})}$-time algorithm and a matching $n^{o(\mathrm{tw})}$-time ETH lower bound.

Several parameterized and fine-grained complexity studies considered the local search for the undirected single-visit TSP parameterized the size of the neighborhood to be searched [10, 16, 22, 34, 44, 46]. None of these studies seems to extend to directed graphs.

is the problem of minimizing a separable convex objective (for us it suffices to minimize a linear objective) over a set of constraints of a specific form. Let $r\in \mathbb{N}$ and $s_i,t_i\in \mathbb{N}$ for every $i\in [N]$. The IP has $d={\sum }_{i\in [N]}{t}_i$ variables partitioned into $N$ so-called bricks. The $i$-th brick is denoted $x^{(i)}$ and contains $t_i$ variables. The constraints have the following form:

where we have $D_i\in {\mathbb{Z}}^{r\times t_i}$, $A_i\in {\mathbb{Z}}^{s_i\times t_i}$, ${𝐛}_0\in {\mathbb{Z}}^r$, ${𝐛}_i\in {\mathbb{Z}}^{s_i}$ and ${𝐥}_i,{𝐮}_i\in {\mathbb{Z}}^{t_i}$ for every $i\in [N]$. Let us denote $s={\max }_{i\in [N]}{s}_i$ and recall that the dimension is $d={\sum }_{i\in [N]}{t}_i$. There are $r$ global constraints and, apart from these, each variable is only involved in at most $s$ local constraints and one box constraint. We call variables not appearing in linking constraints local.

The current best algorithm solving the $N$-fold IP in ${(rs\mathrm{\Delta })}^{O(r^{2}s+r{s}^2)}d\log d\log D\log va{l}_{\max }$ time is by Eisenbrand et al. [28, Cor. 97]; see also [27, 41], where $D$ is the maximum range of a variable, $\mathrm{\Delta }={\max }_{i\in [N]}\left(\max ({\Vert D_i\Vert }_{\mathrm{\infty }},{\Vert A_i\Vert }_{\mathrm{\infty }})\right)$, and $va{l}_{\max }$ is the maximum feasible value of the objective.

Let us formally introduce the considered problems and establish notation used in the next sections.

Hence, an instance of DsTSP can be interpreted as an equivalent instance of DWRP, by letting $\kappa (e)=|V|$ for every arc.

Let $(G=(V,E),W,\omega ,\kappa ,b)$ be an instance of DWRP, where $n=|V|$. Let $G^{\prime }$ be the underlying undirected graph of $G$. Let $F\subseteq E(G^{\prime })$ be a feedback edge set of $G^{\prime }$ of size at most $k$, i.e., $G^{\prime }\setminus F$ is a forest. Note that it can be computed in polynomial time.

Our algorithm consists of three phases. First, we exhaustively apply some straightforward reduction rules in order to simplify (or already reject) the input. Then, we branch into $2^{O(k)}$ of possibilities, guessing the structure of the solution. Finally, for each such guess, we create an equivalent instance of DWRP with $O(k)$ vertices and edges. The original instance is a yes-instance if and only if at least one of the created instances is a yes-instance. Thus, our algorithm can be seen as a compression to OR of $2^{O(k)}$ instances, each of size $O(k)$. By Observation 7, each such instance can be solved in time $k^{O(k)}$ by brute force. Thus, the overall running time is $k^{O(k)}+n^{O(1)}$.

The following reduction rule lets us deal with vertices of degree 1 in $G^{\prime }$.

The correctness of the rule is straightforward. Note that, as $\{u,v\}$ is not part of any cycle in $G^{\prime }$, we may assume that $\{u,v\}\notin F$, and thus $F$ is still a feedback edge set of the graph resulting from the reduction rule.

We apply the reduction rule exhaustively, and, for simplicity, we keep denoting the resulting instance by $(G,W,\omega ,\kappa ,b)$ and the underlying undirected graph by $G^{\prime }$.

Let $R$ be the set of all vertices that are incident to the edges in $F$. Note that since the reduction rule was exhaustively applied, each vertex has degree at least two in $G^{\prime }$. Therefore, each leaf of $G^{\prime \prime }=G^{\prime }\setminus F$ is in $R$ and, thus, $G^{\prime \prime }$ has at most $2k$ leaves. Let $D$ be the set of vertices that have degree at least $3$ in $G^{\prime \prime }$. As $G^{\prime \prime }$ is a forest with at most $2k$ leaves, the size of $D$ is at most $2k-1$. We also define $X=R\cup D$, and we have $|X|\le 4k-1$.

Let ${𝒫}^{\prime }$ contain all paths in $G^{\prime \prime }$ with both endpoints in $X$ and all internal vertices outside $X$. In other words, the paths in ${𝒫}^{\prime }$ correspond to the edges of the forest obtained from $G^{\prime \prime }$ by contracting all vertices of degree 2. As there are at most $4k-1$ vertices in $X$ and, as $G^{\prime \prime }$ is a forest, the number of paths in ${𝒫}^{\prime }$ is at most $4k-2$. Finally, we define $𝒫={𝒫}^{\prime }\cup F$; we clearly have $|𝒫|\le 5k-2$.

Consider an optimum solution $C^{\ast }$, i.e., a shortest (in terms of the sum of weights) closed walk that visits every vertex from $W$ in $G$. Among all such solutions, pick one with the minimum number of edges.

Consider a path $P\in 𝒫$ with endpoints $u,v\in X$. A visit is an inclusion-wise maximal set of orientations of edges from $P$ that appear consecutively in $C^{\ast }$. A visit is a pass if it contains for every edge of $P$ exactly one of its orientations and it contains it exactly once, i.e., it corresponds to traversing $P$ once, either from $u$ to $v$ or from $v$ to $u$.

Notice that a path $P$ might be of one of the following types:

($u\mathbf{\curvearrowright }v$)

there is at least one visit and every visit is a pass from $u$ to $v$,

($u\curvearrowleft v$)

there is at least one visit and every visit is a pass from $v$ to $u$,

($u\leftrightarrows v$)

every visit is a pass and there is at least one pass in each direction,

($u\looparrowleft v$)

none of the visits is a pass, there is a visit that starts in $u$ and ends in $u$, but no visit that starts in $v$ and ends in $v$,

($u\looparrowright v$)

none of the visits is a pass, there is a visit that starts in $v$ and ends in $v$, but no visit that starts in $u$ and ends in $u$,

($u\circlearrowleft v$)

none of the visits is a pass, there is a visit that starts in $u$ and ends in $u$, and a visit that that starts in $v$ and ends in $v$,

$(u\mathrm{\cdots }v$)

the path $P$ is not visited at all by $C^{\ast }$.

Let us make some further observations about possible visits in $P$ by $C^{\ast }$.

If no internal vertex of $P$ is in $W$, then $P$ is of type $u\curvearrowleft v$, $u\curvearrowright v$, $u\leftrightarrows v$, or $u\mathrm{\cdots }v$. Indeed, any non-pass visit can be removed from $C^{\ast }$, contradicting the minimality.

Now consider a path $P$ of type $u\looparrowleft v$ (the case $u\looparrowright v$ is symmetric). We may safely assume that $P$ is visited exactly once by $C^{\ast }$, as one of the visits (the one reaching furthest towards $v$) covers all vertices covered by all the visits altogether. Further, we may assume that this single visit starts in $u$, reaches the internal vertex of $P$ that belongs to $W$ and is closest to $v$, and then goes back to $u$. Thus, if $P$ is of type $u\looparrowleft v$ or $u\looparrowright v$, then the visit in $P$ contributes to the total cost of the solution by a fixed amount that can be computed in advance. We denote this cost by $\mathrm{𝖼𝗈𝗌𝗍}(P,u\looparrowleft v)$ or $\mathrm{𝖼𝗈𝗌𝗍}(P,v\looparrowright u)$, respectively.

Now consider a path $P$ of type $u\circlearrowleft v$. Similarly as before, we can assume that there are at least two vertices from $W$ among internal vertices of $P$, as otherwise we can shorten $C^{\ast }$ by removing one of the visits. Furthermore, we can assume that $P$ is visited exactly twice: one visit starts at, $u$ reaches some vertex $x_u\in W$ and goes back to $u$, and the other visit starts at $v$, reaches some vertex $x_v\in W$, and goes back to $v$. In particular, no edge between $x_u$ and $x_v$ is traversed by $C^{\ast }$. As before, in polynomial time we can find an optimal pair of visits that cover all vertices from $W$ that are on $P$, and compute its contribution to the cost of the solution (here note that we need to be careful as some edges might be only available in one direction). We denote this cost by $\mathrm{𝖼𝗈𝗌𝗍}(P,u\circlearrowleft v)$.

Finally, each pass in a fixed direction has a fixed cost, equal to the sum of weights of edges in $G$ corresponding to the edges of $P$, where we only choose edges in the correct direction. We denote it by $\mathrm{𝖼𝗈𝗌𝗍}(P,u\curvearrowright v)$ or $\mathrm{𝖼𝗈𝗌𝗍}(P,v\curvearrowright u)$, depending on the direction. We also define $\mathrm{𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒}(P,u\curvearrowright v)$ (and, symmetrically, $\mathrm{𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒}(P,u\curvearrowleft v)$) to the minimum capacity of an edge of $G$ corresponding to an edge of $P$, in the direction from $u$ to $v$ (from $v$ to $u$), resp.

Note that due to the directions and capacities of edges, some types might not be available for $P$. We will define the cost associated with such an unavailable type to be $\mathrm{\infty }$.

Now we perform the branching. For each path $P$ in $𝒫$ with endvertices $u,v$, we guess its type $u\sim v$, where $\sim \in \{\curvearrowleft ,\curvearrowright ,\leftrightarrows ,\looparrowleft ,\circlearrowleft ,\looparrowright ,\mathrm{\cdots }\}$. This results in $7^{|𝒫|}=2^{O(k)}$ branches.

Consider one such branch. Now we build an instance $(G^{\prime },W^{\prime },{\omega }^{\prime },{\kappa }^{\prime },b^{\prime })$ of DWRP. Initialize $b^{\prime }=b$. We start with including all vertices from $X$ to $G^{\prime }$, and all vertices from $X\cap W$ to $W^{\prime }$. Now let $P$ be a path in $𝒫$ with endvertices $u,v\in X$. We proceed, depending on $\sim$. If the type of $P$ is $u\mathrm{\cdots }v$, we do nothing. If the type of $P$ is $u\looparrowleft v$ ($\looparrowright$), we add $u$ ($v$) to $W^{\prime }$, and decrease $b^{\prime }$ by $\mathrm{𝖼𝗈𝗌𝗍}(P,u\looparrowleft v)$ ($\mathrm{𝖼𝗈𝗌𝗍}(P,v\looparrowright u)$), respectively. If the type of $P$ is $u\circlearrowleft v$, we add both $u$ and $v$ to $W^{\prime }$, and decrease $b^{\prime }$ by $\mathrm{𝖼𝗈𝗌𝗍}(P,u\circlearrowleft v)$.

Now consider the case that the type of $P$ is $u\curvearrowright v$ (the case $u\curvearrowleft v$ is symmetric). We add a new vertex $x_{u\curvearrowright v}^P$ and edges $(u,x_{u\curvearrowright v}^P)$ and $(x_{u\curvearrowright v}^P,v)$. Vertices $u,v$, and $x_{u\curvearrowright v}^P$ are all included into $W^{\prime }$. We define ${\omega }^{\prime }((u,x_{u\curvearrowright v}^P))=\mathrm{𝖼𝗈𝗌𝗍}(P,u\curvearrowright v)$ and ${\omega }^{\prime }((x_{u\curvearrowright v}^P,v))=0$. Furthermore, we set ${\kappa }^{\prime }((u,x_{u\curvearrowright v}^P))={\kappa }^{\prime }((x_{u\curvearrowright v}^P,v))=\mathrm{𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒}(P,u\curvearrowright v)$. If the type of $P$ is $u\leftrightarrows$, we proceed as if was of both types $u\curvearrowright v$ and $u\curvearrowleft v$.

This concludes the construction of the instance. If , we reject it immediately. Clearly, the number of vertices of $G^{\prime }$ is at most $|X|+2|𝒫|\le 14k$, and the number of edges is at most $4|𝒫|\le 20k$. The discussion about correctness is postponed to the full version. $◀$

An undirected graph $G$ with vertex integrity $k$ has a $k$-modulator $M\subseteq V(G)$ of size at most $k$ such that each connected component of $G-M$ is of size at most $k$. We assume that $G$ is given along with $M$ as it can be found in $k^{O(k)}n$ time [26, 29]. Thus we assume that we are given an instance $(G,W,\omega ,\kappa ,b)$ of DWRP, with a set $M$ of size at most $k$, such that each weakly connected component of $G-M$ has size at most $k$. For brevity, we will speak about “components” instead of “weakly connected components.”

In what follows, we start with introducing some notions and establishing some properties of an optimum solution. Then, after some branching, we build an instance of ILP that corresponds to a solution with the required properties.

A segment is a walk in $G$ with at least two vertices, that starts and ends in a vertex of $M$ and all internal vertices are not in $M$. We remark that there might be no internal vertices – such a segment is just an arc contained in $M$. We call such a segment trivial. However, if a segment is non-trivial (i.e., not trivial), all its internal vertices are contained in a single component of $G-M$; the segment is associated with the component.

Note that the endpoints of a non-trivial segment need not to be distinct. A segment $s$ from $u$ to $v$ is minimal if there is no segment from $u$ to $v$ that uses only the arcs of $s$, contains all vertices of $s$ that are in $W$, and is shorter than $s$.

Let $C^{\ast }$ be an optimum solution, i.e., a shortest (w.r.t. the sum of weights of edges) closed directed walk in $G$ that visits every vertex of $W$. We treat $C^{\ast }$ as a sequence of vertices. Clearly $C^{\ast }$ can be decomposed into segments (where two consecutive segments overlap on corresponding endpoints); let ${𝒮}^{\ast }$ be the collection of these segments. We emphasize that ${𝒮}^{\ast }$ is a multiset, as some segments might be used more than once. We observe that we can assume that each segment in ${𝒮}^{\ast }$ is minimal, for otherwise we can replace it with a shorter one with the same endpoints, still covering all of $W$.

Some segments in ${𝒮}^{\ast }$ might not be needed to cover $W$, but are required to keep the connectivity of the solution. We call them connectors. We can identify connectors with the following procedure. We initialize ${𝒮}^{\circ }=\mathrm{\varnothing }$ and proceed iteratively as follows. If there is a segment $s$ in ${𝒮}^{\ast }\setminus {𝒮}^{\circ }$ such that the segments ${𝒮}^{\ast }\setminus {𝒮}^{\circ }\setminus \{s\}$ cover all vertices of $W$, we include $s$ into ${𝒮}^{\circ }$. We emphasize that here we work with multisets, so the “$\setminus$” operation respects the multiplicity of elements. The set ${𝒮}^{\circ }$ contains connectors. Note that ${𝒮}^{\circ }$ is not defined uniquely and it might depend on the ordering in which segments were selected.

Consider a connector, i.e., a segment $s$ from $u$ to $v$ that is in ${𝒮}^{\circ }$. We observe that we can safely assume that it is a $u$-$v$-path, as otherwise we can replace it with such a path obtaining a solution of no larger length. We call such segments simple.

Now let us consider a component $C$ of $G-M$. A traversal of $C$ is a collection ${𝒮}_C$ of segments associated with $C$ that:

• $\mathrm{■}$

  together cover every vertex from $W\cap V(C)$,

• $\mathrm{■}$

  for every $s\in {𝒮}_C$ there is a vertex in $W\cap V(C)$ not covered by segments in ${𝒮}_C\setminus \{s\}$,

• $\mathrm{■}$

  every segment in ${𝒮}_C$ is minimal,

• $\mathrm{■}$

  every edge $e$ is used at most $\kappa (e)$ times by ${𝒮}_C$.

Note that the segments from ${𝒮}^{\ast }\setminus {𝒮}^{\circ }$ associated with $C$ form a traversal. Indeed, the first condition follows since $C^{\ast }$ covers all vertices from $W$ and we moved segments to ${𝒮}^{\circ }$ if they were not required to cover $W\cap V(C)$. The second condition again follows from the definition of ${𝒮}^{\circ }$. Finally, recall that we already established the third condition without loss of generality.

Let us define two directed graphs $H_0$ and $H_1$ as follows. Both have the same vertex set, $M$.

For distinct $u,v\in M$, the arc $uv$ exists in $H_0$ if such an arc appears in $C^{\ast }$ (i.e., $C^{\ast }$ contains $u$ immediately followed by $v$). On the other hand, the arc $uv$ exists in $H_1$ if there is a non-trivial segment in ${𝒮}^{\ast }$ starting in $u$ and ending in $v$. We emphasize that neither $H_0$ nor $H_1$ has parallel arcs nor loops.

Let $H$ be the directed graph with vertex set $M$ and the arc set being the union of arc sets of $H_0$ and $H_1$ (again, with no parallel arcs). Note that $H$ has one strongly connected component $H^{\prime }$ containing all vertices from $W\cap M$, and vertices that are not in $H^{\prime }$ are isolated in $H$. These vertices do not appear on $C^{\ast }$ at all.

For $u,v\in M$, we say that a segment from $u$ to $v$ is bad (for a particular choice of $H_0,H_1$) if $u$ or $v$ are not in $H^{\prime }$, or the arc $uv$ does not appear in $H$. A traversal is bad if it contains a bad segment.

We say that a collection $𝒮$ of segments is compatible with $H_0$ and $H_1$ if, for every arc $uv$ of $H_0$, $𝒮$ contains at least one copy of the trivial segment $uv$, and for every arc $uv$ of $H_1$, $𝒮$ contains at least one non-trivial segment starting in $u$ and ending in $v$.

We proceed to the description of the algorithm. We exhaustively guess the graphs $H_0$ and $H_1$ described above, considering all possible graphs on the vertex set $M$, so that the union of these two graphs has one strongly connected component and the remaining vertices isolated. This gives us $2^{O(k^2)}$ possible guesses. We are going to look for a set of segments that are compatible with $H_0$ and $H_1$, and the structure of $H_0,H_1$ will be used to ensure that the solution is connected.

Suppose we are in a branch corresponding to one guess. We will build an instance of generalized $N$-fold ILP [27, 41]. In our case, we have a brick corresponding to each component $C$ of $G-M$ and some further bricks that do not have any local constraints.

For each traversal of $C$ that is not bad, we introduce one binary variable; recall that there are at most $k^{k(k+2)}$ such variables. The value of this variable indicates whether the vertices from $W\cap V(C)$ are covered by a particular traversal. Furthermore, we introduce a local constraint to ensure that exactly one traversal is chosen.

For each simple segment associated with $C$ which is a $u$-$v$-path for some $u,v\in M$, we introduce a variable with possible values from $0$ to $n$. The intended meaning of this variable is the number of times this segment was used as a connector from $u$ to $v$ by the solution. There are at most $k^{k+2}$ such variables.

For each edge $e$ with at least one endpoint in $C$ we introduce a (local) constraint ensuring that this edge is used by the solution at most as many times as the capacity permits. Namely, we sum over all simple segments and over all traversals that use edge $e$ (multiplying by how many times they use $e$) and require that this sum is at most $\kappa (e)$.

Now, let us move to variables not related to components. For each ordered pair $u,v$ of distinct vertices, we introduce a variable with possible values from $0$ to $\kappa ((u,v))$. The intended meaning of this variable is the number of times the trivial segment is used as a connector from $u$ to $v$ by the solution. This gives us at most $k^2$ variables. We can put each of this variable to a brick for itself. As the edges within $M$ are not used by any traversals or non-trivial segments, the box constraints ensure that the capacities are adhered for these arcs, i.e., there will be no local constraints for these bricks.

Next, we add global constraints that ensure that the selected set of segments is compatible with $H_0$ and $H_1$. More precisely, for each arc $uv$ of $H_0$ ($H_1$), we add a constraint that ensures that we choose the trivial segment $uv$ (at least one non-trivial segment that starts in $u$ and ends in $v$), respectively. We sum it over all selected traversals and connectors. These constraints are responsible for making the solution connected.

Finally, we need to make sure that for each $v\in M$, the number of segments that start in $v$ is equal to the number of segments that end in $v$. Again, we can force it by summing the number of particular segments, including trivial, connectors, and ones belonging to traversals. These are also global constraints.

We minimize the total length (i.e., the sum of weights of edges) in all selected segments. Note that for some guesses we might get an infeasible instance of ILP – this means that, e.g., the segments that are required by $H_0$ and $H_1$ do not exist in $G$ or all traversals of some component are bad. If all branches give infeasible instances, we return that there is no solution. However, every solution found (in any branch) is feasible and we can return the shortest one. From the description above it follows that if an optimum solution $C^{\ast }$ exist, we will find it (or, more precisely, a solution of the same total length) in the branch corresponding to the actual $H_0$ and $H_1$.

Recall that generalized $N$-fold ILP can be solved (see [28, Cor. 97] and also [27, 41]) in ${(rs\mathrm{\Delta })}^{O(r^{2}s+r{s}^2)}d\log d\log D\log va{l}_{\max }$ time, where

• $\mathrm{■}$

  $r$ is the number of global constraints (at most $k(k-1)+k=k^2$ in our case),

• $\mathrm{■}$

  $s$ is the number of local constraints for each brick ($O(k^2)$ in our case),

• $\mathrm{■}$

  $\mathrm{\Delta }$ is the largest coefficient in the constraints ($k$ in our case),

• $\mathrm{■}$

  $d$ is the total number of variables (at most $k^2+n\cdot k^{k(k+2)}+n\cdot k^{k+2}$ in our case)

• $\mathrm{■}$

  $D$ is the maximum range of a variable (at most $n$ in our case),

• $\mathrm{■}$

  and $va{l}_{\max }$ is the maximum value of the objective function (by Observation 7, in our case it is at most $n^2\cdot U$, where $U$ is the maximum weight of an arc in $G$).

Including the branching to guess $H_0$ and $H_1$, we obtain the final running time bound of $k^{O(k^6)}\cdot n\cdot {\log }^{2}n(\log n+\log U)$. This completes the proof. $◀$

Let $I=(G=(V,E),c,k)$ be an instance of CDS. We describe the construction of an instance $I^{\prime }=(G^{\prime },W,\omega ,\kappa ,b)$ of DWRP that is equivalent to $I$ such that $G^{\prime }$ has a bounded modulator to constant treedepth.

First, we describe the construction of the used gadgets. Each gadget has dedicated connecting vertices marked with “in” (e.g. $u_{\mathrm{in}}$), “out”, or “io”. Every gadget of the final $G^{\prime }$ will be connected to other gadgets by edges incident only to its connecting vertices: “in” (“out” resp.) vertices can only be incident to arcs that are coming “into” (going “out” from resp.) the gadget, and “io” can be incident to both types of arcs. If this is true then we say that the graph contains the gadget. We use $u^X$ to denote the vertex $u$ that belongs to a gadget $X$. All edges have weight $1$. Unless stated otherwise, every edge has capacity $n$; this is always sufficient by Observation 7. Crucially, getting from one terminal to another requires the traversal of exactly two non-terminal vertices. As the final budget is set to exactly $3\cdot (\text{number of terminals})$, it follows that every terminal is visited exactly once.

We begin with the force-$p$-traversals-gadget. It consists of three non-terminal vertices $u_{\mathrm{in}},u_{\mathrm{out}},w$ and terminal vertices $v_1,\mathrm{\dots },v_p$ joined with edges $(u_{\mathrm{in}},v_i),(v_i,w)$ for every $i\in [p]$ and $(w,u_{\mathrm{out}})$ of capacity $p$, see Figure 2.

Next, we need the cover-$z$-gadget, which is illustrated in Figure 3. Let $R_1$ be the directed path that starts at $s_{\mathrm{in}}$, goes to $f$, then to $b$, continues to $x_{\mathrm{in}}$, traverses all the $w$s’ until $y_{\mathrm{out}}$, goes to $c$ and finishes in $t_{\mathrm{out}}$. Also, let $R_2$ and $P$ be the red and blue paths depicted in Figure 3. The idea here is that this gadget has two possible behaviors: either its terminals are covered by the combination of the $R_2$ and $P$ paths, or all of its terminals except from $z_{\mathrm{io}}$ are covered by the $R_1$ path, and $z$ is covered by some external path that visits this gadget. Formally:

We now present the construction of $(G^{\prime },W,\omega ,\kappa ,b)$, see Figure 4. Let $𝒮$ be a force-$(k+1)$-traversals-gadget that we call selection-gadget and let $𝒜$ be a force-$(2|E|+|V|+1)$-traversals-gadget. We create an auxiliary non-terminal vertex $x$ and add an arc $(x,u_{\mathrm{in}}^{𝒜})$. Let $x$ together with $𝒜$ be called the auxiliary-gadget. We connect the selection- and auxiliary-gadgets by creating terminal vertices $x_1,x_2$, non-terminal vertex $x_3$, and arcs $(u_{\mathrm{out}}^{𝒜},x_2)$, $(x_2,x_3)$, $(x_3,u_{\mathrm{in}}^{𝒮})$, $(u_{\mathrm{out}}^{𝒮},x_1)$, $(x_1,x)$. These two gadgets compose the upper part of $G^{\prime }$.

Finally, we encode the vertices and edges of $G$ into $G^{\prime }=(V^{\prime },E^{\prime })$. For every vertex $u\in V$ we add vertices $z_u$, $c_u$, and $d_u$ to $V^{\prime }$, then we create a cover-$z_u$-gadget denoted ${ℰ}^u$. We add arcs $(u_{\mathrm{out}}^{𝒮},x_{\mathrm{in}}^{{ℰ}^u})$, $(y_{\mathrm{out}}^{{ℰ}^u},c_u)$, $(c_u,d_u)$, $(c_u,u_{\mathrm{in}}^{𝒮})$, $(u_{\mathrm{out}}^{𝒜},s_{\mathrm{in}}^{{ℰ}^u})$, $(t_{\mathrm{out}}^{{ℰ}^u},x)$ to $E^{\prime }$, and we set the capacity of $(c_u,d_u)$ to $c(u)$. For every arc $(u,v)$ such that $\{u,v\}\in E$, we create a cover-$z_v$-gadget denoted ${ℰ}^{u,v}$. Then we add arcs $(d_u,x_{\mathrm{in}}^{{ℰ}^{u,v}})$, $(y_{\mathrm{out}}^{{ℰ}^{u,v}},c_u)$, $(u_{\mathrm{out}}^{𝒜},s_{\mathrm{in}}^{{ℰ}^{u,v}})$, $(t_{\mathrm{out}}^{{ℰ}^{u,v}},x)$. Note that in the above we created two gadgets, ${ℰ}^{u,v}$ and ${ℰ}^{v,u}$, for each $\{u,v\}\in E$. Finally, we set the budget $b=132|E|+69|V|+3k+12$. This concludes construction of the DWRP instance.

On a high level, we show that any solution $C$ of the instance $(G^{\prime },W,\omega ,\kappa ,b)$ obeying the above budget has a specific behavior. First, the budget is set so that each terminal can be visited at most once. Let $S\subseteq V$ be a solution of $I$. The walk $C$ is separated into two stages. In the first stage, for each $u\in S$ the walk $C$ starts from $u_{\mathrm{in}}^{𝒮}$, goes through $𝒮$ to $u_{\mathrm{out}}^{𝒮}$, from there to $x_{\mathrm{in}}^{{ℰ}^u}$, using the $P$ path (visiting $z_u$) of the gadget ${ℰ}^u$ to $y_{\mathrm{out}}^{{ℰ}^u}$ and to $c_u$. Then for each vertex $v$ that is dominated by $u$, it goes from $c_u$ to $d_u$, uses the $P$ path of gadget ${ℰ}^{u,v}$ to visit $z_v$ and return to $c_u$. Crucially, this can be done at most $c(u)$ times. Finally it returns to $u_{\mathrm{in}}^{𝒮}$.

Once all the vertices of $S$ are dealt with in this way the first stage is done, and $C$ proceeds to $𝒜$. For each cover-gadget $ℰ$ (which are equal in number to the terminals of $𝒜$ minus one), the walk $C$ goes from $x$ through $𝒜$ to $u_{\mathrm{out}}^{𝒜}$ and then through $ℰ$ to cover the “remaining” vertices of $ℰ$ (i.e., the vertices that were not visited during the first stage); this is done by employing either the $R_1$ or the $R_2$ path, according to whether $ℰ$ was traversed during the first step. We then show that $C$ exists and is of the correct budget if and only if $I$ is a yes-instance of CDS.

The rest of the proof focuses on proving that $G^{\prime }$ has a modulator of size $7|M|+7$ to treedepth $86$, using that $G^{\prime }\setminus M$ has treedepth $2$ (it is a disjoint union of stars). $◀$