F IXED -PARAMETER A LGORITHMS FOR R ECTILINEAR
S TEINER TREE AND R ECTILINEAR T RAVELING
S ALESMAN P ROBLEM IN THE PLANE

arXiv:1512.06649v3 [cs.DS] 23 Feb 2017

Hadrien Cambazard and Nicolas Catusse?
Univ. Grenoble Alpes, G-SCOP, F-38000 Grenoble, France
CNRS, G-SCOP, F-38000 Grenoble, France
{hadrien.cambazard|nicolas.catusse}@grenoble-inp.fr

Abstract. Given a set P of n points with their pairwise distances, the traveling
salesman problem (TSP) asks for a shortest tour that visits each point exactly
once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the l1 distance. In this paper, a fixedparameter algorithm for the Rectilinear TSP is presented and relies on techniques
for solving TSP onbounded-treewidth graphs. It proves that the problem can be
solved in O nh7h where h ≤ n denotes the number of horizontal lines containing the points of P . The same technique can be directly applied to the problem
of finding a shortest rectilinear Steiner tree that interconnects the points of P
providing a O nh5h time complexity. Both bounds improve over the best time
bounds known for these problems.

1

Introduction

Given a set P of n points with their pairwise distances, the Traveling Salesman Problem (TSP) asks for a shortest tour that visits each point exactly once. We consider the
Rectilinear instances of the TSP (RTSP), i.e. TSP instances where the distance between
two points is the sum of the differences of their x- and y-coordinates. This metric is
commonly known as the l1 distance, the Manhattan distance or the city-block metric.
We are also interested in the rectilinear variant of the minimum Steiner tree problem
(RST). The RST problem is to find a shortest Steiner tree that interconnects the points
of P using vertical and horizontal lines. A number of studies have considered the rectilinear Steiner tree in the past, motivated by the applications to wire printed circuits.
Let h (resp. v) be the number of horizontal (resp. vertical) straight lines that contain the
points of P . Note that without loss of generality, we can assume that h ≤ v. We present
fixed-paramete r algorithms using h as a parameter for RTSP and RST. Similarly to the
RST, the RTSP is expressed as a Steiner (also called Subset) TSP in a planar grid-graph
of pathwidth equal to h. Our approach is then based on standard techniques for solving
TSP and Steiner tree on bounded-treewidth graphs [5, 9]. A number of existing results
exploiting planarity or bounded treewidth/pathwidth can thus be applied and will be
?

Nicolas Catusse is partially supported by LabEx PERSYVAL-Lab (ANR -11- LABX -0025) and
a grant PEPS JCJC from CNRS, entitled OTARI.

reviewed in this introduction.
The contribution of this paper is a refined complexity
analysis showing
that RTSP


and RST can be solved respectively in time O nh7h and O nh5h . A specific structure called non-crossing partitions lies at the core of the complexity of problems that
involve a global connectivity constraint in planar graphs [4, 12, 11]. Moreover the number of such non-crossing partitions relates to Catalan numbers which have been used in
the past to establish complexity results.


The O nh7h and O nh5h runtimes improve over the bounds known from dedicated approaches [7, 15], dynamic programming algorithms dedicated to weighted problems in planar graphs [12, 20] or the recent and more generic framework of [6]. The algorithm proposed for RTSP generalizes the approaches designed for specific placement
of the points in the context of warehouses [24, 25]. The parameter is meaningful in a
number of routing applications and the resulting time complexity is low enough for the
algorithm to be used in practice as demonstrated by the experimental evaluation.
Firstly, the existing results about RTSP will be reviewed. The NP-completeness
proof by Itai, Papadimitriou, and Szwarcfiter [19] for the Euclidean TSP immediately
implies the NP-completeness of the following type of TSP: points are in R2 and distances are measured according to a norm with a centrally symmetric unit ball. In particular, the TSP with Manhattan distances is NP-complete. A similar parameter to h has
been used by Rote [26]. When the points of P lie on a small number h of parallel lines
in the plane, Rote shows that the Euclidian TSP problem can be solved with a dynamic
programming approach in time O(nh ). Moreover, this algorithm can be applied with
the l1 metric. Note also that a variant of the RTSP where the objective is to minimize
the number of bends has been widely studied and in particular using fixed-parameter
tractability [13]. A specific case of the RTSP is considered by Ratliff and Rosenthal’s
[24] to compute the shortest order picking tour in a warehouse with rectangular layout. Warehouses are usually designed with multiple parallel vertical aisles and multiple
horizontal cross aisles. The algorithm of [24] solves the problem when the warehouse
does not have any cross aisles (i.e. a case similar to h = 2) and Roodbergen and De
Koster [25] extend this algorithm to handle the case of one single cross aisle (i.e. a case
similar to h = 3). Beyond the RTSP, many results related to Euclidian or Subset/Steiner
TSP are relevant to this paper. The Polynomial-Time Approximation Scheme (PTAS)
for the Euclidean TSP, proposed by Arora [3], can be applied with any geometric norm,

such as lp for p ≥ 1 or other Minkowski norms. It provides, for any c > 1, a 1 + 1c approximation running in time√O(n(log n)O(c) ). A number of subexponential exact
algorithms of running time 2O( nlog(n)) have been designed independently for the Euclidian TSP by taking advantage of planar
separators [18]. A recent result inheriting
√
from this line of research is a O(29.8594 n ) for the TSP on planar graphs proposed by
Dorn et al. [12] and exploiting non-crossing partitions. Such partitions are at the heart
of the present paper and have been used already by Arora et al. [4] to achieve better approximation schemes. The link between non-crossing partitions and the Catalan number
has been investigated further by Dorn et al. [11] when applying dynamic programming
to H-minor-free graphs. A recent parametrized algorithm was also proposed in [20] for

the Subset TSP (also referred to as Steiner TSP) on planar graphs with distances no
greater than W. The problem is to find the shortest
closed walk visiting all vertices of a
√
subset of k vertices. It is solved by [20] in (2 klog(k) + W )nO(1) . Since we recast the
RTSP as a Steiner TSP in a graph of√hv vertices where a subset of n of them must be
visited, the result of [20] yields a (2 nlog(n) + W )(hv)O(1) algorithm which is more
general but incomparable to the complexity proposed in the present paper.
The Steiner tree problem has been extensively studied and exact algorithms for the
rectilinear variant have been proposed. An exact approach for h = 2 is proposed by [2]
in 1977 and can be generalized for higher values of h. It can be shown that the resulting
algorithm have a time complexity of O(n16h ) (see [7]). The algorithm is implemented
by Ganley and Cohoon [16] but the high time complexity limits its applicability. A
second exact approach based on dynamic programming is later proposed by [7] with a
O(nh3 10h ) time complexity. Arora also proposed a PTAS for the Steiner tree problem
in his
√ paper dedicated to TSP [3]. Similarly to TSP, a subexponential algorithm with a
2O( nlog(n)) runtime has been recently designed [15].
It also worth mentioning the work of Bodlaender et al. [6] which addresses a wide
range of graph problems with bounded treewidth tw and a global connectivity property
such as the Hamiltonian Cycle, Steiner tree or Traveling Salesman problems. It was not
known for a long time how to improve the twtw nO(1) time complexity of the known
dynamic programming approaches taking advantage of a bounded treewidth tw of the
underlying graph. The rank based approach proposed in [6] however provides algorithms with a ctw nO(1) time complexity, where c is a small constant, for both weighted
and counting versions of these problems. In particular, the Steiner Tree can be solved
in n(1 + 2w )h hO(1) where w is the matrix multiplication exponent (the best known
upper bound for w is currently 2.3727 [30]). We believe that the use of the rank based
approach for the Steiner TSP would lead to a n(1 + 2w+1 )h hO(1) runtime (the details
are in Section 4) and that the improvement obtained by [10] for TSP is not directly
applicable. Both runtimes thus remain improved by our dedicated analysis.
In section 2, we present a dynamic programming approach for the RTSP by describing the possible states, transitions, and the main algorithm (Section 2.3) whereas
Section 2.4 deals with the complexity analysis of the algorithm. Section 3 follows the
same outline for the RST. Section 4 is focused on the comparison with the rank based
technique. Some experimental results for both problems are presented in Section 5 followed by concluding remarks in section 6.

