Edge-Minimum Walk of Modular Length in Polynomial Time

What is the complexity of EWM for constant $q$? It is unclear a priori; EWM is related to both polynomial-time solvable problems such as Shortest Modular-Length $st$-Walk and Directed Steiner Network, as well as NP-hard problems such as Shortest Modular-Length $st$-Path. Our main result is that EWM is in polynomial time for constant $q$:

Specifically, the exponent of $n$ in Theorem 1.1 has reasonable constants: $7+3{\log }_{2}q$, though we did not focus on optimizing them.

A natural generalization of EWM is to consider weighted graphs. EWM admits two natural notions of weights: (1) each edge has a length, and the length of a walk is the sum of the lengths of the edges, and (2) each edge (or vertex) has a cost and the edge-minimum walk is measured in terms of the sum of the costs of the edges (or vertices) that it traverses. We show in Section 7 that our algorithm extends to accommodate costs, and that it can also accommodate lengths provided that their values are polynomial. In the case where lengths and the value $q$ are super-polynomial, we show that the problem is NP-complete by reduction from Subset Sum.

Inspired by Directed Steiner Network, we also extend our results in Section 8 from one walk to multiple walks. The input is a directed graph $G$, and $k$ endpoint pairs along with modularity constraints: $(s_1,t_1,q_1,r_1),\mathrm{\dots },(s_k,t_k,q_k,r_k)$, and the goal is to find an edge-minimum subgraph that contains a walk from $s_i$ to $t_i$ of length $r_{i}mod{q}_i$, for all $i$. Generalizing our main result, we show (Theorem 8.4) that this problem, which subsumes the DSN and EWM problems, also admits a polynomial-time algorithm for constant $q_i$ values and a constant number $k$ of endpoint pairs. Our approach to show the result focuses on the case of strongly connected solutions (in line with the connection to DSN mentioned earlier), before extending the proof to arbitrary solutions by re-using lemmas from [18].

Let $w$ denote an edge-minimum odd-length $st$-walk, and let $G_w$ be the subgraph of $G$ consisting of the union of edges in the walk $w$. We first observe that, without loss of generality, $w$ does not contain any even cycles: If $w$ contained an even cycle, we could simply delete it, and $w$ would still be of odd length, and still be edge-minimum. (To clarify, we are not referring to even cycles in $G_w$, but rather even cycles in the walk $w$ itself. After deleting a cycle $C$ from $w$, edges from $C$ can still appear in $G_w$ if they are traversed at another point of the walk $w$.)

Now suppose $w$ contains two odd cycles in succession. Again, we could simply delete both cycles, and $w$ would still be of odd length, and still be edge-minimum. So, we can suppose without loss of generality that $w$ has either no cycles (and trivially has small cutwidth), or consists of a simple path $P_1$, followed by an odd cycle $C$, followed by a simple path $P_2$. We assume this latter case in the rest of the discussion, and we define $C$ by looking at first time that the walk re-visits a previously visited vertex: this ensures that, by construction, $P_1$ is vertex-disjoint from $C$. However, the graph does not necessarily have small cutwidth, because $P_2$ could intersect $P_1$ and $C$ in intricate ways forming an unbounded number of nested cycles. It is a priori conceivable that, e.g., a grid-like structure with high cutwidth could emerge. However, we can show that this does not happen.

First, we can observe that once $P_2$ leaves $C$, without loss of generality it does not return. This is because if $P_2$ leaves $C$ at vertex $a$ and then returns at vertex $b$, we can delete the subpath of $P_2$ from $a$ to $b$, and instead traverse only the edges of $C$ to get from $a$ to $b$. This way, we can still ensure that $w$ is of odd length since every traversal of $C$ changes the parity of $w$, and we can traverse $C$ for “free” without adding any extra edges.

Finally, we consider how $P_1$ and $P_2$ can interact. We can observe that without loss of generality $P_2$ cannot hit a vertex $a$ on $P_1$, then leave $P_1$, then return to a later vertex $b$ on $P_1$. In this case we could delete the subpath of $P_2$ from $a$ to $b$, and instead traverse $P_1$ to get from $a$ to $b$. Again, we can still ensure that $w$ is of odd length since we can always traverse $C$ for free to change the parity of $w$. We stress that this argument only holds when $P_2$ re-enters $P_1$ at a later vertex, and in fact, $P_2$ can re-enter $P_1$ at an earlier vertex an unbounded number of times.

With all of these observations in mind, we conclude that if $w$ has a cycle, then $w$ must have the very specific structure depicted in Figure 2. Then, it is visually clear that any vertical cut only has a constant number of crossing edges, and thus $w$ has constant cutwidth.

