An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

Consider a mixed graph $G=(V,E\cup A)$ with a set of undirected edges $E$ and directed arcs $A$. An arbitrary orientation is assigned to each undirected edge to define a forward direction, which serves solely as a notational convenience and has no bearing on the results. We define ${\delta }^{-}(v)$ and ${\delta }^{+}(v)$ as the sets of in-edges/in-arcs and out-edges/out-arcs of a vertex $v$, respectively. Each edge and arc has an associated lower bound, upper bound, and cost function, denoted as $\mathrm{\ell },u:E\cup A\to \mathbb{Z}$ and $c:E\cup A\to ℝ$.

A circulation is a function $f:E\cup A\to \mathbb{Z}$ such that ${\sum }_{e\in {\delta }^{-}(v)}f(e)={\sum }_{e\in {\delta }^{+}(v)}f(e)$ for every vertex $v\in V$. The circulation $f$ is feasible with respect to the lower bounds $\mathrm{\ell }$ and upper bounds $u$ if $\mathrm{\ell }(e)\le f(e)\le u(e)$ for every edge $e\in E\cup A$. Typically, the values of $\mathrm{\ell }$ and $u$ are clear from the context.

The cost of a circulation $f$ under the cost function $c$ is given by ${\sum }_{a\in A}f(a)c(a)+{\sum }_{e\in E}|f(e)|c(e)$. A feasible circulation with the minimum cost is called a min-cost circulation. An edge or arc $e$ is termed fixed if $\mathrm{\ell }(e)=u(e)$. An edge $e$ is considered unconstrained if $\mathrm{\ell }(e)=-\mathrm{\infty }$ and $u(e)=\mathrm{\infty }$. An arc is unconstrained if $\mathrm{\ell }(e)=0$ and $u(e)=\mathrm{\infty }$. The support of $f$, denoted by $\mathrm{supp}(f)$, is defined as $\{e\mid f(e)\ne 0,e\in E\cup A\}$.

For a circulation $f$, we use $[f]$ to denote the set of all tours corresponding to $f$ in a natural way: a tour where $f(e)$ represents the difference between the number of times the tour traverses the edge in the forward and backward directions. The set $[f]$ is referred to as a homology class, and two tours in $[f]$ are said to be homologically equivalent.

For the SCP problem with input graph $G=(V,E\cup R)$, the corresponding circulation problem is a circulation problem on $G$ where each edge in $E$ is unconstrained, and each arc in $R$ is fixed with a flow value of 1. The costs of the edges and arcs remain the same as in the original SCP formulation. The SCP problem and the corresponding circulation problem are not equivalent. A gap exists due to connectivity. A tour must be connected, but the corresponding circulation does not guarantee connectivity by simply looking at the support.

For an undirected graph $G=(V,E)$, the functions $f:E\to \mathbb{Z}$ can be represented as vectors in ${\mathbb{Z}}^E$. The space of circulations is a submodule of ${\mathbb{Z}}^E$, known as the integral cycle space, or simply the cycle space. If the graph is connected, the dimension of the cycle space is $|E|-|V|+1$ [3]. This value, $|E|-|V|+1$, is referred to as the cycle rank. Any two topologically equivalent graphs have the same cycle rank.

A circulation $f$ is called a cycle flow if $\mathrm{supp}(f)$ forms an undirected cycle (after considering all edges as undirected). A cycle flow $f$ is a unit cycle flow if $|f(e)|=1$ for all $e\in \mathrm{supp}(f)$. Let $T$ be a spanning tree in $G$. For each edge $uv\notin T$, the fundamental cycle $C_{uv}$ with respect to $T$ is defined as the unit cycle flow that traverses $uv$ in the forward direction and then traces back from $v$ to $u$ along the unique path in $T$. Note that it is possible that some fundamental cycles have a negative flow value on some edges.

The fundamental cycles with respect to $T$ form a basis for the cycle space. That is, let $C_1,\mathrm{\dots },C_r$ be the fundamental cycles with respect to $T$. Then, for any circulation $f$, we have $f={\sum }_{i=1}^r{\lambda }_i{C}_i$ for some coefficients $\lambda \in {\mathbb{Z}}^r$ [15].

Atallah and Kosaraju solved SCP$(H)$ for the cases where $H$ is either a path or a cycle [2]. Using a more modern and general perspective, their approach can be summarized as a three-step algorithm:

1. 1.

   Find a min-cost circulation $f$ in the corresponding circulation problem.

2. 2.

   Find all circulations $g$ such that ${\Vert f-g\Vert }_{\mathrm{\infty }}\le b$ for some bound $b$.

3. 3.

   Find a min-cost tour in each homology class $[g]$, and return the minimum.

It is crucial that $H$ is a path or a cycle, as their technique in each of these steps relies heavily on this property. We describe how to eliminate such a restriction.

In the first step, finding a min-cost circulation when $H$ is either a path or a cycle was solved through an ad-hoc process in linear time. On a path, such a circulation is unique. For a cycle, they fix a flow sent along a particular edge, and then the circulation becomes unique. Alternatively, one can use a min-cost flow algorithm on a one-tree [13], which can also obtain a linear time algorithm. We show that min-cost circulation can be solved in linear time for arbitrary fixed $H$ by reducing it to a problem similar to linear programming in a fixed dimension. See Subsection 4.1.

For the second step, Atallah and Kosaraju showed that $b=0$ suffices for paths, leading to an optimal algorithm. In the same paper, they established a bound of $b=p$ for cycles, where $p$ is the number of requests. Fortunately, their technique does not explicitly generate all circulations, but instead searches through them using a binary search, implemented alongside step 3. Later, Frederickson improved the bound on $b$ to $1$ by squeezing the value of the min-cost tour between two one-dimensional functions, thereby achieving the desired proximity result [9]. This improvement not only made the algorithm faster but also allowed steps 2 and 3 to be separated.

In general, it is not difficult to argue that for any $H$, a bound of $b=p$ suffices. The number of feasible circulations in step 2 would then be $O({(2p+1)}^r)$, where $r$ is the cycle rank of $B$. This is too large to yield a fast algorithm. Unfortunately, Frederickson’s technique does not generalize to graphs with higher cycle ranks. Therefore, we need a proximity theorem for arbitrary graphs. This is the most technical part of our paper. As we will show in Section 3, a bound of $b=r$ suffices. The algorithm to explicitly enumerate $O({(2r+1)}^r)$ such circulations will be described in Subsection 4.2.

For the third step, Atallah and Kosaraju found the min-cost tour in a homology class by computing a minimum spanning tree in an auxiliary graph. The auxiliary graph is constructed by contracting edges in the circulation that defines the homology class. Once again, computing a minimum spanning tree suffices only because $H$ is a path or a cycle. In Subsection 4.3, we show that the correct problem to solve is minimum Steiner tree in the auxiliary graph, which is an NP-hard problem in general. However, since the number of Steiner branch vertices depends only on $H$, the running time remains efficient.

For a graph or mixed graph $G$, let $G^{\prime }=\text{sym}(G)$ be the directed graph obtained by replacing each edge with two opposing arcs. Interestingly, we prove the proximity result by considering circulations in the residual graph of $G^{\prime }$, as it is easier to reason about.

The residual graph for a given directed graph $G$ with lower and upper bounds $\mathrm{\ell }$ and $u$, and a feasible circulation $f$, is the directed graph $G_f$ along with new lower and upper bounds ${\mathrm{\ell }}_f$ and $u_f$. For each arc $a\in A$, define $u_f(a)=u(a)-f(a)$ and ${\mathrm{\ell }}_f(a)=\mathrm{\ell }(a)-f(a)$. The residual graph $G_f$ consists of all arcs for which either $u_f(a)\ne 0$ or ${\mathrm{\ell }}_f(a)\ne 0$. Note that the lower bounds in the residual graph do not have to be non-negative. However, ${\mathrm{\ell }}_f(a)\le 0\le u_f(a)$ is always satisfied, meaning that the zero circulation is always feasible. The fixed arcs in the original graph do not appear in the residual graph, so the complexity of the residual graph can be much smaller than the original graph.

One can observe that the SCP can be reduced to a min-cost connected circulation problem on $G^{\prime }=(V,A\cup R)=\text{sym}(G)$. Here, $A$ are the arcs obtained from symmetrizing $E$. For arcs in $A$, the lower bound is $0$ and the upper bound is infinity. The cost of each arc is the cost of the corresponding edge. For arcs in $R$, both the lower bound and upper bound are $1$. If $f^{\prime }$ is a min-cost connected circulation in $G^{\prime }$, then it corresponds to a min-cost tour of the same cost in $G$.