2

A Fixed-parameter algorithm for the Rectilinear TSP

As above, let P denote the given set of points in the plane. The Hanan grid Γ (P )
is the set of segments obtained by constructing vertical and horizontal lines through
each point of P . Recall that h and v denote the number of horizontal and vertical lines
of Γ (P ). Fig. 1 shows an instance where |P | = 5 and the corresponding Hanan grid
Γ (P ). Note that, for all the figures, the points of P are indicated by circled black dots.
Let l1 (p1 , p2 ) be the l1 distance between two points p1 and p2 . Let define the undirected graph G = (V, E) by associating a vertex to each intersection of Γ (P ) and two
parallel edges for each segment of Γ (P ), with length equal to the l1 distance between

the intersections (see Fig. 2). We denote by vij with i ∈ [1, h] and j ∈ [1, v] the vertex
at the intersection between horizontal line i and vertical line j. The points of P are thus
related to some of the vertices of G and we have P ⊆ V .
The problem is to find a shortest tour in G, visiting all points of P . The TSP problem
is thus solved as a Steiner TSP problem on G. The Steiner TSP is a variant of TSP
where the graph is not complete, only a subset of the vertices must be visited by the
salesman, vertices may be visited more than once and edges may be traversed more
than once [22]. Any optimal tour in G visiting all points of P i.e. an optimal solution
of the Steiner TSP problem where P is the set of mandatory vertices, is also an optimal
solution of the rectilinear TSP problem. The points (vertices) of V − P can be used
to change direction and can lie on a rectilinear path connecting two vertices of P . We
will show that G always contains an optimal solution of the original rectilinear TSP
problem.
Notice that we do not need to consider a directed graph, i.e. G is undirected, because
the algorithm builds a shortest tour subgraph that can be directed as a post-processing
step. A subgraph T of G that contains all points P will be called a tour subgraph
if there is an orientation of the edges that is a tour in which every edge of T is used
exactly once (an order-picking tour in [24]). Fig. 3 and 4 show a tour subgraph and a
possible orientation. The following characterization of a tour subgraph, given in [24],
is a specialization of a well known theorem on Eulerian graphs (e.g., see Christofides
[8]):
Lemma 1. (adapted from [24]) A subtour T ⊂ G is a tour subgraph if and only if:
(a) All vertices of P belong to the vertices of T ;
(b) T is connected;
(c) every vertex in T has an even degree.
The tour subgraph of Fig. 3 is connected and has 3 vertices of degree 4. Note that
parallel edges can be used in a tour subgraph. From any subgraph that is known to be
a tour subgraph, we can easily determine an oriented TSP-tour by using any algorithm
for finding an Eulerian cycle. Therefore we will focus on finding a minimum length
tour subgraph. Let’s now show that an optimal solution of the Steiner TSP problem in
G provides an optimal solution of the original RTSP problem.

Fig. 1. The Hanan grid Γ (P )

Fig. 2. The graph G

Lemma 2. Let l∗ be the length of an optimal solution for the RTSP problem. There
exists an optimal tour subgraph in G of length l∗ .
Proof. Consider an optimal ordering of P (giving a solution of distance l∗ ) and a tour
in G obtained by following a shortest path in G between consecutive points of the
ordering. Firstly, Ratliff shows that a minimum length tour subgraph contains no more
than two edges between any pair of vertices [24]. So the tour subgraph is feasible since
it does not use an edge more once. Secondly, it has a length equals to l∗ since G contains
a shortest rectilinear path between each pair of points.

The algorithm builds a tour subgraph by completing a partial tour subgraph.
Definition 1. For any subgraph L ⊂ G; a subgraph T ⊂ L is a L partial tour subgraph if there exists a subgraph F ⊂ G − L such that T ∪ F is a tour subgraph of
G.
We consider L partial tour subgraphs defined by a given horizontal line i and a given
vertical line j and refer to them as Lij partial tour subgraphs. Let Lij be the induced
subgraph of G consisting of vertices located in the rectangles [1, j] × [1, i] and [1, j −
1] × [i + 1, h]. Fig. 5 shows L4,5 in a dark gray area. L4,5 contains the vertices in the
rectangles [1, 5] × [1, 4] and [1, 4] × [5, 7] since h = 7. Fig. 5 shows also a L4,5 partial
tour subgraph (black lines) since we can complet it (dashed lines) to obtain a complete
tour subgraph of G.
The right border of Lij is denoted Rij and defined as the subset of the h rightmost
vertices of Lij for each horizontal line. Fig. 5 represents the vertices of R4,5 by squares
inside the dark gray area as opposed to the light gray area representing L4,5 .
The rationale for the dynamic programming approach is the following: an optimal
subtour consistent with R4,5 consists of the optimal partial tour for the vertices to the
left of R4,5 combined to the optimal partial tour for the vertices to the right of R4,5 .
The two restricted problems are made independent if enough information, namely the
degree parity and connected components, is known about the vertices of R4,5 .
The algorithm will thus start with the initial state defined as the first partial subtour
L1,1 . It extends the partial subtour Lij by adding vertical/horizontal edges between
vertices iteratively. At the end, it has built the Lhv partial tour subgraphs, which are all

Fig. 3. A tour subgraph

Fig. 4. A directed tour subgraph

7
6

C4,5

R4,5

5
v4,5

4
L4,5

3
2
1
1

2 3

4

5

6

7 8

9

Fig. 5. Hanan grid Γ (P ) with L4,5 inside the light gray area and R4,5 inside the dark gray area.
The vertices of R4,5 are represented by squares. The black edges represent a L4,5 partial tour
subgraph and the dashed edges represent one possible completion.

no zero-degree
{(E, E, E), (1, 2, 3)}
{(U, U, E), (1, 1, 2)}
{(E, E, E), (1, 1, 2)}
{(E, U, U ), (1, 2, 2)}
{(E, E, E), (1, 2, 2)}
{(U, E, U ), (1, 2, 1)}
{(E, E, E), (1, 2, 1)}
{(U, U, E), (1, 1, 1)}
{(E, U, U ), (1, 1, 1)}
{(U, E, U ), (1, 1, 1)}
{(E, E, E), (1, 1, 1)}