This concludes the outline for the case of odd walks. The same argument holds for even walks, and more generally an argument for a particular choice of constants $q,r$ is easily extendable by reduction to other constant values $r^{\prime }$ with the same $q$, simply by adding a new source connected to the original source by a path of constant length $r^{\prime }-r$ mod $q$. The challenging part is extending to arbitrary $q$. Our approach is to define a segment decomposition of the walk and prove that each successive segment allows us to expand the reachable set of remainder values, so that the number of segments is bounded as a function of $q$ (Lemma 4.3). We then show that the cutwidth of a walk can be bounded linearly in its number of segments (Proposition 5.1): we do this by defining a suitable ordering of the vertices following the chunks of the walk, which refine the segments in the decomposition. These two results imply that solutions to EWM have bounded cutwidth and hence that they can be found in polynomial time.

All graphs in the paper are finite and directed. Graphs are not necessarily simple; they may contain self-loops, but they do not contain multi-edges. Given a directed graph $G=(V,E)$, a walk $w$ in $G$ is a sequence of edges $w[1],\mathrm{\dots },w[\mathrm{\ell }]$ such that the target vertex of $w[i]$ is equal to the source vertex of $w[i+1]$ for each . Note that an edge $e$ of $G$ may occur at several positions in $G$: considering a position $i$ for which $w[i]=e$, we write $w[i]$ to refer to that occurrence of $e$ at the $i$-th position of $w$. However, when convenient we abuse notation and identify $w[i]$ with $e$ itself; e.g., we talk about the source and target vertices of $w[i]$ to mean those of $e$. For $1\le i\le \mathrm{\ell }$ we call $w[i]$ a first-visited edge occurrence if it is the first occurrence of some edge $e$, i.e., if there is no such that $w[j]=w[i]$. Otherwise, $w[i]$ is a revisited edge. Of course, each edge that occurs in $w$ is first-visited at exactly one position.

The source vertex $s$ of $w$ is that of $w[1]$, and its target vertex $t$ is that of $w[\mathrm{\ell }]$: we then call $w$ an $st$-walk. The length $|w|$ of $w$ is $\mathrm{\ell }$. The set of vertices used by $w$, denoted $V_w$, is simply the set of vertices that occur in $w$, i.e., occur in some edge of $w$; in particular the source and target vertices of $w$ are in $V_w$. The set of edges used by $w$ is . The subgraph spanned by $w$ is $G_w=(V_w,E_w)$. Note that $G_w$ is not the subgraph induced by $V_w$, as it only contains the edges that actually occur on the walk. A subwalk of $w$ is a contiguous subsequence of $w$. We denote subwalks of $w$ with the slicing convention, i.e., $w[:i]=w[1]\mathrm{\dots }w[i]$ and $w[i:j]=w[i]\mathrm{\dots }w[j]$. Note that the right endpoint is included so that, e.g., $w[i:j]$ is empty precisely when , and $w[:i]$ is empty precisely when $i\le 0$. When $u$ and $v$ are walks and when the target vertex of $u$ is the source vertex of $v$, we write $uv$ to mean the walk obtained by concatenating $u$ and $v$: it admits $u$ and $v$ as subwalks, and of course $|uv|=|u|+|v|$.

For convenience, throughout the paper we denote by $G_{w,i}$ the graph $G_{w[:i]}$ spanned by the subwalk $w[:i]$ (up to $i$ included); by convention $G_{w,0}$ is always the graph with the single vertex $s$ and no edges.

A strongly connected component (SCC) of a graph $G$ is a maximal set of vertices $C$ of $G$ such that, for any two distinct vertices $u,v\in C$, there is a directed path from $u$ to $v$ in $G$. As usual, belonging to the same SCC is an equivalence relation, so that SCCs form a partition of the vertices of $G$. We say that an SCC $C$ of $G$ is non-trivial if the subgraph of $G$ induced by $C$ contains at least one edge. This is the case if and only if $C$ contains more than one vertex, or contains a single vertex on which there is a self-loop.

We study the Edge-Minimum Walk of Modular Length problem (EWM), as defined in the introduction: given a directed graph $G=(V,E)$, terminals $s$,$t$, and non-negative integers , we wish to compute a subset $E^{\prime }$ of $E$ such that $(V,E^{\prime })$ has an $st$-walk of $rmodq$ and $E^{\prime }$ is edge-minimum (i.e., the number of edges of $G^{\prime }$ is minimum). This phrasing is somewhat different from the one given in the introduction, in which we wanted to compute an edge-minimum walk. However, we can easily compute an edge-minimum walk from $E^{\prime }$ by a product construction, in time $O(|E^{\prime }|\times q)$.

In the sequel, we only consider the computation of edge-minimum subsets of edges (rather than walks). When fixing inputs $G=(V,E)$, $s$, $t$, $q$, and $r$, we talk about a candidate solution to mean a subset $E^{\prime }$ of $E$ such that $(V,E^{\prime })$ has an $st$-walk of length $rmodq$ but $E^{\prime }$ is not necessarily edge-minimum, and of an optimal solution to mean a candidate solution which is additionally edge-minimum.