In this section, we bound the number of elementary circulations in a graph using its cycle rank.

The idea is to show that for an elementary circulation $f$, we have ${\Vert f\Vert }_{\mathrm{\infty }}\le r$, where $r$ is the cycle rank, by expressing the circulation as the sum of $r$ cycle flows. We then use the fact that no flow traverses a cycle more than once to establish the desired bound.

However, a naive decomposition might result in a cycle flow with values greater than $2$, even though the overall circulation remains elementary due to cancellations.

To avoid this issue, we transition to non-negative circulations, ensuring that everything we analyze is non-negative. This simplifies the argument, as it prevents flow cancellations on edges when summing flows around cycles.

First, we strengthen the well-known flow decomposition theorem for circulations, which typically states that a circulation can be decomposed into $m$ cycle flows, where $m$ is the number of edges [19]. We show that this can be improved to $r$, the cycle rank of the graph.

Recall that we are interested in finding the min-cost circulation $f$ of $G=(V,E\cup R)$, where $f(a)=1$ for all $a\in R$. The min-cost circulation problem was shown to be solvable in $m^{1+o(1)}$ time, where $m$ is the number of edges in the graph [5]. In our case, the graph has $p+m$ edges. The min-cost flow algorithm on a one-tree gives a linear time algorithm for the special case when the base graph have cycle rank $1$ [13]. We can show that there is a linear time algorithm for base graphs with fixed cycle rank.

In this section, we show how to generate all circulations that are close to the min-cost circulation in terms of the $L_{\mathrm{\infty }}$ norm.

Recall that we are interested in finding the min-cost tour in the homology class $[f]$ for some given circulation $f$ in $G=(V,E\cup R)$, where $f(a)=1$ for $a\in R$.

If $f$ is already connected, then we are done, as we can find a tour that uses each edge $e$ exactly $|f(e)|$ times. Otherwise, we need to find a tour in $[f]$. Note that in addition to the edges in $\mathrm{supp}(f)$, some extra edges might need to be used by the tour. Naturally, this would look like a Steiner Asymmetric Traveling Salesman Problem (ATSP), defined as finding the shortest tour in a directed graph that visits each terminal vertex at least once, which is even harder to work with than ATSP. However, because we are restricting the tour to be in $[f]$, this limits the kinds of edges we add to the tour: Specifically, these are edges outside $\mathrm{supp}(f)$ that must be traversed both forward and backward exactly once.

To address this, we take $G$ and contract each connected component of $\mathrm{supp}(f)$ into a single vertex. Let the resulting graph be $B^{\prime }$. Note that only edges in $E$ might remain, as all arcs in $R$ have been contracted. Therefore, $B^{\prime }$ is a graph instead of a mixed graph. Moreover, we change the weight of the edges to twice their original cost since each edge would be traversed once forward and once backward. We then reduce the problem to the minimum Steiner tree problem.

For a graph $G=(V,E)$ with a set of terminal vertices $T\subseteq V$, the vertices in $V\setminus T$ are called Steiner vertices. A Steiner tree is a tree that contains all the vertices in $T$. The minimum Steiner tree with respect to a weight function $w:E\to {ℝ}^{+}$ is a Steiner tree of minimum weight.

We are interested in solving the minimum Steiner tree problem on $B^{\prime }$, where the terminals are the contracted vertices. This would give us the minimum set of extra edges the tour must traverse to be connected. The minimum Steiner tree problem is NP-hard in general, but note that $B^{\prime }$ has only a bounded number of Steiner branch vertices. The number of Steiner branch vertices in $B^{\prime }$ is at most the number of branch vertices in $B$. Indeed, the contracted vertices are not Steiner vertices, so all Steiner branch vertices must be branch vertices in $B$. The Steiner vertices of degree $1$ and $2$ can be preprocessed away, so only Steiner branch vertices remain [7]. Hence, the minimum Steiner tree can be solved in $O(2^k\mathrm{MST}(m))$ time for a graph containing $k$ Steiner branch vertices and $m$ edges [12].

Since $B^{\prime }$ can have at most $m$ edges, the minimum Steiner tree in $B^{\prime }$ can be found in $O(2^k\mathrm{MST}(m))$ time. This leads us to the following theorem.

Combining all the components, we obtain the desired algorithm as described in Figure 2. We are now ready to prove our main theorem.