1 zero-degree
2 zero-degree
3 zero-degree
{(E, E, 0), (1, 2, −)} {(E, 0, 0), (1, −, −)} {(0, 0, 0), (−, −, −)}
{(0, E, E), (−, 1, 2)} {(0, E, 0), (−, 1, −)}
{(E, 0, E), (1, −, 2)} {(0, 0, E), (−, −, 1)}
{(U, U, 0), (1, 1, −)}
{(E, E, 0), (1, 1, −)}
{(0, U, U ), (−, 1, 1)}
{(0, E, E), (−, 1, 1)}
{(U, 0, U ), (1, −, 1)}
{(E, 0, E), (1, −, 1)}

Table 1. States of Ω(3) (for RTSP) sorted by number of zero-degree vertices.

the possible tour subgraphs, so that a shortest can be identified as an optimal solution.
We now describe the possible states and transitions between them.
2.1

States.

Two Lij partial tour subgraphs are equivalent if any completion of one partial tour subgraph is a completion for the other. The equivalent classes of Lij partial tour subgraphs
can be characterized by some features of the vertices in Rij . Let’s go back to Fig. 5 and
notice that the L4,5 partial tour subgraph is made of two connected components.
So, to characterize the equivalent classes of Lij partial tour subgraphs, we need the
degree parity of each vertex of Rij and distribution of vertices of Rij over distinct con-

nected components. Two vertices of Rij can be connected with 0, an odd, or an even
number of paths and the total number of incident paths determines the parity 0, U, or
E of the vertex. We use the same notation as [24] to describe degree parities: even =
E, odd = U (uneven) and zero = 0. Connected components are described by their indices or ”-” for a zero degree. An equivalent class is related to a state of the dynamic
program. In the following, such a state ω is denoted ω = {(x1 , . . . , xh ), (c1 , . . . , ch )}
where xi ∈ {U, E, 0} and ci are respectively the parity label and the connected component of the i-th vertex of ω. Moreover Cj denotes the set of vertices belonging to
connected component number j so that Cj = {i|ci = j, ∀i = 1 . . . h}. For example
the equivalence class of L4,5 in Fig. 5 is described by the the following pair of vectors
{(E, E, E, U, U, 0, 0), (1, 1, 1, 2, 2, −, −)} and we have C1 = {1, 2, 3}, C2 = {4, 5}.
In this example, the vertices belong to two distinct connected components (of the corresponding class of tour subgraphs). In the first component (index 1), the three vertices
are connected to an even number of paths and in the second component, the two vertices
are connected to an odd number of paths.
We denote by Ω(h) the set of all possible states for h vertices in the same Rij , and
Ω the set of all states of the dynamic program. Table 1 lists all the possible states of
Ω(3). We summarize a number of key observations about valid states that are needed
to fully understand the algorithm and to establish its complexity.
Consider a connected component j with a single vertex i so that Cj = {i}. Such a
vertex is referred as a vertex with a self-loop.
Lemma 3. A vertex with a self-loop has degree 2.
Proof. The degree of i is not zero since it belongs to a connected component. The only
possible connection to vertex i is from the vertex located to its left and it can have at
most 2 edges. It has exactly 2 edges since the degree must be even, see Theorem 1. 
An example of a self-loop in a state is shown Fig. 6.
U, 1
d

0, −

π1

E, 1
self-loop
U, 2
π2
U, 2

Fig. 6. Example of a self-loop: a vertex with
two incoming edges and alone in its connected
component.

U, 2
c
U, 1
b
U, 2
a

Fig. 7. Example of an inconsistent labelling of
the connected components. π1 and π2 must
cross so that a,b,c and d must belong to the
same connected component.

vi+1,j vi+1,j vi+1,j vi,j

vi,j+1

vi,j

vi,j+1

vi,j

vi,j+1

vi,j

vi,j

vi,j

Fig. 8. Vertical and horizontal transitions

Lemma 4. A connected component of a state in Ω(h) has zero or an even number of
vertices labeled with U .
Proof. By Lemma 1, vertices of Li,j − Ri,j have an even degree. So in a state, only
vertices of Ri,j can have an odd degree. Since in a graph, the number of vertices of odd
degree is even, a state has zero or an even number of vertices with an odd degree. 
Lemma 5. The partition describing the connected components {C1 , . . . , Ck } of a state
is a non-crossing partition, i.e. if a < b < c < d (ordered from bottom to top) and
a, c ∈ Ci and b, d ∈ Cj , then i = j.
Proof. Since vertices a and c belong to the same component Ci , there is a path π1 from
a to c. Similarly there is another path π2 from b to d (see Fig. 7). Thus, π1 and π2 must
cross, the intersection point is a vertex in both π1 and π2 , thus a, b, c and d belong to
the same connected component.

2.2

Transitions.

There are two types of transitions between states: vertical and horizontal transitions,
corresponding to the addition of vertical or horizontal edges of Γ (P ) (see Fig. 8).
In an optimal tour subgraph, two adjacent vertices in G can be connected by one or
two edges, or not connected. The cost of a transition is the sum of the lengths of the
edges. For instance (see Fig. 9), the addition of a single vertical edge (v2,j , v3,j ) to state
{(U, U, E), (2, 2, 1)} leads to the state {(U, E, U ), (1, 1, 1)}. Similarly, the addition of
a double horizontal edge (v1,j−1 , v1,j ) to state {(0, E, 0), (−, 1, −)}, leads to the state
{(E, E, 0), (2, 1, −)}.
2.3

Algorithm.

Algorithm 1 processes the edges of Γ (P ) from bottom to top and then from left to
right (line 3): the vertical edges (vi,0 , vi+1,0 ), then the horizontal edges (vi,0 , vi,1 ),
then the vertical edges (vi,1 , vi+1,1 ) and so on. From any state (line 4), three possible
transitions are considered (line 5): no edge, a single one or a double one. All the states
obtained after adding l transitions belong to the l-th layer and the dynamic programming
algorithm can be seen as a shortest path algorithm in a layered graph (see Fig. 10). We

E, 1

U, 1

0, −

0, −

U, 2

E, 1

E, 1

E, 1

U, 2
U, 1
j
j
adding vertical edge (v2,j , v3,j )

0, −
E, 2
j
j
adding double horizontal edge (v1,j−1 , v1,j )

Fig. 9. Examples of two transitions: using a single vertical edge (left picture) and using a double
horizontal edge (right picture).

denote by T (ω, l) the value of the shortest path to reach state ω located on layer l. Lines
6-13 updates the possible states of the next layer (l+1) by extending the considered state
ω of layer l with the considered transition tr. The new state ω 0 might not be a valid tour
subgraph and it is checked line 7. Moreover, an existing shortest partial tour subgraph
might be already known to reach ω 0 and this is checked line 9.

Algorithm 1 Dynamic Programming algorithm for the Rectilinear TSP
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