The cutwidth is a structural parameter of graphs. We show that there always exists an optimal solution to EWM with bounded cutwidth, which suffices to ensure that such solutions can be found with an efficient algorithm. We first recall the definition of cutwidth for undirected graphs. Let $G=(V,E)$ be an undirected graph. An ordering of $G$ is a total order over the vertex set $V$ of $G$. A cut $(V_{-},V_{+})$ of $G$ that respects the ordering is a partition $V_{-}\uplus V_{+}=V$ such that for all $(v_{-},v_{+})\in V_{-}\times V_{+}$. We say that an edge $e$ of $G$ crosses the cut if it has one endpoint in $V_{-}$ and one in $V_{+}$, i.e., $e\cap V_{-}$ and $e\cap V_{+}$ are both nonempty. Note that self-loops never cross cuts. The cutwidth of a cut $(V_{-},V_{+})$ that respects is the number of edges that cross this cut, and the cutwidth of is the maximum cutwidth of a cut that respects . The cutwidth of $G$ is then the minimum cutwidth of an ordering of $V$.

We now define cutwidth for directed graphs. Let $G=(V,E)$ be a directed graph. Its underlying undirected graph is $G^{\prime }=(V,E^{\prime })$ where $E^{\prime }=\{\{u,v\}\mid (u,v)\in E,u\ne v\}$: note that self-loops are not reflected in $G^{\prime }$. We then define the cutwidth of $G$ to be that of $G^{\prime }$. We underscore that our definition of cutwidth for directed graphs is always the undirected cutwidth: we do not consider the directed cutwidth in this paper. We then define the cutwidth of a walk $w$ of $G$ as the cutwidth of the directed graph $G_w$.

Let $w$ be a walk. Its segment decomposition is a sequence of walks $s_1,\mathrm{\dots },s_{\xi }$ such that $w=s_1\mathrm{\cdots }{s}_{\xi }$; the number $\xi$ is the number of segments of $w$. The segment decomposition is defined by processing the walk $w$ from left to right as follows. Initially, the segment decomposition is the empty sequence, and the entire walk $w$ remains to be decomposed. At any point of the decomposition, we have already computed the first $\sigma$ segments $s_1,\mathrm{\dots },s_{\sigma }$ for some number $\sigma \ge 0$ of segments, and can write $w=s_1\mathrm{\cdots }{s}_{\sigma }{w}^{\prime }$. If $w^{\prime }$ is non-empty, we compute the next segment as a prefix of $w^{\prime }$.

Informally, we read $w^{\prime }$ and terminate the segment whenever we have a first-visited edge $w^{\prime }[j]=(u,v)$ followed (not necessarily immediately) by an edge $w^{\prime }[k]=(x,y)$ where $y$ can be reached by a path from $u$ using only edges of $w$ up to $w^{\prime }[j]$ excluded. The intuition of segments is that they capture a moment where the walk revisits a vertex $y$ from a vertex $u$ via a path that starts with an edge $e=(u,v)$ which had not been previously visited in $w$, even while there was already a path from $u$ to $y$ in the graph spanned by the walk before $e$ was visited. Formally, we will look for the segment end inside the suffix $w^{\prime }$ of $w$, according to the following definition:

Given the definition of a segment end above, the next segment of the decomposition after $s_{\sigma }$ is simply $s_{\sigma +1}:=w[{\lambda }_{\sigma }+1:k]$. This means that we terminate the $(\sigma +1)$-th segment right after the edge $w[k]$, and continue the decomposition if $s_1\mathrm{\cdots }{s}_{\sigma +1}$ does not yet cover the entire walk $w$. If there is no segment end at any $k$, then we take all the rest of the walk $w^{\prime }$ to be the last segment of the decomposition and we finish. Note that for this reason, unlike other segments, the last segment of the decomposition may not feature a segment detour.

Let us formalize which paths are known to exist at the moment when a segment ends:

Notice that we may have $y=u$, and then $p_{\sigma }$ and $\overline{p_{\sigma }}$ may be empty; but ${\text{det}}_{\sigma }$ is never empty because it contains at least $w[j]$.

In the sequel for each we denote by $p_{\sigma }$ and $\overline{p_{\sigma }}$ a pair of paths obtained by applying Lemma 4.2 (if there are multiple valid choices for $p_{\sigma }$ and $\overline{p_{\sigma }}$, we choose arbitrarily).

For a walk $w$ and segment $\sigma$, we denote by ${\mathrm{\Delta }}_q(w,\sigma )$ the value $(|{det}_{\sigma }|-|p_{\sigma }|)modq$ and call this the³³3Note that there could be several choices for the difference achievable by $\sigma$ depending on the arbitrary choices made earlier, e.g., depending on the first edge $j$ for the segment detour, and on the choice of paths $p_{\sigma }$ and $\overline{p_{\sigma }}$; nevertheless, we fix one single value ${\mathrm{\Delta }}_q(w,\sigma )$ according to the choices made. difference achievable by $\sigma$. We often drop the subscript $q$ when clear from context. Intuitively, we know that we can modify the walk $w$ to replace the subwalk ${det}_{\sigma }$ from $u$ to $y$ by the existing path $p_{\sigma }$ that goes from $u$ to $y$, and this change subtracts ${\mathrm{\Delta }}_q(w,\sigma )$ from the length of the walk modulo $q$; we will make this formal in the sequel. It should also be intuitively clear that achievable differences can be assumed to be non-zero in an edge-minimum walk: intuitively, an achievable difference of 0 means that we can replace the detour ${det}_{\sigma }$ by the existing path $p_{\sigma }$ that has the same endpoints, without changing the length of the walk modulo $q$. We know that this change does not harm the edge-minimality of $w$ because $p_{\sigma }$ consists of already visited edges. What is more, having too many segments with the same achievable difference is useless, because we can intuitively replace ${det}_{\sigma }$ by $p_{\sigma }$ and compensate the effect of this change by doing similar substitutions in earlier segments. Then, thanks to Lagrange’s theorem on the additive group $\mathbb{Z}/q\mathbb{Z}$, the number of segments can in fact be bounded by $1+{\log }_{2}q$. We formalize this in the following lemma, which is the main result of this section:

The rest of this section is devoted to proving the Segment Decomposition Lemma; we will then use it in the next section to bound the cutwidth of some edge-minimum solution.

Recall that a preorder over a set is a binary relation that is both reflexive and transitive (this is a weaker requirement than non-strict partial orders which are additionally required to be antisymmetric). To prove the Segment Decomposition Lemma (Lemma 4.3), we define a preorder over the edge-minimum walks that are using a specific set of edges. Intuitively, the preorder favors walks which do their first visit of edges as late as possible relative to the end of the walk. More precisely, the preorder criterion asks us to minimize the number of remaining steps of the walk at the moment where the last first-visited edge is visited; then break ties by minimizing the number of remaining edges at the moment where the second-to-last first-visited edge is visited; and so on. This is designed to ensure that replacing a detour ${det}_{\sigma }$ by $p_{\sigma }$ improves the walk according to the preorder.

Let us fix from now on the graph $G=(V,E)$, the source $s$ and target $t$, and the integers $r$ and $q$. For any subset of edges $E^{\prime }\subseteq E$, we define an $E^{\prime }$-walk to mean an $st$-walk of length $rmodq$ in $G$ which uses precisely the edges of $E^{\prime }$. Let us then define the order:

In other words, the timestamp preorder compares two walks by the number of remaining edges to traverse when visiting the last first-visited edge, then the second-to-last, and so on. Note that the timestamp preorder is not antisymmetric because two different walks on the same set of edges may happen to have the same first-visited timestamp (i.e., they visit first-visited edges at the same positions from the end, even though the identity of these edges and the revisits may be different). We then define:

Note that, whenever there is an $E^{\prime }$-walk, then there is a timestamp-minimum $E^{\prime }$-walk, but it is not necessarily unique because the timestamp preorder is not antisymmetric. We are now ready to conclude the section by proving the Segment Decomposition Lemma (Lemma 4.3):

We show that a timestamp-minimal walk has at most $1+{\log }_{2}q$ segments. We consider the successive subgroups of $\mathbb{Z}/q\mathbb{Z}$ generated by the achievable differences of the successive segments, and show that these must be a strictly increasing subsequence, so that the bound follows by Lagrange’s theorem. To do this, we show as an intermediate claim that walks can be modified to augment their length by any combination of achievable differences of previous segments, while still using the same edges. Thanks to this claim, assuming by contradiction that there is a segment $s_{\sigma }$ whose achievable difference is already achievable using the preceding segments, then we rewrite the segment to replace its detour ${\text{det}}_{\sigma }$ by the path $p_{\sigma }$ from Lemma 4.2, and use the claim to modify the walk and fix its length. We then show that this modification yields a walk which is smaller in the timestamp preorder, contradicting the minimality of $w$. See the full version [3] for the full proof. $◀$

We define first-visited vertices similarly to first-visited edges: for every vertex $v\in V_w$ occurring in $w$, we say $v$ is first-visited at $w[i]$ if $w[i]$ is the first edge in which $v$ occurs. Note that a vertex $v$ which is first-visited at $w[i]$ always occurs as the target vertex of $w[i]$, except in the specific case of the first edge $w[1]$ where both the source $s$ and the target vertex are first-visited at $w[1]$. Of course, every vertex of $V_w$ is first-visited at exactly one position. Further, if a vertex $v$ is the target vertex of an edge $w[i]$ and is first-visited at $w[i]$, then both $w[i]$ and $w[i+1]$ (if it exists) must be first-visited edges.

We can now define chunks:

In other words, a chunk is a maximal sequence of one or more consecutive first-visited edges such that the first and last vertex are not first-visited (unless they are extremities of the whole walk) but all intermediate vertices are first-visited. A chunk may consist of a single first-visited edge $w[i]$ between two already-visited vertices, in which case there are no intermediate vertices.

The first and last vertices of chunk $w[i:j]$ are the source vertex of $w[i]$, and the target vertex of $w[j]$, respectively. Note that two successive chunks in the walk need not be separated by revisited edges and can simply be separated by a revisited vertex: for instance, for the length-$2$ walk $(s,s),(s,t)$, all edges are first-visited, but there are two chunks of length 1 which are separated by the revisit of the vertex $s$.