ω0 ← {(0, . . . , 0), (−, . . . , −)}; T (w0 , 0) = 0; L0 ← {w0 }
l←0
for each edges of e ∈ Γ (P ) from bottom to top and from left to right do
for each state ω ∈ Ll do
for each possible transitions (zero, one or two edges) tr for e do
ω 0 ← ω + tr
if check(ω 0 , l + 1) then
if ω 0 ∈ Ll+1 then
if T (ω 0 , l + 1) < T (ω, l) + length(tr) then
T (ω 0 , l + 1) ← T (ω, l) + length(tr)
else
T (ω 0 , l + 1) ← T (ω, l) + length(tr)
Ll+1 ← Ll+1 ∪ {ω 0 }
l ←l+1
wopt ← argminω∈Lhv T (ω, l∗ ) where l∗ is the last layer.
return wopt

An illustrative execution of the algorithm is shown Fig. 10, where a particular path
is outlined demonstrating the relation between states and partial tours. The algorithm
is a shortest path algorithm in the graph of Fig. 10 where there are O(hv) layers (the
maximum number of possible transitions), at most |Ω(h)| nodes in each layer and at
most three outgoing arcs from any node.

l=1

l=2

0
0
0

0
E
E

0

1

0

--

U
U
E
1
1
1

0
E
E

-

1
1

-

1
1

0

0

0

0

0
U
U

U
U
0
1
1
1

-1

--

0
0
0

l=3
0

E
E
E
1
1
1

U
U
U
1
1
1

0

0

U
U
E
1
1
1

Fig. 10. Example of the graph underlying the dynamic programming algorithm. Each layer is
identified with a value of l. Three transitions are possible from each state. The partial toursubgraph obtained by following the black path is shown on the bottom right corner.

Let’s give more details about line 7 and infeasible or suboptimal states. The following conditions comes directly from Theorem 1 and must be satisfied by the states to
ensure the algorithm computes a valid tour subgraph:
1. A non-zero degree vertex has an even number of incident edges in any state.
2. A vertex belonging to P has a positive degree in any state.
3. A state located on the last layer must have a single connected component since the
tour subgraph must be connected.
Conditions 1 and 2 can be checked after the last step involving an incident edge of
the vertex and condition 3 after all edges of Γ (P ) have been processed. These conditions are evaluated when considering a state ω for layer l (see the call to check(ω, l) line
7 of Algorithm 1) to filter invalid states. Additionally we know that some states cannot
belong to an optimal tour sub-graph. The following simple filtering rule is applied to
speed up the algorithm and rule out some sub-optimal states:
– A vertex vi,j that is not in P can not be solely connected to two parallel edges (this
would create a useless turn back and forth in vi,j ).
2.4

Complexity analysis.

All states of the graph underlying the dynamic program have an out degree of at most
three. The time-complexity of the algorithm solely depends on the number of states.

Since we have O(hv) layers (exactly (h − 1)v + (v − 1)h = 2hv − h − v), we focus
on counting the maximum number of states of a layer. Notice that Figure 10 implies a
total of 3O(hv) states but some of them are identical and we refine the counting in the
present section. The number of possible states made of h possible vertices is denoted by
|Ω(h)|. As an example, Table 1 which enumerates the states belonging to Ω(3) shows
that |Ω(3)| = 24. To compute |Ω(h)|, we proceed as follows:
1. Firstly, we compute |Ωpos (h)|, the number of states with only positive degree vertices (i.e. without vertices of zero-degree). We thus have Ωpos (h) ⊂ Ω(h). We will
show that |Ωpos (h)| is equal to the super Catalan number by using a particular interpretation of the super Catalan number referred to as f 4 in [1]:
fn4 : Number of ways of connecting n points in the plane lying on a horizontal line
by noncrossing edges above the line such that if two edges share an endpoint p,
then p is a left endpoint of both edges. Then color each edge by black or white.
We denote by Ωf 4 (h) the set of configurations described above and establish a bijection between Ωpos (h) and Ωf 4 (h) (Lemma 6). Since fn4 is known to be equal to
the super Catalan number Sn (see [1]), we have |Ωpos (h)| = Sh (Lemma 7).
2. Secondly, we consider the zero-degree vertices to relate |Ω(h)| to the super
 Catalan
numbers (Lemma 8). We can then prove (Theorem 1) that |Ω(h)| = O

√
(4+ 8)h+1

√

(h+1)3

We now start by establishing a bijection between the number of states with vertices
of positive degree and the configurations of f 4 . An example of such a bijection for
h = 3 is given Fig. 11. The 11 states of Ωpos (3) are taken from the first column of table
1 and are matched to the 11 configurations of Ωf 4 (3).
Lemma 6. There is a bijection between Ωpos (h) and Ωf 4 (h).
Proof. Recall that a state ω ∈ Ωpos is denoted ω = {(x1 , . . . , xh ), (c1 , . . . , ch )}. A
state ω 0 ∈ Ωf 4 is described by h consecutive points p1 , . . . , ph on a line and a set of
white/black edges. In the following, pi is the point associated to the i-th vertex of ω.
⇒ We give an injective function from a state ω ∈ Ωpos to a state ω 0 ∈ Ωf 4 . We
built ω 0 as follow. We consider each connected component C of ω consisting of more
than one vertex i.e. of vertices v1 , v2 , . . . vk (cv1 = cv2 = . . . = cvk ). For each vertex
vi ∈ C with i 6= 1, if xvi is U (resp, E) vertex, we add a white (resp, black) edge
between the points pv1 and pvi . A self-loop vertex vi is thus matched to a zero-degree
point pvi .
Firstly ω 0 is unique since the label of xi (E, U or 0) determines the number nw of
white edges incident to pi . Secondly ω 0 is a valid configuration of Ωf 4 . Indeed, in each
connected component the added edges share only vertex pv1 so that two edges in ω 0
can only share their left endpoint. Finally, the edges of ω 0 are non-crossing since they
are incident to vertices belonging to the same connected component of ω (connected
components are indeed non-crossing in ω by Lemma 5).

.

{(E, E, E), (1, 2, 3)}

{(E, E, E), (1, 2, 2)}

{(E, U, U ), (1, 1, 1)}

{(U, U, E), (1, 1, 2)}

{(U, E, U ), (1, 2, 1)}

{(U, E, U ), (1, 1, 1)}

{(E, E, E), (1, 1, 2)}

{(E, E, E), (1, 2, 1)}

{(E, E, E), (1, 1, 1)}

{(E, U, U ), (1, 2, 2)}

{(U, U, E), (1, 1, 1)}

Fig. 11. Example of bijection between Ωpos (3) and Ωf 4 (3).