It will be useful to distinguish two special kinds of chunks. First, tadpole chunks, which loop back on an intermediate vertex of the chunk:

In other words, a tadpole is a chunk that consists of a path (containing at least one edge), followed by a cycle (possibly a self-loop).

Second, cycle chunks, which loop back on the vertex from which they started:

Note that these two cases are mutually exclusive. A chunk which is neither a tadpole nor a cycle, and thus is a simple path, is a normal chunk.

The notion of chunk must be distinguished from the notion of segments used in the segment decomposition of the previous section, but we can notice the following connections between the two notions:

• $\mathrm{■}$

  Segment ends never happen within a chunk: indeed, the intermediate vertices $y$ reached within a chunk are first-visited by definition, so there is no way to reach them except by the edge that precedes them, and thus no earlier path can reach $y$ in the walk.

• $\mathrm{■}$

  At the end of a tadpole chunk or cycle chunk, the current segment always ends. Indeed, the last edge $e^{\prime }=(x,y)$ of the chunk reaches a vertex $y$ which already has an outgoing edge in the chunk: this edge is a first-visited edge $e=(y,v)$, and the empty path from $y$ to itself allows us to finish the segment at the end of the chunk, i.e., just after $e^{\prime }$.

In summary, chunks are contiguous subsequences of the walk that never straddle segment boundaries, and the end of a tadpole chunk or cycle chunk always triggers the end of a segment. Also note that, by definition, chunks form a partition of the first-visited edges. This implies that, except possibly for the last segment, every segment must contain at least one chunk, because they contain at least one first-visited edge.

Having defined the notion of chunks of the walk $w$, we now define the ordering $\prec$ along which we will show that the cutwidth is bounded. This definition only depends on chunks; it does not depend on the segment decomposition. We see the total order $\prec$ as a sequence of vertices. Initially, the order is the empty order on the single vertex $s$. Then, for every chunk $w[i:j]$ successively, we consider the (possibly empty) sequence $\sigma$ of the intermediate vertices of $w[i:j]$. Recall that the first vertex of $w[i:j]$ is already in the domain of $\prec$: either it is $s$ (for the first chunk), or it is a vertex which is already visited. Then there are four cases:

• $\mathrm{■}$

  Tadpole: If $w[i:j]$ is a tadpole, then we insert all its intermediate vertices at the end of the current ordering $\prec$, in the order in which they were first-visited.

• $\mathrm{■}$

  Cycle: Otherwise, if $w[i:j]$ is a cycle, then, letting $v$ be its first and last vertex, we know that $v$ already occurs in $\prec$, and we insert all its intermediate vertices right after the vertex $v$, in the order in which they were visited.

• $\mathrm{■}$

  Normal: We consider two subcases:

  • –

    First, suppose that the last vertex $t$ of $w[i:j]$ is first-visited at $w[j]$. This is only possible with $j=|w|$, so that $w[i:j]$ is the last chunk. Then we do the same as in the tadpole case: insert the intermediate vertices and $t$ at the end of the current ordering $\prec$, in the order in which they were first-visited.

  • –

    Otherwise, $w[i:j]$ is a chunk whose last vertex $v$ is first-visited at $w[k]$ with so $v$ already occurs in $\prec$, and as we explained the first vertex $u$ of the chunk also already occurs in $\prec$. Further, we have $v\ne u$ because the chunk is not a cycle. Then, we insert the intermediate vertices so that the vertices along the chunk are ordered in a monotone fashion in the ordering. In other words, let $x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ be the successive intermediate vertices of the chunk, so that its edges are $(u,x_1),(x_1,x_2),\mathrm{\dots },(x_{\mathrm{\ell }-1},x_{\mathrm{\ell }}),(x_{\mathrm{\ell }},v)$. If $u\prec v$ then we insert $x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ in order between $u$ and $v$, and if $v\prec u$ we insert $x_{\mathrm{\ell }},\mathrm{\dots },x_1$ in order between $v$ and $u$. The order $\prec$ between the newly inserted elements and the existing elements between $u$ and $v$ is arbitrary, for instance we can arbitrarily say that we insert the new vertices just after the smallest of $u$ and $v$ in $\prec$.

Note that, in all cases above, the (intermediate) vertices of a chunk are always ordered as a monotone sequence.

We have defined, from our walk $w$, the order $\prec$ along which we will bound the cutwidth. To show the cutwidth bound, we establish two results describing the SCCs of the graph generated by the walk and its close relationship with our ordering $\prec$:

We can now turn back to the segment decomposition introduced in the previous section for the walk $w$, and show how the number of segments of $w$ can be used as a bound on the cutwidth of the graph $G_w$ spanned by $w$, following the order $\prec$ that we defined. For this, we will consider an arbitrary cut $V_{-}\uplus V_{+}$ of $V_w$ following $\prec$, and count how many edges of $w$ cross the cut. As each edge is first-visited once, and first-visited in exactly one segment, it suffices to bound how many edges each segment contributes to the cut, and to count only the first-visited edges of each segment. We want to show:

This immediately implies the Segment Cutwidth Bound (Proposition 5.1) stated at the beginning of the section. This bound of $3$ edges crossing the cut can be proved by a case analysis summarized in the following lemmas:

All that remains is to bound the contribution to the cut of the normal chunks that cross the cut backwards. To this end, let us distinguish the last chunk of a segment which we call the final chunk, and the remaining chunks in that segment which we call non-final chunks. Non-final chunks must be normal (because the segment ends right after cycle chunks or tadpole chunks), and they cannot cross the cut forward by the previous lemma.

We are ready to conclude the proof of Lemma 5.9:

We consider a segment and consider the SCC decomposition of the graph of the walk when the segment starts, using Lemma 5.7. By Lemma 5.8 the segment begins in the rightmost SCC according to the order. Now the intuition is the following: if all chunks but the final one stay on the same side of the cut, then only the final chunk can cross the cut and the preceding lemmas (Lemma 5.10, Lemma 5.11 and Lemma 5.12) show that the bound is satisfied.

Otherwise, there is a first non-final chunk which ends on some SCC $C_{\varphi }$ that contains nodes to the left of the cut and this chunk thus potentially crosses the cut (backwards, by Lemma 5.13). If the next chunk is final, the bound is satisfied, so we may assume the next chunk is not final. This next chunk may also cross the cut, but in any case it has for target an SCC $C_{\psi }$ which is further left than $C_{\varphi }$, a property we exploit to show that the walk cannot return to the right of the cut without terminating the segment. This implies that the cut is crossed at most 4 times in total: once for each of the two non-final chunks considered, and potentially twice for the final chunk. We lower the bound to 3 by showing that in fact the final chunk can only cross the cut once if it is preceded by two chunks that already crossed the cut. See the full version [3] for the full proof. $◀$

We first study the extension of the EWM problem with costs on edges. Specifically, the EWM problem with costs on edges takes as input a directed graph $G=(V,E)$, a cost function $\gamma$ giving to each edge $e\in E$ a cost $\gamma (e)$, a pair of a source $s\in V$ and target $t\in V$, and a modularity requirement $rmodq$ for integers $q$ and $r$. The output to the EWM problem with costs on edges is an $st$-walk of length $rmodq$ such that the cost $\gamma (E_w):={\sum }_{e\in E_w}\gamma (e)$ is minimum. We assume that all costs given by $\gamma$ are nonnegative. Indeed, in the presence of negative weights, we lose the correspondence explained in Section 3: computing a minimum-weight subgraph that contains a walk reduces to the case of positive weights (all negative-weight edges will always be included in the optimal solution subgraph); but computing a minimum-weight walk is NP-hard even without modularity constraints:

Our tractability result for EWM (Theorem 1.1) can be easily extended to solve the EWM problem with costs on edges. Specifically, the Segment Decomposition Lemma (Lemma 4.3) shows that there must be an optimal solution to EWM with costs on edges that obeys the bound on the number of segments, because the $\gamma$ function on subset of edges is monotone. Then the Segment Cutwidth Bound (Proposition 5.1) applies as is, and the algorithm to find an optimal solution of bounded cutwidth from the previous section can be easily extended: simply modify the definition of the graph of configurations (Definition 6.3) so that the cost of an edge labeled with a set $E^{\prime }$ of edges of $G$ is no longer the cardinality $|E^{\prime }|$ of $E$ but the total cost $\gamma (E^{\prime })$. Other than that, the algorithm proceeds in the same way, and computes a shortest path which now reflects the subgraph of $G$ satisfying the requirements which has minimum cost instead of minimum cardinality.

We also mention that the EWM problem can be defined to have costs (unit costs or not) on vertices instead of edges. In this case, the cost of a candidate solution is the number of different vertices traversed by the walk (or more generally their total cost). However, this problem is interreducible to the EWM problem with costs on edges:

Having studied the use of costs on edges to change the optimization criterion, we turn to a different problem variant where we annotate edges with integer lengths. Specifically, the EWM problem with lengths takes as input a directed graph $G=(V,E)$, a length function $\delta :E\to \mathbb{N}$, and a pair of a source $s\in V$ and target $t\in V$ and a modularity requirement $rmodq$ for integers $q$ and $r$. The answer to the EWM problem with lengths is an $st$-walk $w$ that traverses a minimum number of distinct edges and whose total length is $rmodq$, i.e., $\delta (w):={\sum }_{1\le i\le |w|}\delta (w[i])$ is $rmodq$. (Note that the length of an edge is summed as many times as the edge is traversed.)

The impact of allowing lengths is different depending on the regime. In the case where $r$ and $q$ are constant, or given in unary, then we can rewrite the graph in polynomial time to eliminate edge lengths. Specifically, letting $m$ be the number of edges in the graph, we replace each edge $e$ of length $\delta (e)$ by a path on $(m+1)q+(\delta (e)modq)$ edges (where $m$ is the number of edges in the graph). This ensures that a walk in the new graph has the same modularity as the corresponding walk in the original graph, and the cost of a candidate solution in the rewritten graph is $(m+1)qM+ϵ$, where $M$ is the number of original edges traversed and $ϵ\le mq$. This ensures that an optimal solution in the original graph indeed minimizes the number of edges taken from the original graph.