⇐ We describe now an injective function from a state ω 0 ∈ Ωf 4 to a state ω ∈ Ωpos .
If a point pi is not connected to any edge it is matched to a self-loop vertex so we set
xi to E. If it is connected to at least one white edge we look at the number nw of white
edges connected to pi : we set xi to E if nw is even and to U if nw is uneven. Finally if it
is connected to black edges only, we set it to E. Then, we index connected components
in increasing order and note ”-” if the vertex is a zero degree.
Firstly the corresponding state ω is unique since the parity (U , E or 0) of a vertex
i corresponding to a point pi is uniquely determined by the number and color of the
connected edges to pi . This leads to a unique indexing of the connected components.
Secondly ω is a valid state of Ωpos . We check to this end that the number of U labels in a
connected component of ω satisfies the requirement of Lemma 4. A point pv1 connected
to more than one edge is related to one connected component of ω defined by k vertices:
v1 , v2 , . . . vk . Consider the number nw of white edges connected to v1 . If nw = 0 (only
black edges), we have xv1 = . . . = xvk = E by construction of ω and Lemma 4 is
satisfied. If nw is odd then xv1 = U and an odd number of xvj (j 6= 1) have been set
to U by construction so that the total number of U is even. Similarly if nw is even then
xv1 = E and an even number of of xvj (j 6= 1) have been set to U . In any case, the
number of U is even (or null) in any connected component of ω.

Lemma 7. |Ωpos (h)| = Sh , where Sn is the super Catalan number (see OEIS A001003).
Proof. |Ωpos (h)| = fh4 due to Lemma 6 and fh4 is known (see [1]) to be equal to the
super Catalan number Sh .

We now include the zero-degree vertices in the counting to obtain |Ω(h)|.

Ph
Lemma 8. |Ω(h)| = k=0 hk Sk

Proof. When (h − k) vertices out of h have a zero-degree, there are |Ωpos (k)| ways
to connect the k remaining vertices. This is because vertices with zero-degree are
completely independent from the other vertices. The number of states with exactly
Ph
h
h
(h−k) zero-degree vertices is thus h−k
|Ωpos (k)|. So Hh = k=0 h−k
|Ωpos (k)| =


Ph
P
h
h
h

k=0 k |Ωpos (k)|. By Lemma 7 we end up with Hh =
k=0 k Sk .
The problem boils down to compute a bound on the sequence defined in Lemma 8
and based on the super Catalan numbers.

 √