One different regime is when $r$ and $q$ are written in binary and do not necessarily have polynomial value. In this case, the EWM problem with lengths written in binary can be shown to be NP-hard by an easy reduction from Subset Sum. In fact, just the problem of deciding the existence of a walk of length $qmodr$ is NP-hard:

We do not know whether an analogous hardness result holds for the original EWM problem (without edge lengths) in the setting where $q$ and $r$ can be written in binary and do not necessarily have polynomial value. Indeed, in the proof above, we crucially use the edge lengths to concisely write the numbers given in the Subset Sum instance; writing them in unary as paths of the corresponding length will not give a polynomial-time reduction and indeed the Subset Sum problem can be solved in pseudo-polynomial time.

We last address the question of showing an upper bound on the complexity of EWM with lengths, by showing an NP upper bound. Of course the bound is phrased on the decision version of EWM with lengths, i.e., given an instance of EWM with lengths and a threshold $k$, we wish to decide whether there exists a candidate solution having at most $k$ different edges. We have:

Let us recall the definition of the SCSS problem [17, 18] before explaining how it can be reduced to EWM. In the SCSS problem, the input simply consists of a directed graph $G=(V,E)$ with an input set $T\subseteq V$ of terminals, and we want to find the smallest subgraph $E^{\prime }\subseteq E$ that is strongly connected and contains edges incident to each terminal in $T$. In other words, SCSS is a special case of DSN where the connectivity requirements on the vertices of $T$ require that they are strongly connected. The SCSS problem is NP-hard in general (by an easy reduction from the directed Steiner tree problem) but it can be solved in polynomial time provided that the size of $T$ is bounded by a constant, as shown in [17]. Thus, for $k\in \mathbb{N}$, we write $k$-SCSS to refer to the SCSS problem where the set $T$ of terminals is required to contain at most $k$ vertices. Following our previous terminology in the paper, when we talk of candidate solutions we mean a subgraph satisfying the requirements of a problem (e.g., for $k$-SCSS, a strongly connected subgraph containing the requisite terminals), and by optimal solution we mean a candidate solution which is also edge-minimum.

Let us show that the SCSS problem can be reduced to EWM, which implies that Theorem 1.1 gives an alternative proof of the results of [17] (with worse bounds). More precisely, we show:

The previous reduction shows that our EWM problem is intuitively at least as complicated as SCSS, given that the tractability of EWM for constant $q$ implies that of SCSS for constant $k$. (This being said, we do not claim that the polynomial algorithm given by our results is as efficient as that of earlier works [17, 18].) Alternatively, instead of this black-box reduction, we can also adapt our techniques to recapture the tractability of SCSS by showing a bound on the cutwidth of optimal solutions, using the segment decomposition. We exemplify below how this is done, and will revisit this afterwards when extending EWM to support multiple paths. Recall the notion of timestamp-minimum walks (Definition 4.5), and let us show the following result; note that it applies to edge-minimal solutions (not just optimal solutions).

We remark that the cutwidth bound of $3k$ given by this result is slightly better than the bound of $6k$ shown in [18].

The reduction from SCSS to EWM leads to the natural question of whether there could be a problem which subsumes SCSS and EWM, or even DSN and EWM; and a polynomial-time algorithm that subsumes the tractability of all these problems. We now introduce such a problem, dubbed Directed Steiner Network with Modularity (DSNM), and show a polynomial-time algorithm to solve it.

Our last result in this paper is to show that the $k$-DSNM problem is in PTIME when $k$ and the modulo values $q_i$ are constants. This result subsumes Theorem 1.1 and the tractability of $k$-DSN for constant $k$ shown in [17, 18].

Note that our exponents are given up to constant factors, so we do not claim to recover the same exponents as earlier works on $k$-DSN without modularity constraints (i.e., for $q=1$).

The overall strategy to prove Theorem 8.4 is to follow the methodology used for EWM, adjusting the constructions presented so far in the paper. Deviating somewhat from EWM, but following prior work about DSN [17, 18], in our study of DSNM we will focus on the SCCs of an optimal solution and study them separately, instead of studying the entire solution graph. Our main objective is to bound the cutwidth of SCCs in an optimal solution as a function of $q$ and of the number $k$ of endpoint pairs. We can then easily deduce like in [18] that the cutwidth of optimal solutions is bounded as a function of $q$ and $k$. To compute the solutions of bounded cutwidth, we then modify slightly the algorithm of Section 6.

To study the SCCs of optimal solutions, it will be useful to introduce an analogue of the SCSS problem featuring modularities. Specifically, we call $k$-SCSSM the problem that takes the same input as $k$-DSNM and returns a smallest strongly connected subgraph $H$ of $G$ such that $H$ contains a walk from $s_i$ to $t_i$ of length $r_{i}mod{q}_i$ for every $i\le k$. Note that, unlike the SCSS problem which was simply defined by a set of terminals, in $k$-SCSSM we specify a set of tuples connecting pairs of vertices, because we need to specify which remainder must be achieved by which endpoint pair. The difference with $k$-DSNM is only that the solution graph is required to be strongly connected. Our study of $k$-SCSSM is motivated by the fact that the SCCs of optimal solutions to $k$-DSNM are optimal solutions to instances of $k$-SCSSM, as was already known in the setting without modularities [17]. Namely:

We next bound the cutwidth of optimal solutions to the $k$-SCSSM problem specifically. Then we will deduce a cutwidth bound on optimal solutions to $k$-DSNM using a result of [18]. Finally, we explain how to design an algorithm to compute these solutions.

Let us start by showing that solutions to $k$-SCSSM have a small segment number and hence a small cutwidth:

Note that this claim only works for the $k$-SCSSM problem, not the $k$-DSNM problem, because it assumes the solution can be covered by a single walk which is not true in general for $k$-DSNM. Let us show the result:

The proof of this result can be decomposed into three steps. In step 1, we define the notion of a legal covering walk, which is a walk that covers the edges of a solution in a prescribed order: first visit all terminals to witness that they are strongly connected in a subwalk $w_0$ (similarly to Lemma 8.2), then visit all paths with the prescribed modularities in a subwalk $w^{\prime }$. In step 2, we carefully impose a variant of timestamp-minimality on legal covering walks towards bounding their number of segments. In step 3, we use Lemma 8.2 (on the first part of the legal covering walk) and an argument adapted from Lemma 4.3 (for the second part) to show that the number of segments is bounded. The point of splitting the walk in two is that $w_0$ visits enough edges to allow us to move to arbitrary endpoints and ensure strong connectedness: this allows us to replay arbitrary detours in any subwalk no matter where they occur, intuitively “pooling” the achievable differences $\mathrm{\Delta }(w,\mathrm{\dots })$ between all the subwalks. See the full version [3] for the full proof. $◀$

We have shown that optimal solutions to the $k$-SCSSM problem can be assumed to have bounded cutwidth. We now wish to show that the same is true for optimal solutions to the $k$-DSNM problem. This is simple, using Lemma 8.6 above along with two lemmas from [18]:

We have shown in Lemma 8.7 that optimal solutions to the $k$-DSNM problem have cutwidth $O(k+\log q)$. The only remaining thing to prove Theorem 8.4 is to adapt the dynamic algorithm from Section 6 to compute solutions to that problem instead of EWM. We explain in the full version [3] how this is done.

One natural direction for further research would be to improve the complexity bounds that we show. Our algorithm for EWM runs in time $n^{O(\log q)}\cdot 2^{O(q{\log }^{2}q)}$. Can the factor of $q$ in the exponent be improved, e.g., by getting an algorithm in time $n^{O(\log q)}$? Or, on the other hand, is the problem NP-hard? (We have only shown that the variant of EWM with edge lengths is NP-hard, in Proposition 7.1.)

It could be interesting to search for walks that are minimized according to some criterion that is “intermediate” between shortest walk and edge-minimum walk, e.g., if the cost of each edge is expressed as a function of how many times it is traversed by the walk. Such a general framework would capture the two problem variants that we contrast in the introduction: shortest walks are the case where we are charged $\mathrm{\ell }$ when traversing an edge $\mathrm{\ell }$ times, and edge-minimum walks are the case where we are charged $1$ when traversing an edge $\mathrm{\ell }>0$ times and charged $0$ when we do not traverse it.

Last, one other problem of interest would be to investigate the complexity of finding edge-minimum subgraphs guaranteeing the existence of $st$-walks satisfying other properties. One very natural example is the following: Given a number $\mathrm{\ell }$, and a directed graph $G$ with specified vertices $s,t$, find an edge-minimum $st$-walk of length exactly $\mathrm{\ell }$. (This is the same as EWM except the length is exactly $\mathrm{\ell }$, instead of $rmodq$.) The trivial algorithm for this problem is in time $O(n^{\mathrm{\ell }})$, but can we do better? To our knowledge, this problem has not been studied.

Another example is looking for edge-minimum walks that achieve constraints expressed by a finite semigroup. For instance, assume that each edge of the graph is labeled by a semigroup element, and that we want a walk whose evaluation in the semigroup achieves a specific target element of the semigroup, where evaluating the walk means multiplying the labels of its edges in the order that they are traversed. This problem generalizes the EWM problem (with lengths on edges), which uses the semigroup $\mathbb{Z}/q\mathbb{Z}$. An alternative way to phrase this problem is in the language of regular path queries (RPQs) mentioned in the introduction: fixing a regular language $L$ on an alphabet $\mathrm{\Sigma }$, and given a directed graph $G$ with terminals $s$ and $t$ and with edges labeled by letters of $\mathrm{\Sigma }$, find an edge-minimum subgraph $G$ with an $st$-walk which evaluates to a word that belongs to $L$. For which fixed regular languages $L$ can this problem be solved in polynomial time in $G$?