h+1
√ 8) 3
Theorem 1. |Ω(h)| = O (4+
(h+1)

Proof. First we show that |Ω(h)| = Th+1 where Tn is a specific number defined in
OEIS A118376 1 (see [27]).
Let A(x) and B(x) be the P
generating functions of respectively
Tn and Sn (the super
P
catalan numbers) i.e. A(x) = n≥0 Tn xn and B(x) = n≥0 Sn xn . Closed forms are
√

√

2

2

−8x+1
1−6x+x
and B(x) = 1+x− 4x
known for both functions so that A(x) = 1− 8x
4−4x
x
(see [27]). As a result, we can express A(x) as a composition of B(x) and 1−x
as
x
x
follow A(x) = 1−x B( 1−x ).
We use a result from [21] to compute compositions of generating functions and
adapt the proof of Theorem 8 of [21]:



k X 
k+1
x
x X
x
x
x
B
Sk
A(x) =
=
=
Sk
1−x
1−x
1−x
1−x
1−x
k≥0

Replacing

A(x) =



x
1−x

k+1

by

k≥0

n−1
n≥k+1 n−k−1



P

xn (see [21]) we obtain:

 
 
 


0
1
2
n−1
S0 x +
S0 x2 +
S0 x3 + · · · +
S0 xn + . . .
0
0
0
0
 
 


1
2
n−1
+
S1 x2 +
S1 x3 + · · · +
S1 xn + . . .
1
1
1
 


2
n−1
+
S2 x3 + · · · +
S2 xn + . . .
2
2

...


n−1
+
Sn−1 xn + . . .
n−1
P
Summing the coefficients of xn for n > 0, we get A(x) = n≥0 Tn xn where
Tn =


n 
X
n−1
k=1

1

k−1

Sk−1 =

n−1
X
k0 =0




n−1
Sk0
k0

The interpretation of Tn , which is irrelevant to the proof, is given as the number of all trees of
weight n, where nodes have positive integer weights and the sum of the weights of the children
of a node is equal to the weight of the node.


Ph
h
0
By taking n = h + 1, we can state Th+1 =
k0 =0 k0 Sk so we have, from
Lemma 8, |Ω(h)| = Th+1 . Moreover, we can use the singularitymethod given
 in [14]
(Proposition IV.1 and Theorem V1.1) to show that Th+1 is in O

√
(4+ 8)h+1

√



.

(h+1)3

h
12 3 4 5
6
7
8
9
10
|Ωpos (h)| = Sh 1 3 11 45 197 903 4279 20793 103049 518859
|Ω(h)| = Th+1 2 6 24 112 568 3032 16768 95200 551616 3248704
Table 2. The exact value of the numbers |Ω(h)| and |Ωpos (h)| for h between 1 and 10.


The number of states |Ω(h)| of the dynamic program is thus in O


√
(4+ 8)h+1
√

(h+1)3

.

Table 2 shows the order of magnitude of the numbers involved. Since thereare at most
O(hv) edges to consider, the overall time complexity of algorithm 1 is in O

√
(4+ 8)h+1

√

(h+1)3

hv

assuming that we can check that a state belongs to a layer in constant time (line 9 of
Algorithm 1). For sake of simplicity,
 we highlight n and h only (since v ≤ n) and
simplify the complexity to O hn7h .

3

Fixed-parameter algorithm for Rectilinear Steiner tree.

We now apply the exact same methodology to the Steiner tree problem. We briefly describe how each step is modified to handle the Steiner tree case. Notice that the previous
7
6

C4,5

R4,5

5
v4,5

4
L4,5

3
2
1
1

2 3

4

5

6

7 8

9

Fig. 12. Hanan grid Γ (P ) with L4,5 in the light gray area and R4,5 in the dark gray area. The
black edges represent a L4,5 partial tree and the dashed edges represent one possible completion.



0 zero-degree 1 zero-degree 2 zero-degree 3 zero-degree
(1, 1, 1)
(1, 1, −)
(1, −, −)
(−, −, −)
(1, 1, 2)
(−, 1, 1)
(−, 1, −)
(1, 2, 1)
(1, −, 1)
(−, −, 1)
(1, 2, 2)
(1, 2, −)
(1, 2, 3)
(1, −, 2)
(−, 1, 2)
Table 3. States of Ω(3) for the Steiner Tree.

methodology was described in details for the more complex case of rectilinear TSP and
that it is now merely simplified. For sake of simplicity the notations are kept identical.
We now define the undirected graph G = (V, E) by associating a vertex to each intersection of Γ (P ) and a single edge for each segment of Γ (P ), with length equal to the
l1 distance between the intersections. The L partial tour subgraph become L trees.
Definition 2. For any subgraph L ⊂ G; a tree T ⊂ L is a L partial tree if there exists
a tree F ⊂ G − L such that T ∪ F is a Steiner tree of G.
Figure 12 demontrates a Lij partial tree and its Rij right most frontier. A L45 partial
tree is shown and a possible completion to a complete Steiner tree.
3.1

States and Transitions.

States A state ω is denoted ω = (c1 , . . . , ch ) where ci is the connected component
of the i-th vertex of ω. Connected components are described by their indices or ”” for a zero degree. Notice that the parity of the degree does not need to be stored
anymore. Regarding the degree information, we now only need to know whether the
degree is null or not. This information amounts at checking whether ci 6=”-”. Table 3
gives the possible states for h = 3. For the exact same reason given in section 2.1,
the partition describing the connected components {C1 , . . . , Ck } of a state is a noncrossing partition. Typically, the state representing the equivalent class of L4,5 in Fig. 12
is described by the following vector (1, 1, 1, 2, 2, −, −).
Transitions There are two types of transitions: vertical and horizontal. However, there
is now only two possible configurations for connecting two adjacent vertices of G in an
optimal Steiner tree: zero or one edge.
3.2

Algorithm.

Algorithm 2 gives the pseudo-code where the changes compared to Algorithm 1 are
highlighted by rectangular boxes. The algorithm is only modified lines 1, 5 and 7. The
modification lines 1 and 5 simply account for the new definition of the states and the
restriction of the transitions to two cases (rather than three for the TSP). Removing
infeasible states line 7 amounts at checking that:

Algorithm 2 Dynamic programming algorithm for Steiner Tree
1: ω0 ← (−, . . . , −); T (w0 , 0) = 0; L0 ← {w0 }
2: l ← 0
3: for each edges of e ∈ Γ (P ) from bottom to top and left to right do
4:
for each state ω ∈ Ll do
5:
for each possible transitions (zero or one edge) tr for e do
6:
ω 0 ← ω + tr
7:
if check(ω 0 , l + 1) then
8:
if ω 0 ∈ Ll+1 then
9:
if T (ω 0 , l + 1) < T (ω, l) + length(tr) then
10:
T (ω 0 , l + 1) ← T (ω, l) + length(tr)
11:
else
12:
T (ω 0 , l + 1) ← T (ω, l) + length(tr)
13:
Ll+1 ← Ll+1 ∪ {ω 0 }
14:
l ←l+1
15: wopt ← argminω∈Lhv T (ω, l∗ ) where l∗ is the last layer
16: return wopt

1. A vertex of P have a positive degree
2. The partial tree is connected (all vertices on the last layer belong to the same connected component)
The following rules are also applied to filter sub-optimal or symmetrical states. We
basically restrict the algorithm to identify trees that satisfy the following conditions by
following [2, 7]:
1. A vertex vi,j that is not in P can not be connected to a single edge (it would create
a useless pendant vertex).
2. Two vertices already in the same connected component can not be directly connected (it would create a cycle which is sub-optimal).
3. Two horizontally (resp. vertically) adjacent vertices vi,j anf vi,j+1 (resp vi,j and
vi+1,j ) that both belongs to P are connected by the direct corresponding edge
(vi,j , vi,j+1 ) (resp. (vi,j , vi+1,j )) [2].
4. Any horizontal/vertical line (sequence of consecutive horizontal/vertical edges)
contains at least one point of P [7].
Conditions (4) is global and requires, for efficient checking, to store whether a vertex in the state is connected to a point of P .
3.3

Complexity.

Any state in the graph underlying the dynamic program has now a degree of at most
two and there are O(hv) layers in the graph. We therefore establish the complexity of
the algorithm by counting the number of possible states |Ω(h)| of a single layer. As an
example, Table 3 enumerates the states belonging to Ω(3) so |Ω(3)| = 15. |Ω(h)| is
computed as follows:

1. Firstly, we show that |Ωpos (h)| is equal to the Catalan number referred to as h5 in
[28]:
h5n : Ways of connecting n points in the plane lying on a horizontal line by noncrossing arcs above the line such that if two arcs share an endpoint p, then p is a
left endpoint of both the arcs.
Since Ωpos (h) is in bijection with Ωh5 (h) and h5n is known to be equal to the Catalan number Cn (see [28]), we have |Ωpos (h)| = Ch .
2. Secondly, we prove that |Ω(h)| is a known sequence related to the Catalan numbers
(see OEIS A007317 [27]).
We now start by establishing a bijection between the number of states with a positive
degree and the configurations of h5 . An example of such a bijection for h = 3 is given
Fig. 13. The 5 states of Ωpos (3) are taken from the first column of Table 3 and are
matched to the 5 configurations of Ωh5 (3).

(1, 1, 1)

(1, 1, 2)

(1, 2, 2)

(1, 2, 3)

(1, 2, 1)

Fig. 13. Example of bijection between Ωpos (3) and Ωh5 (3). Note that at most one single connected component appears for h = 3 when no self-loops are allowed.

Lemma 9. There is a bijection between Ωpos (h) and Ωh5 (h).
Proof. Recall that a state ω ∈ Ωpos is denoted ω = (c1 , . . . , ch ) (see section 2.1). A
state ω 0 ∈ Ωh5 is described by h consecutive points p1 , . . . , ph on a line and a set of
edges. In the following, pi is the point associated to the i-th vertex of ω.
⇒ We give an injective function from a state ω ∈ Ωpos to a state ω 0 ∈ Ωh5 . We
built ω 0 as follow. We consider each connected component C of ω consisting of vertices
v1 , v2 , . . . vk (cv1 = cv2 = . . . = cvk ). For each vertex vi ∈ C with i 6= 1, we add an
edge between the points pv1 and pvi .
By construction ω 0 is unique. ω 0 is a valid configuration of Ωh5 because in each
connected component the added edges share only vertex pv1 so that two edges in ω 0 can
only share their left endpoint. Finally, the edges of ω 0 are noncrossing since they are
incident to vertices belonging to the same connected component of ω.

⇐ We describe now an injective function from a state ω 0 ∈ Ωh5 to a state ω ∈ Ωpos .
The construction is simple, we just index connected components in increasing order.
Firstly the corresponding state ω is unique by construction because there is only one
way to index the connected components. Secondly ω is a valid state of Ωpos because
there is no crossing edges in ω 0 .

Lemma 10. |Ωpos (h)| = Ch , where Cn is the Catalan number (see OEIS A000108).
Proof. |Ωpos (h)| = h5h due to Lemma 9 and h5h is known (see [28]) to be equal to the
Catalan number Ch .


Ph
Lemma 11. |Ω(h)| = k=0 hk Ck
Proof. Identical to proof of Lemma 8.
 h 
Theorem 2. |Ω(h)| = O √5h3
Ph



h
k=0 k



Ck of Lemma 11 is known as the integer sequence A007317
q
(see [27]). Since the generating function of this sequence is 32 − 12 1−5x
1−x , we can use
the singularity method
described
in
[14]
(Proposition
IV.1
and
Theorem
VI.1) to show
 h 
5
that |Ω(h)| = O √h3 .

Proof. The formula

There are O(hv) layers and the number of states in a given layer is in O(5h ) so the
overall time-complexity can be expressed as O(nh5h ) for sake of simplicity.

4

Comparison and relationship to the rank based technique

The planar grid-graph used in this paper has a pathwidth and treewidth of h and the rank
based approach recently proposed by Bodlaender et al. [6] can be directly applied. It is
indeed intended for graph problems with a bounded treewidth/pathwidth and a global
connectivity property such as the Hamiltonian Cycle, Steiner tree or TSP. We focus on
the results obtained via a path decomposition which are stronger for the present paper.
A path decomposition of our grid-graph is made of bags (or separators) of at most h + 1
vertices and the dynamic programming approach must encode some information about
the degree as well as the connected components to which the vertices of a bag belong.
Encoding the connected components involve partitioning the vertices of a bag (one
partition refers to one component) which lead to consider a hh number of partitions. In
a breakthrough result, the authors of [6] show that there exists a representative subset
of these partitions of size 2h . Moreover, given a set A of partitions, it is possible to
0
0
compute this representative subset A ⊆ A (with |A | ≤ 2h ) in time |A|2(w−1)h hO(1)
where w is the matrix multiplication exponent (see Theorem 3.7 of [6]). The number
of partitions generated in the course of the algorithm over a nice path decomposition at
most double from one bag to the next (when an edge is introduced). Thus the algorithm
is always applied on a set of at most 2h+1 partitions and the reduction is performed in
time 2wh hO(1) . We now briefly review the runtimes obtained with this technique for the
two problems considered here. Table 4 gives a summary of the comparison to the best
knowledge of the authors.

Steiner Tree Let us consider a bag of the path decomposition and count
the states shar
ing a given set of k positive degree vertices (there are at most h+1
of
such
sets in the
k
bag). In each set, the number of states relates to the number of partitions of k elements
and is bounded by k k in general. It is here the number of non-crossing partitions counted
by the Catalan numbers as explained in section 3.3 and is thus bounded2 by 4k . Alternatively, applying the rank-based reduction algorithm would reduce the number of such
partitions to 2k and thus reduce the space needed. But, as explained above, the reduction algorithm runs 2wk k O(1) . It follows
that the time complexity to process all states
 wk O(1)
Ph+1
of a bag is bounded by k=1 h+1
2
h
= (1 + 2w )h+1 hO(1) . Overall, considerk
ing that the number of bags is linearly dependent of n, [6] reports a n(1 + 2w )h hO(1)
runtime. By assuming the best case of w = 2, it matches the O(nh5h ) proposed in this
paper. Our approach thus improves over the rank-based technique for the current best
known upper bound of w = 2.3727 but takes advantage of the grid structure in addition
to bounded pathwidth.
Steiner Traveling Salesman We apply the same reasoning to the case of the Steiner
TSP. Consider all the states with a given triple of k0 vertices of zero degree, k1 vertices of odd degree and k2 vertices of even degree. The number of such states relates
to the number of partitions of k1 + k2 elements where at most two vertices of odd
degree belong to the same partition. The rank based approach reduces the number of
such partitions toP2k1 +k2 and leads
the following complexity (using the multinomial
 to
h+1
k0 k1 (k1 +k2 )w O(1)
1 2
h
= (1 + 2w+1 )h+1 hO(1) . The
theorem):
1
k0 ,k1 ,k2
k0 +k1 +k2 =h+1

runtime is thus in n(1 + 2w+1 )h hO(1) and our approach improves over the rank-based
technique even when assuming the best case of w = 2.
The Steiner TSP is not addressed in [6] but a n(2 + 2w/2 )h hO(1) runtime for TSP
is reported. When considering the TSP, the partitions boil down to perfect matchings of
the degree one vertices. It is known from [10] that an improved reduction algorithm can
be applied in this specific case and the number of representative partitions is only 2h/2 .
However, the partitions considered for Steiner TSP are not strictly speaking matchings
since they encompass the even degree vertices even though the odd degree vertices are
paired. Thus the afore-mentionned result of [10] does not seem applicable.

pathwidth h
(2 ≤ w < 2.3727)
Steiner Tree n(1 + 2w )h hO(1)
Steiner TSP n(1 + 2w+1 )h hO(1)
TSP
n(2 + 2w/2 )h hO(1)

Assumptions

pathwidth h grid graph of pathwith h
(w = 2)
n5h hO(1)
O(nh5h )
n9h hO(1)
O(nh7h )
h O(1)
n4 h
-

Table 4. Comparison with the rank based approach.

2

This bound can be proved by using Stirling’sapproximation of n! applied to the explicit for2n
1
mula for the Catalan numbers Cn = n+1
n

5

Experimental results.

We performed simple experiments that serve as a proof of concept and show the scalability of the proposed algorithms. In particular, we show that the rectilinear TSP can be
solved exactly up to h = 8 horizontal lines in practice demonstrating that this algorithm
could be used for real-life picking problems in warehouses. Real-life warehouses often
have a rectangular layout with few cross-aisles (horizontal lines). The experiments were
performed on an Intel Xeon E5-2440 v2 @ 1.9 GHz processor and 32 GB of RAM. The
experiments ran with a memory limit of 8 GB of RAM.

5.1

Results on rectilinear traveling salesman problem.

Pre-processing. To improve the execution time of the algorithm, we observe that any
layout that contain a shortest path π of length l1 (p1 , p2 ) between each pair of vertices
p1 , p2 ∈ P is valid to solve the problem. Finding the distance preserver (1-spanner)
with the minimum number of edges is an NP-complete problem, namely the minimum
Manhattan network problem. In practice, if n is not too big (n ≤ 1000), this preprocessing of the graph improves the total execution time. Table 5 presents the execution
time with and without the computation of the minimum Manhattan network problem
with CPLEX 12.5, using a flow formulation (see [23]). Notice that since any distancepreserver graph can be used to compute the minimum subtour, we can also apply an
approximation algorithm as a pre-process, such as the 2-factor approximation algorithm
[23] or [17] running in O(n log n).

Experiments. Table 5 provides the average and maximum computation time in seconds needed to solve random instances with n ∈ {50, 100, 200} and h varying from
1 to 8. It also reports the maximum number of states obtained on one layer during the
computation. We report the results obtained with algorithm 1 (column no pre-proc) as
well as algorithm 1 extended with the pre-processing step (column pre-proc). We generated 100 random instances for each configuration i.e. for each pair (n, h). Firstly the
algorithm can efficiently handle instances with up to 8 horizontal lines. Secondly, the
increase of time appears to be roughly linear in practice as n increases for a given h.
Finally, the maximum number of states matches exactly the values of |Ω(h)| (see table
2) showing that the worst case is always reached at least on one layer.

5.2

Results on rectilinear Steiner tree.

Table 6 provides the average and maximum computation time in seconds for solving
random instances with n ∈ {50, 100, 200} and h varying from 1 to 11. It also reports the
maximum number of states obtained on one layer during the computation. No particular
pre-processing is applied here. The execution was aborted (due to memory issues) for
the cases denoted by ”-” in the table.

h
1
2
3
4
5
6
7
8

n = 50
n = 100
n = 200
no pre-proc. pre-proc. no pre-proc. pre-proc.
no pre-proc.
pre-proc.
avg. max. avg. max. avg. max. avg. max. avg. max. avg. max.
0 0.01 0 0.01
0
0.02
0 0.01
0
0.02
0
0.02
0 0.01 0
0
0
0.04
0 0.02
0
0.05
0
0.03
0 0.01 0
0
0.01 0.01
0 0.02 0.01 0.02 0.01 0.06
0.02 0.04 0.01 0.01 0.04 0.06 0.02 0.03 0.08 0.11 0.04 0.06
0.12 0.18 0.05 0.08 0.27 0.33 0.12 0.18 0.51 0.65 0.27
0.4
0.76 1.09 0.26 0.42 1.72 2.52 0.78 1.23 3.56 4.84 1.78 2.73
4.67 8.13 1.32 3.38 12.18 16.27 4.93 7.17 25.71 27.89 13.45 15.06
42.18 72.01 7.66 19.74 114.11 136.28 50.78 69.6 242.49 269.56 116.55 131.73

max.
states
2
6
24
112
568
3032
16768
95200

Table 5. Results on RTSP. Execution time in seconds and maximum number of states encountered
on one layer.

h
1
2
3
4
5
6
7
8
9
10
11

n = 50
avg. max.
0 0.01
0 0.01
0 0.01
0 0.01
0.01 0.02
0.03 0.05
0.11 0.19
0.36 0.57
1.2 2.4
4,46 14.05
16,92 52.41

n = 100
avg. max.
0 0.01
0 0.01
0 0.01
0.01 0.01
0.04 0.06
0.15 0.21
0.58 0.98
2.3 3.9
10.74 13.8
49.63 87.13
-

n = 200
avg. max. max. states
0 0.01
2
0 0.01
5
0.01 0.01
15
0.02 0.03
51
0.09 0.12
188
0.36 0.5
731
1.55 2.35
2950
7.16 8.03 12235
33.97 55.2 51822
222616
771128

Table 6. Results on RST. Execution time in seconds and maximum number of states encountered
on one layer.

6

Concluding remarks.

We introduced a new fixed parameter algorithm for the rectilinear TSP that can efficiently solve instances where the points lie on a few number of horizontal
lines. The

complexity analysis proves that RTSP can be solved in time O nh7h . Moreover, this
algorithm is immediately adapted to solve the rectilinear Steiner tree problem with a
O nh5h runtime and improves over the best known fixed parameter algorithm using
the exact same parameter.
As future work, we are investigating how the algorithm for rectilinear TSP can be
used to design very efficient exact methods for the picking problem as well as the joint
order batching and picker routing problem in rectangular warehouses [29].

Acknowledgements
We would like to thank V.V. Kruchinin and D.V. Kruchinin for their help with Theorem
1 and L. Esperet for his explanation of the singularity method.

References
1. T. Mansour A. N. Fan and S. X. M. Pang. Elements of the sets enumerated by super-catalan
numbers.
2. Alfred V. Aho, Michael R. Garey, and Frank K. Hwang. Rectilinear steiner trees: Efficient
special-case algorithms. Networks, 7(1):37–58, 1977.
3. S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and
other geometric problems. Journal of the ACM, 45(5):753–782, 1998.
4. Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej
Woloszyn. A polynomial-time approximation scheme for weighted planar graph tsp. In
Howard J. Karloff, editor, SODA, pages 33–41. ACM/SIAM, 1998.
5. Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 11(1-2):1–21, 1993.
6. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Solving weighted
and counting variants of connectivity problems parameterized by treewidth deterministically
in single exponential time. CoRR, abs/1211.1505, 2012.
7. Marcus Brazil, Doreen A. Thomas, and Jia Feng Weng. Rectilinear Steiner Minimal Trees
on Parallel Lines, pages 27–37. Springer US, Boston, MA, 2000.
8. Nicos Christofides. Graph Theory: An Algorithmic Approach (Computer Science and Applied Mathematics). Academic Press, Inc., Orlando, FL, USA, 1975.
9. William J. Cook and Paul D. Seymour. Tour merging via branch-decomposition. INFORMS
Journal on Computing, 15(3):233–248, 2003.
10. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of
perfect matchings. CoRR, abs/1211.1506, 2012.
11. Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Catalan structures and dynamic
programming in h-minor-free graphs. J. Comput. Syst. Sci., 78(5):1606–1622, 2012.
12. Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, and Fedor V. Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790–
810, 2010.
13. Vladimir Estivill-Castro, Apichat Heednacram, and Francis Suraweera. The rectilinear kbends tsp. In My T. Thai and Sartaj Sahni, editors, COCOON, volume 6196 of Lecture
Notes in Computer Science, pages 264–277. Springer, 2010.
14. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University
Press, 2009.
15. Fedor V. Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.
Subexponential algorithms for rectilinear steiner tree and arborescence problems. In
Sándor P. Fekete and Anna Lubiw, editors, Symposium on Computational Geometry, volume 51 of LIPIcs, pages 39:1–39:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2016.
16. Joseph L. Ganley and James P. Cohoon. Rectilinear steiner trees on a checkerboard. ACM
Trans. Design Autom. Electr. Syst., 1(4):512–522, 1996.
17. Zeyu Guo, He Sun, and Hong Zhu. A fast 2-approximation algorithm for the minimum
manhattan network problem. In Rudolf Fleischer and Jinhui Xu, editors, AAIM, volume
5034 of Lecture Notes in Computer Science, pages 212–223. Springer, 2008.

18. R. Z. Hwang, R. C. Chang, and Richard C. T. Lee. The searching over separators strategy to
solve some np-hard problems in subexponential time. Algorithmica, 9(4):398–423, 1993.
19. Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid
graphs. SIAM J. Comput., 11(4):676–686, 1982.
20. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for subset tsp
on planar graphs. In Chandra Chekuri, editor, SODA, pages 1812–1830. SIAM, 2014.
21. V. V. Kruchinin and D. V. Kruchinin. Composita and its properties. Journal of Analysis and
Number Theroy, 2:1–8, 2014.
22. Adam N. Letchford, Saeideh D. Nasiri, and Dirk Oliver Theis. Compact formulations of the
steiner traveling salesman problem and related problems. European Journal of Operational
Research, 228(1):83–92, 2013.
23. Karim Nouioua. Enveloppes de Pareto et réseaux de Manhattan. PhD thesis, Université de
la Méditerranée, 2005.
24. H. Donald Ratliff and Arnon S. Rosenthal. Order-picking in a rectangular warehouse: A
solvable case of the traveling salesman problem. Operations Research, 31(3):507–521, 1983.
25. Kees Jan Roodbergen and René M. B. M. de Koster. Routing order pickers in a warehouse
with a middle aisle. European Journal of Operational Research, 133(1):32–43, 2001.
26. Günter Rote. The n-line traveling salesman problem. Networks, 22(1):91–108, 1992.
27. N. J. A. Sloane. The on-line encyclopedia of integer sequences. http://oeis.org.
28. R. Stanley. Catalan addendum, 2005.
29. Cristiano Arbex Valle, John E. Beasley, and Alexandre Salles da Cunha. Modelling and
solving the joint order batching and picker routing problem in inventories. In ISCO, 2016.
30. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In
Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New
York, NY, USA, May 19 - 22, 2012, pages 887–898, 2012.

