On subexponential parameterized algorithms for Steiner Tree and
Directed Subset TSP on planar graphs∗
Dániel Marx†

Marcin Pilipczuk‡

Michal Pilipczuk§

arXiv:1707.02190v1 [] 7 Jul 2017

Abstract
There are numerous examples of the so-called “square root phenomenon” in the field of
parameterized algorithms: many of the most fundamental graph problems, parameterized by
some natural parameter k, become significantly simpler when restricted
to planar graphs and
√
in particular the best possible running time is exponential in O( k) instead of O(k) (modulo
standard complexity assumptions). We consider two classic optimization problems parameterized
by the number of terminals. The Steiner Tree problem asks for a minimum-weight tree
connecting a given set of terminals T in an edge-weighted graph. In the Subset Traveling
Salesman problem we are asked to visit all the terminals T by a minimum-weight closed walk.
We investigate the parameterized complexity of these problems in planar graphs, where the
number k = |T | of terminals is regarded as the parameter. Our results are the following:
√

• Subset TSP can be solved in time 2O( k log k) · nO(1) even on edge-weighted directed
planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with
the same running time that worked only on undirected planar graphs with polynomially
large integer weights.
• Assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs
cannot be solved in time 2o(k) · nO(1) , even in the unit-weight setting. This lower bound
makes Steiner Tree the first “genuinely planar” problem (i.e., where the input is only
planar graph with a set of distinguished terminals) for which we can show that the square
root phenomenon does not appear.
√

• Steiner Tree can be solved in time nO( k) ·W on undirected planar graphs with maximum
edge weight W . Note that this result is incomparable to the fact that the problem is known
to be solvable in time 2k · nO(1) even in general graphs.
A direct corollary of the combination of our results for Steiner Tree is that this problem does
not admit a parameter-preserving polynomial kernel on planar graphs unless ETH fails.

∗

This research is a part of projects that have received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme under grant agreements No. 280152 (Dániel
Marx) and 714704 (Marcin Pilipczuk). The research of Michal Pilipczuk is supported by Polish National Science
Centre grant UMO-2013/11/D/ST6/03073. Michal Pilipczuk is also supported by the Foundation for Polish Science
(FNP) via the START stipend programme.
†
Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Hungary,
dmarx@cs.bme.hu
‡
Institute of Informatics, University of Warsaw, Poland, marcin.pilipczuk@mimuw.edu.pl.
§
Institute of Informatics, University of Warsaw, Poland, michal.pilipczuk@mimuw.edu.pl.

1

Introduction

It has been observed in the context of different algorithmic paradigms that planar graphs enjoy
important structural properties that allow more efficient solutions to many of the classic hard
algorithmic problems. The literature on approximation algorithms contains many examples of
optimization problems that are APX-hard on general graphs, but admit polynomial-time approximation schemes (PTASes) when restricted to planar graphs (see, e.g., [2–5, 7, 17, 18, 23, 27, 30]). Even
though the planar versions of most NP-hard problems remain NP-hard, a more fine-grained look
reveals that significantly better running times are possible for planar graphs. As a typical example,
consider the 3-Coloring problem: it can be solved in 2O(n) time in general graphs and, assuming
the Exponential-Time Hypothesis (ETH), this is best possible as there is no 2o(n) -time
√ algorithm.
O(
n) , which is
However, when restricted to planar graphs, 3-Coloring
√ can be solved in time 2
o(
n)
again best possible assuming ETH: the existence of a 2
-time algorithm would contradict ETH.
There are many other problems that behave in a similar way and this can be attributed to the
√
combination of two important facts: (1) every planar graph on n vertices has treewidth O( n)
and (2) given an n-vertex graph of treewidth t, most of the natural combinatorial problems can
O(t) · nO(1) (or perhaps 2O(t·polylog t) · nO(1) ). On the lower bound side, to rule
be solved
√ in time 2
o(
n)
out 2
time algorithms, it is sufficient to observe that most planar NP-hardness proofs increase
the size of the instance at most quadratically (because of the introduction of crossing gadgets).
For example, there are reductions from n-variable m-clause 3SAT to√ 3-Coloring a planar graph
with O((n + m)2 ) vertices, and together with ETH, this rules out 2o( n) time algorithms
for planar
√
O(
n)
3-Coloring. Thus the existence of this “square root phenomenon” giving 2
time complexity
is well-understood both from the algorithmic and complexity viewpoints.
Our understanding of this phenomenon is much less complete for parameterized problems. A
large fraction of natural fixed-parameter tractable graph problems can be solved in time 2O(k) · nO(1)
(with notable exceptions [13, 31]) and a large fraction of W[1]-hard problems can be solved in time
nO(k) . There are tight or almost-tight lower bounds showing the optimality of these running
times.
√
O( k·polylog k)
By now, there
is
a
growing
list
of
problems
where
the
running
time
improves
to
n
√
or to 2O( k·polylog k) · nO(1) when restricted to planar graphs. For a handful of problems (e.g.,
Independent Set, Dominating Set, Feedback Vertex Set, k-Path) this improvement can
be explained in a compact way by the elegant theory of bidimensionality [14]. However, there√ is
no generic argument (similar to the simple argument described above for the existence of 2O( n)
algorithms) why such an improvement should be possible for most parameterized problems. The
√
fact that every n-vertex
planar graph has treewidth O( n) does not seem to help in improving
√
the 2O(k) factor to 2O( k) in the running time. The algorithmic results of this form are thus very
problem-specific, exploiting nontrivial observations on the structure of the solution or invoking other
tools tailored to the problem’s nature. Recent results include algorithms for Subset TSP [29],
Multiway Cut [28, 33], unweighted Steiner Tree parameterized by the number of edges of the
solution [38, 39], Strongly Connected Steiner Subgraph, [9], Subgraph Isomorphism [21],
facility location problems [35], Odd Cycle Transversal [32], and 3-Coloring parameterized by
the number of vertices with degree ≥ 4 [1].
It is plausible to expect that other natural problems also have significantly faster parameterized
algorithms on planar graphs. The reason for this optimism is twofold. First, even though the
techniques used to obtain the results listed above are highly problem-specific, they suggest that
planar graphs have rich structural properties that could be exploited when solving other problems.
Second, it looks almost impossible to prove lower bounds ruling out subexponential algorithms for
planar problems. To prove that a parameterized algorithm with running time 2o(k) · nO(1) violates

1

ETH, one needs to give a reduction from 3SAT with m clauses to a planar instance with parameter
k = O(m). In a typical reduction, we represent each bit of information in the 3SAT instance
(e.g., values of the variables in the solution) by a small “gadget” in the planar graph. In order to
encode the constraints of the input instance, we need to connect these gadgets in an appropriate
way. However, in a planar graph, we need to introduce some kind of “crossing gadgets” in order to
realize these connections. To realize the constraints given by the O(m) clauses, it may be necessary
to introduce up to O(m2 ) crossings. As each crossing typically increases the parameter,
we end up
√
with an instance having parameter k = O(m2 ), which is only sufficient to rule out 2o( k) · nO(1) -time
algorithms. Thus the appearance of many crossing gadgets seems to be an inherent limitation
preventing stronger lower bounds. This may suggest that running times of the form 2o(k) · nO(1) are
achievable for many problems.
Our contribution. In this paper we address two network design problems on planar graphs
for which the existence of subexponential parameterized algorithms was open. Given a graph
G with a subset T of vertices distinguished as terminals, the Subset TSP problem asks for a
shortest closed walk visiting the terminals in any order. Parameterized by the number k = |T |
of terminals, the problem is fixed-parameter tractable in arbitrary graphs: it can be solved in
time 2k · nO(1) by first computing the distance between every pair of terminals, and then solving
the resulting k-terminal instance using the standard Bellman-Held-Karp dynamic programming
algorithm. Klein and Marx [29] showed that if G is an undirected planar graph with√polynomially
bounded edge weights, then the problem can be solved significantly faster, in time 2O( k log k) · nO(1) .
The limitations of polynomial weights and undirected graphs are inherent to this algorithm: it starts
with computing a locally 4-step optimal solution (which requires polynomial weights to terminate in
polynomial time) and relies on an elaborate subtour-replacement argument (which breaks down if
the tour has an orientation). The main argument is the unexpected and somewhat√mysterious claim
that the union of an optimal and a locally 4-step optimal tour has treewidth O( k).
Our first result is a more robust and perhaps less mysterious algorithm that achieves the same
running time, but does not suffer from these limitations.
Theorem 1.1. Given an edge-weighted directed planar
graph G with terminals T , Subset TSP
√
parameterized by k = |T | can be solved in time 2O( k log k) nO(1) .
The proof of√Theorem 1.1 has the same high-level idea as the algorithm of Klein and Marx [29]:
a family of 2O( k log k) subsets of terminals is computed, followed by applying a variant of the
Bellman-Held-Karp dynamic programming algorithm that considers only subsets of terminals that
appear in this family. However, the way we compute such a family is very different: the construction
of Klein and Marx [29] crucially relies on how the optimal solution interacts with the locally 4-step
optimal solution (e.g., they cross each other O(k) times), while our argument here does not use
any such assumption. For directed graphs, we can extract much fewer properties of the structure
of the solution or how it interacts with some other object. For example, we cannot require that
the optimum solution is non-self-crossing and the number of self-crossings cannot be even bounded
by a function of k. Thus in order to find an algorithm working on directed graphs, we need to
use more robust algorithmic ideas that better explain why it is possible to have subexponential
parameterized algorithms for this problem. In Section 2, we highlight these new ideas in an overview
of the algorithm of Theorem 1.1.
Given an edge-weighted undirected graph G and a set T of terminal vertices, Steiner Tree asks
for a minimum-weight tree connecting all the terminals. This problem is well known to be NP-hard,
even in planar graphs [24]. Dreyfus and Wagner [16] gave a dynamic programming algorithm that
2

solves Steiner Tree in time 3k · nO(1) in arbitrary graphs. The running time of this algorithm
was improved to 2k · nO(1) for small weights using fast subset convolution [37]. It is known that,
assuming ETH, there is no 2o(k) · nO(1) time algorithm for the problem in general graphs and in fact
it is conjectured that the 2k factor cannot be improved to (2 − )k for any  > 0 [10].
In light of the long list of other subexponential parameterized
problems on planar graphs, it is
√
natural to expect that Steiner Tree can be solved in 2O( k log k) · nO(1) time on planar graphs. In
fact, this question has been posed as a natural open problem in various places [6,11,19,34,38,39]. As
partial progress toward this goal, in the unweighted case, subexponential algorithms parameterized
by the number of edges of the solution and number of nonterminal vertices were found [38, 39, 41].
However, the number of edges can be of course much larger than the number of terminals, hence an
algorithm that is subexponential in the number of edges is not necessarily subexponential in the
number of terminals. We show here that there was a reason why, despite significant efforts, no such
algorithm was found so far: assuming ETH, there is no subexponential parameterized algorithm for
Steiner Tree on planar graphs.
Theorem 1.2. Unless the ETH fails, there is no 2o(k) · nO(1) time algorithm for Steiner Tree
on an unweighted and undirected planar graph with k = |T | terminals.
Thus unlike many other problems, Steiner Tree parameterized by the number of terminals
does not become dramatically simpler with the restriction of planarity. This is highly unexpected:
Steiner Tree seems to be first “genuinely planar” problem where there is no significant speedup
when restricted to planar graphs, and the 2O(k) factor for arbitrary graphs cannot be improved. The
informal expression “genuinely planar” emphasized the fact that input of Steiner Tree is planar
graph with a distinguished subset of vertices and there is no other extra, nonplanar information
encoded in the input. For example, it was known before that Directed Steiner Network (given
a directed graph G and requests (s1 , t1 ), . . . , (sk , tk ), find a subgraph of minimum weight that
contains an si → ti path for every i) can be solved in time nO(k) on general graphs, and there is no
f (k)no(k) time algorithm even on planar graphs [9]. However, this problem is not genuinely planar,
as the pairs (si , ti ) can encode arbitrary connections that do not respect planarity.
Theorem 1.2 makes the previous subexponential algorithms (including Theorem 1.1 for Subset
TSP on directed graphs) even more surprising: apparently there is no general rule why these
problems should have subexponential parameterized algorithms on planar graphs, and it could have
turned out for other problems as well that planarity does not allow any dramatic speedup. This
negative result also changes our expectations for future work in this direction: we cannot take it for
granted that most reasonable problems have subexponential parameterized algorithms on planar
graphs and now it seems to be a very real possibility that other natural problems behave similarly
to Steiner Tree.
We need some explanation how it was possible to prove Theorem 1.2: earlier we have argued that
such lower bounds seem very unlikely, because one would need O(n2 ) crossings when reducing from
a 3SAT instance with O(n) variables and O(n) clauses. In the proof of Theorem 1.2, we are doing
something unusual: in the created planar instance, we are not only introducing O(n) gadgets, each
representing one bit of the 3SAT instance (as it is usually done in reductions), but we introduce
also gadgets representing larger groups of bits. The crucial trick is that we can create crossings
where an information flow of one bit crosses the information flow of many bits, and this crossing
increases the parameter only by O(1). With such crossings, the total number of crossing gadgets
can be limited and we can make sure that the parameter becomes O(n). The catch is that the
reduction is no longer polynomial: the representation of large groups of bits require a planar graph
that is exponentially large. However, we can argue that a subexponential parameterized algorithm
on this exponentially large graph would result in a 2o(n) algorithm for 3SAT, violating ETH.
3

The reduction in the proof of Theorem 1.2 is a “hybrid” reduction in the sense that it combines
different proof strategies. In typical NP-hardness proofs, one constructs small gadgets that represent
one bit or information or have a constant number of different states. In typical W[1]-hard proofs,
the challenge is to construct large gadgets that can have many different states (corresponding to,
say, the choice of a vertex in a clique). The proof of Theorem 1.2 combines these two ideas: we
need both small gadgets representing single bits and large gadgets having many different states.
Additionally, we use the idea of splitting the variables into groups and allowing a blowup of the size
of the instance by a factor that is exponential in the size of the groups (as it is done in, e.g., [8, 31]).
Thus our reduction combines in a novel way many of the insights that we have learned in the past
decades about proving lower bounds on the exact complexity of hard algorithmic problems.
Our final result shows that there is still some way in which subexponentiality appears for
planar Steiner Tree. On high level, the proof of this theorem follows the same approach as a
corresponding result for rectilinear Steiner tree [20].
Theorem 1.3. Given an edge-weighted planar undirected graph G with n vertices
and a set T ⊆ V (G)
√
O( |T |)
· W , where W is the
of terminals, one can find a minimum-cost Steiner tree for T in time n
maximum weight of an edge.
Note that this running time is incomparable to the 2k · nO(1) time, available for general graphs.
It is known that unweighted Steiner Tree in planar graphs admits a polynomial kernel when
parameterized by the number of edges in the solution [39]. A natural question is whether this can
be improved to a polynomial kernel parameterized by the number of terminals. While we cannot
answer this question here, a simple combination of Theorems 1.2 and 1.3 implies that, assuming
ETH, there is no kernelization algorithm that produces a polynomial kernel that preserves the
number of terminals.
Corollary 1.4. Suppose there is a polynomial-time algorithm that, given an unweighted planar
Steiner Tree instance (G, T ) and an integer k, computes another unweighted planar Steiner
Tree instance (G0 , T 0 ) and an integer k 0 , such that |T 0 | = O(|T |), |G0 | bounded polynomially in |T |,
and (G, T ) admits a Steiner tree of size at most k if and only if (G0 , T 0 ) admits a Steiner tree of
size at most k 0 . Then the ETH fails.

2

Directed Traveling Salesman: overview

In this section we give an overview of the approach leading to the subexponential parameterized
algorithm for Directed Subset TSP, that is, the proof of Theorem 1.1. We first describe the
high-level strategy of restricting the standard dynamic programming algorithm to a smaller family
of candidate states. Then we explain the main idea of how such a family of candidate states can be
obtained, however we introduce multiple simplifying assumptions and hide most of the technical
problems. Finally, we briefly review the issues encountered when making the approach work in full
generality, and explain how we cope with them. We strongly encourage the reader to read this
section before proceeding to the formal description, as in the formal layer many of the key ideas
become somehow obfuscated by the technical details surrounding them.

2.1

Restricted dynamic programming

Restricting dynamic programming to a small family of candidates states is by now a commonly
used technique in parameterized complexity. The idea is as follows. Suppose that we search for a
minimum-cost solution to a combinatorial problem, and this search can be expressed as solving a
4

number of subproblems in a dynamic programming fashion, where each subproblem corresponds
to a state from a finite state space S. Usually, subproblems correspond to partial solutions, and
transitions between states correspond to extending one partial solution to a larger partial solution
at some cost, or combining two or more partial solutions to a larger one. For simplicity, assume for
now that we only extend single partial solutions to larger ones, rather than combine multiple partial
solutions. Then the process of assembling the final solution from partial solutions may be described
as a nondeterministic algorithm that guesses consecutive extensions, leading from a solution to the
most basic subproblem to the final solution for the whole instance. The sequence of these extensions
is a path (called also a computation path) in a directed graph on S where the transitions between
the states are the arcs. Then the goal is to find a minimum-weight path from the initial state to any
final state, which can be done in time linear in the size of this state graph, provided it is acyclic.
In order to improve the running time of such an algorithm one may try the following strategy.
Compute a subset of states S 0 ⊆ S with the following guarantee: there is a computation path
leading to the discovery of a minimum-weight solution that uses only states from S 0 . Then we may
restrict the search only to states from S 0 . So the goal is to find a subset of states S 0 that is rich
enough to “capture” some optimum solution, while at the same time being as small as possible so
that the algorithm is efficent.
Let us apply this principle to Directed Subset TSP. Consider first the most standard dynamic
programming algorithm for this problem, working on general graphs in time 2k · nO(1) , where we
denote k = |T | by convention. Each subproblem is described by a subset of terminals S ⊆ T and
two terminals s1 , s2 ∈ S. The goal in the subproblem is to find the shortest tour that starts in s1 ,
ends in s2 , and visits all terminals of S along the way. The transitions are modelled by a possibility
of extending a solution for the state (S, s1 , s2 ) to a solution for the state (S ∪ {s0 }, s1 , s0 ) for any
s0 ∈
/ S at the cost of adding the shortest path from s2 to s0 . The minimum-weight tour can be
obtained by taking the best among solution obtained as follows: for any s1 , s2 ∈ T , take the solution
for the subproblem (T, s1 , s2 ) and augment it by adding the shortest path from s2 to s1 .
This is not the dynamic programming algorithm we will be improving upon. The reason is
that restricting ourselves to constructing one interval on the tour at a time makes it difficult to
enumerate a small subfamily of states capturing an optimum solution.
Instead, we consider a more
√ involved variant of the above dynamic programming routine, which
intuitively keeps track of O( k) intervals on the tour at a time. More precisely, each subproblem is
described by a state defined as a pair (S, M), where S ⊆ T is a subset of terminals to be visited,
and M (also
√ called connectivity pattern) is a set of pairwise disjoint pairs of terminals from S, where
|M| ≤ C k for some universal constant C. The goal in the subproblem is to compute a family of
paths P(S,M) of minimum possible weight having the following properties: for each (s1 , s2 ) ∈ M
there is a path in P(S,M) that leads from s1 to s2 , and each terminal from S lies on some path in
P(S,M) . Note, however, that we do not specify, for each terminal from S, on which of the paths it
has to lie. Solutions to such subproblems may be extended by single terminals as in the standard
dynamic programming, but they can be also combined in pairs. Precisely, given solutions P1 and
P2 respectively for (S1 , M1 ) and (S2 , M2 ), where S1 ∩ S2 = ∅, we may merge these solutions into a
solution for (S1 ∪ S2 , M) by connecting paths from P1 and P2 using shortest path between respective
start and end vertices, so that
M is obtained at the end. Since we assume
√
√ the connectivity pattern
O(
k)
that |M1 |, |M1 |, |M| ≤ C k, there are only k
ways to perform such a merge. While this
dynamic programming algorithm formally does not conform to the “linear view” described in the
paragraphs above, as it may merge partial solutions for two simpler states into a larger partial
solution, it straightforward to translate the concept restricting the state space to a small subset that
preserves the existence of a computation path (in this setting, rather a computation tree) leading to

5

a minimum-cost solution.
√
Observe that since in a state (S, M) we√stipulate the size of M to be O( k), the total number
of states with a fixed subset S ⊆ T is k O( k) . Thus, from the discussion above we may infer the
following lemma, stated here informally.
Lemma 2.1 (Lemma 5.22, informal statement). Let (G, T ) be an instance of Directed Subset
TSP. Suppose we are also given a family B of subsets of T with the following guarantee: there is a
computation path of the above dynamic programming leading to an optimum solution that uses only
states of the form √(S, M) where S ∈ B. Then we can find an optimum solution for the instance
(G, T ) in time k O( k) · (|B| · |G|)O(1) .
Concluding, we are left with constructing
a family B of subsets of T that satisfies the prerequisites
√
of Lemma 2.1 and has size k O( k) , provided the underlying graph G is planar. For this, we will
crucially use topological properties of G given by its planar embedding.

2.2

Enumerating candidate states

Suppose (G, T ) is the input instance of Directed Subset TSP where G is planar. Without loss
of generality we may assume that G is strongly connected. Fix some optimum solution W , which is
a closed walk in the input graph G that visits every terminal.
We now introduce a number of simplifying assumptions. These assumptions are made with loss
of generality, and we introduce them in order to present our main ideas in a setting that is less
obfuscated by technical details.
(A1) Walk W is in fact a simple directed cycle, without any self-intersections. In particular, the
embedding of W in the plane is a closed curve without self-crossings; denote this curve by δ.
(A2) Walk W visits every terminal exactly once, so that we may speak about the (cyclic) order of
visiting terminals on W .
We will also assume that shortest paths are unique in G, but this can be easily achieved by perturbing
the weights of edges of G slightly.
Suppose now that
√ we have another closed curve γ in the plane, without self-crossings, that
crosses δ in p = O( k) points, none of which is a terminal. Curve γ divides the plane into two
regions—say R1 , R2 —and thus δ is divided into p intervals which are alternately contained in R1
and R2 . Let S be the set of terminals visited on the intervals contained in R1 . Then it is easy to√see
that S is a good candidate for a subset of terminals that we are looking: S forms at most O( k)
contiguous intervals in the order of visiting terminals by W , and hence for the connectivity pattern
M consisting of the first and last terminals on these intervals, the state (S, M) would describe a
subproblem useful for discovering W .
However, we are not really interested in capturing one potentially useful state, but in enumerating
a family of candidate states that contains a complete computation path leading to the discovery of
an optimum solution. Hence, we rather need to capture a hierarchical decomposition of T using
curves γ as above, so that terminal subsets S induce the sought computation path. For this, we will
use the notion of sphere-cut decompositions of planar graphs, and the√well-known fact that every
k-vertex planar graph admits a sphere-cut decomposition of width O( k).
A branch decomposition of a graph G is a tree T with every internal node having degree 3,
together with a bijection η from the edges of G to leaves of T . For every edge e of T , the removal
of e from T splits T into two subtrees, say Te1 and Te2 . This naturally induces a partition {Fe1 , Fe2 }
of the edge set of G as follows: Fe1 comprises edges mapped by η to leaves residing in Te1 , and
6

symmetrically for Te2 . The width of the edge e is the number of vertices of G incident to both an
edge of Fe1 and to an edge of Fe2 , and the width of a branch decomposition (T , η) is the maximum
width among its edges. The branchwidth of a graph G is the minimum possible width of a branch
√
decomposition of G. It is well-known that a planar graph on k vertices has branchwidth O( k)
(see e.g. [22]).
After rooting a branch decomposition (T , η) in any node, it can be viewed as a hierarchical
decomposition of the edge set of G using vertex cuts of size bounded by the width of the decomposition.
Robertson et al. [40] proved that in planar graphs we can always find an optimum-width branch
decomposition that somehow respects the topology of the plane embedding of a graph. Precisely,
having fixed a plane embedding of a connected graph G, call a closed curve γ in the plane a noose if
γ has no self-crossings and it crosses the embedding of G only at vertices; in particular it does not
intersect any edge of G1 . Such a curve γ divides the plane into two regions, which naturally induces
a partition of the edge set of G into edges that are embedded in the first, respectively the second
region. A sphere-cut decomposition of G is a branch decomposition (T , η) where in addition every
edge e of T is assigned its noose γ(e) that induces exactly the partition {Fe1 , Fe2 } of the edge set
of G in the sense above. Then the result of Robertson et al. [40] may be stated as follows: every
connected planar graph has a sphere-cut decomposition of width equal to its branchwidth2 . Together
with the square-root behavior of the branchwidth of a planar graph, this implies the following.
Theorem 2.2 (see e.g. [22]).
√ Every connected plane graph on k vertices has a sphere-cut decomposition of width at most α k, for some constant α.
Moreover, such a sphere-cut decomposition of can be computed in polynomial time [15, 25].
Turning back to our Directed Subset TSP instance (G, T ) and its optimum solution W , our
goal is to enumerate a possibly small family of subsets of T that contains some complete computation
path leading to the discovery of W . The idea for this will be as follows. Take any minimal tree H0
in (the underlying undirected graph) of G spanning all terminals of T . We may assume that H0
contains at most k leaves that are all terminals, at most k − 2 vertices of degree at least 3, and
otherwise it consists of at most 2k − 3 simple paths connecting these leaves and vertices of degree at
least 3 (further called special vertices of H0 ). To avoid technical issues and simplify the picture, we
introduce another assumption.
(A3) Walk W and tree H0 do not share any edges.
Let H be the graph formed by the union of W and H0 . Even though both W and H consists of
at most 2k simple paths in G, the graph H may have many vertices of degree more than 3. This is
because a subpath Q between two consecutive terminals on W and a path P in H0 that connects two
special vertices of H0 may cross many times. The intuition is, however, that the planar structure of
H roughly resembles a structure√of a planar graph on O(k) vertices, and a sphere-cut decomposition
of this planar graph of width O( k) should give rise to the sought hierarchical partition of terminals
leading to the discovery of W by the dynamic programming algorithm.
Let us remark that, of course, the definition of the graph H relies on the (unknown to the
algorithm) solution W , though the tree H0 can be fixed and used by√the algorithm. At the end
we will argue that having fixed H0 , we may enumerate a family of k O( k) candidates for nooses in
1
In standard literature, e.g. [40], a noose is moreover required to visit every face of G at most once; in this paper
we do not impose this restriction.
2
In [40] it is also assumed that the graph is bridgeless, which corresponds to the requirement that every face is
visited by a noose at most once. It is easy to see that in the absence of this requirement it suffices to assume the
connectivity of the graph.

7

a sphere-cut decomposition of H. Roughly, for each such noose γ we consider the bi-partition of
terminals according to the regions of the plane minus γ in which they lie, and
√ we put all terminal
subsets constructed in this manner into a family B, which is of size k O( k) . Then restricting
the dynamic programming algorithm to B in the sense of Lemma 2.1 gives us the required time
complexity.
Therefore,
√ the goal is to simplify the structure of H so that it admits a sphere-cut decomposition
of width O( k). Consider any pair of terminals t1 , t2 visited consecutively on W , and let P be the
subpath of W from t1 to t2 . Consider contracting all internal vertices on P into a single vertex,
thus turning P into a path P 0 on 2 edges and 3 vertices. Let H 0 be the graph obtained from H
by contracting each path between two consecutive terminals on W in the manner described above.
Observe that thus, H 0 has less than 3k vertices of degree at least 3: there are at most 2k vertices
on the contracted W in total, and there can be at most k − 2 vertices of degree at least 3 on H0
that do not lie on W . If we now take H 0 and contract every maximal path with internal vertices of
00
00
degree 2 into a single edge, we turn H 0 into a planar
√ graph H on at most 3k vertices. Then H
has a sphere-cut decomposition of width at most α 3k, say (T , η, γ(·)).
Consider family D of subsets of terminals constructed as follows. For each noose γ(e) for
e ∈ T , that is, appearing in the sphere-cut decomposition (T , η, γ(·)), and each
partition (X, Y )
√
√
of terminals traversed by γ(e) (there are at most α 3k such terminals, so 2O( k) such partitions),
add to D the following two terminal subsets: the set of terminals enclosed by γ(e) plus X, and the
set of terminals excluded by γ(e) plus Y . It can be now easily seen that D contains a complete
computation
path that we are looking for, as each terminal subset included in D forms at most
√
O( k) contiguous intervals in the cyclic order of terminals on W , and the decomposition tree T
shows how our dynamic programming should assemble subsets appearing in D in pairs√up to the
whole terminal set. In other words, if we manage to construct a family B of size k O( k) with a
guarantee that it contains the whole D, then we will be done by Lemma 2.1.
Obviously, the graph H 00 is not known to the algorithm, as its definition depends on the fixed
optimum solution W . Nevertheless, we may enumerate a reasonably small family of candidates for
nooses used in its sphere-cut decomposition (T , η, γ(·)). The √main idea is that even though the
full structure of H 00 cannot be guessed√at one shot within k O( k) possibilities, each noose we are
interested in traverses only at most α 3k vertices of H 00 , and hence it is sufficient to guess only
this small portion of H 00 .
More precisely, let Q be the subset of those vertices of H 00 that are obtained from contracting
the subpaths of W between consecutive terminals. Fix a noose γ appearing in √
the sphere-cut
decomposition of H 00 , that is, γ = γ(e) for some e ∈ T . Then γ traverses at most α √3k vertices of
Q; say that R ⊆ Q is the set of these vertices. We can now enumerate a set of k O( k) candidates
for γ as follows (by guessing we mean iterating through all options):
√
(1) Guess a set R of at most α 3k pairs of distinct terminals.
(2) For each (s, t) ∈ R, take the shortest path P(s,t) from s to t and consider contracting it to a
single vertex p(s,t) .
(3) Take the fixed tree H0 that spans terminals in G, apply the above contractions in G, and let
HR be the graph to which H0 is transformed under these contractions.
(4) Enumerate all nooses
√ γ that meet HR only at terminals and vertices of degree at least 3, and
traverse at most α 3k such vertices.
√

In the Step 1 we have at most k O( k) options for such a set R, and the contractions in Steps 2
and 3 turn H0 into a planar graph HR with O(k) vertices. It is not hard to convince oneself that in
8

√

such a graph, there are only k O(√ k) nooses satisfying the property expressed in the√Step 3, so all
in all we enumerate at most k O( k) curves in the plane, each traversing at most α 3k terminals.
Now, to conclude the construction of B we do as follows. For each enumerated curve γ, and each
partition (X, Y ) of terminals traversed by γ, we include into B two terminal subsets: the set√ of
terminals enclosed by γ plus X, and the set of terminals excluded by γ plus Y . Thus |B| = k O( k) .
It remains to argue that B contains the whole family D that was given by the sphere-cut
decomposition (T , η, γ(·)) of H 00 , so that Lemma 2.1 may be applied. It should be quite clear that
it is sufficient to show that every noose γ appearing in (T , η, γ(·)) is somehow enumerated in Step 4
of the procedure from the previous paragraph. However, nooses with respect to HR are formally
not necessarily nooses with respect to H 00 , as we wanted. Nevertheless, if a noose γ appears in the
sphere-cut decomposition (T , η, γ(·)) of H 00 , and we take R to be the set of pairs of consecutive
terminals on W such that γ passes through the contracted vertices p(s,t) exactly for (s, t) ∈ R, then
after dropping parts of H 00 not appearing in HR , γ becomes a noose enumerated for HR . Therefore,
the terminal partitions raised by γ are still included in B as we wanted, and we are done.

2.3

Traps, issues, and caveats

The plan sketched in the previous section essentially leads to an algorithm with the promised
time complexity, modulo Assumptions A1, A2, A3, and a number of technical details of minor
relevance. Assumptions A2 and A3 are actually quite simple to achieve without loss of generality.
It is Assumption A1 that was a major conceptual obstacle.
For Assumption A2, we may at the very beginning perform the following reduction. For every
original terminal t, introduce a new terminal t0 and edges (t, t0 ) and (t0 , t) of weight 0 to the graph;
t0 and these edges are embedded in any face incident to t. The new terminal set consists of terminals
t0 for all original terminals t. In this way, any closed walk visiting any new terminal t0 has to make
a detour of weight 0 using arcs (t, t0 ) and (t0 , t), and we may assume that an optimal solution makes
only one such detour for each new terminal t0 . Thus we achieve Assumption A2, but actually the
fact that we may assume that every terminal is incident to one non-trivial face and one trivial face
between (t, t0 ) and (t0 , t) also helps in solving technical issues later on.
For Assumption A3, observe that in the reasoning we relied only on the fact that H0 is a tree
spanning all terminals that has at most k leaves and at most k − 2 vertices of degree at least 3. In
particular, we did not use any metric properties of H0 . In fact, the reader may think of H0 as a
combinatorial object used to control the homotopy group of the plane with terminals pierced out:
for any non-self-crossing curve γ on the plane, we may infer how terminals are partition into those
enclosed by γ, excluded by γ, and lying γ by just examining the consecutive intersections of γ with
H0 . Therefore, instead of choosing H0 arbitrarily, we may add it to the graph artificially at the
very beginning, say using edges of weight +∞. In this way we make sure that the optimum solution
W does not use any edge of H0 .
Finally, let us examine Assumption A1: the optimum solution W is a simple directed cycle
without self-intersections. Unfortunately, this assumption may not hold in general. Consider the
example depicted in Figure 1, where we have a directed planar graph with two terminals s, t, and
the only closed walk visiting both s and t consists of two paths, one from s to t and the second from
t to s, that intersect each other an unbounded number of times. Therefore, in general the optimum
solution W may have an unbounded number of self-crossings. Nevertheless, we may still develop
some kind of a combinatorial understanding of the topology of W .
It will be convenient to assume that no edge of the graph is traversed by W more than once;
this can be easily achieved by copying each edge |T | times, and using a different copy for each
traversal. Consider two visits of the same vertex u by W ; let e1 , e2 be the edges incident to u used
9

s

t

Figure 1: A planar Directed Subset TSP instance with two terminals. The only solution consists
of the union of the red path from s to t and the blue path from t to s. These two paths cross each
other many times, which gives many self-crossings of the solution.
by W just before and just after the first visit, and define f1 , f2 in the same way for the second visit.
Examine how e1 , e2 , f1 , f2 are arranged in the cyclic order of edges around vertex u. If they appear
in the interlacing order, i.e., (e1 , f1 , e2 , f2 ) or (e1 , f2 , e2 , f1 ), then we say that these two visits form
a self-crossing of W . Intuitively, if the order is not interlacing, then we may slightly pull the two
parts of the embedding of W near u corresponding to the visits so that they do not intersect. So
topologically we do not consider such a self-intersection as a self-crossing. For two walks W1 , W2 in
G that do not share any common edges we define their crossing in a similar manner, as a common
visit of a vertex u such that the cyclic order of edges used by W1 and W2 immediately before and
immediately after these visits is interlacing.
We now prove the following structural statement about self-crossings of W : we may always
choose an optimal solution W so that the following holds. Consider any self-crossing of W at some
vertex u (recall it consists of two visits of u) and say it divides W into two closed subwalks W1 and
W2 : W1 is from the first visit of u to the second, and W2 is from the second visit of u to the first.
Then the subwalks W1 and W2 do not cross at all. This statement can be proved by iteratively
“uncrossing” an optimum solution W as long as the structure of its self-crossings is too complicated.
However, one needs to be careful in order not to split W into two closed curves when uncrossing.
It is not hard to observe that the statement given in the previous paragraph actually shows that
the topology of W roughly resembles a cactus where each 2-connected component is a cycle (here,
we assume that self-intersections that are not self-crossings are pulled slightly apart so that W does
not touch itself there). See the left panel of Figure 2 in Section 5.1 for reference. Then we show (see
Lemma 5.7) that W can be decomposed into O(k) subpaths P = {B1 , . . . , B` } such that:
• each path Bi has no terminal as an internal vertex and is the shortest path between its
endpoints; and
• each path Bi may cross with at most one other path Bj .
To see this, note that the cactus structure of W may be described as a tree T with at most k leaves
and at most k − 2 vertices of degree at least 3. We have a pair of possibly crossing subpaths in the
decomposition P per each maximal path with internal vertices of degree 2 in T .
The idea now is as follows. In the previous section we essentially worked with the partition of
W into subpaths between consecutive terminals, as Assumption A1 allowed us to do so. In the
absence of this assumption, we work with the finer partition P as above. The fact that the paths of
P interact with each other only in pairs, and in a controlled manner, makes the whole reasoning go
through with the conceptual content essentially unchanged, but with a lot more technical details.
One nontrivial difference is that in the previous section we were contracting shortest paths
between pairs of consecutive terminals, so we had a small set of candidates for the endpoints of
10

these paths: the terminals themselves. In the general setting, the decomposition statement above
a priori does not give us any small set of candidates for endpoints of paths Bi . If we chose
those
√
O( k) instead
endpoints as arbitrary
vertices
of
the
graph,
we
would
end
up
with
time
complexity
n
√
of promised k O( k) · poly(n). Fortunately, the way we define the decomposition P = {B1 , . . . , B` }
allows us to construct alongside also a set of at most k 4 important vertices such that each path Bi
is the shortest path from one important vertex to another important vertex.
Finally, there are more technical problems regarding handling possible self-intersections of W
that are not self-crossings. Recall that in our topological view of W , we would like not to regard
such self-intersections as places where W touches itself. In particular, when examining a sphere-cut
decomposition of the union of W and H0 after appropriate contractions, the nooses in this sphere-cut
decomposition should not see such self-intersections as vertices through which they may or should
travel. A resolution to this problem is to consider a “blow-up” of the original graph where each
vertex is replaced by a large well-connected “cloud” of vertices, and each edge is replaced by a large
matching of parallel edges leading from one cloud to another. Walks in the original graph naturally
map to walks in the blow-up. Every original self-crossing maps to a self-crossing, and every original
self-intersection that is not a self-crossing actually is “pulled apart”: there is no self-intersection at
this place anymore. This blow-up has to be performed at the very beginning of the proof, and hence
we need to work on it throughout the whole reasoning. This technical layer is somehow conceptually
simple, but contributes to the technical complexity of the argumentation.

3

Preliminaries

Throughout the paper we denote [n] = {1, 2, . . . , n} for any positive integer n,
We will consider directed or undirected planar graphs G with a terminal set T ⊆ V (G) and
weight function ωG : E(G) → Z≥0 ; we omit the subscript if it is clear from the context. Furthermore,
we assume that G does not contain loops, but may contain multiple edges or arcs with the same
endpoints.
We assume that shortest paths in the input instance G are unique. Since we do not analyze the
polynomial factor in the running time bound of our algorithms, this can be ensured in a standard
manner by replacing a weight ω(e) of the i-th edge/arc with ω(e) · n|E(G)|+1 + ni . Let PG (u, v) be
the shortest path from u to v in G.
We also assume that every terminal t ∈ T has only one neighbor wt , with two arcs arcs (wt , t)
and (t, wt ) of weight 0 in the directed setting, or a single edge twt of weight 0 in the undirected
setting. To obtain such a property, for every terminal t0 ∈ T we can make its copy t, connect t and
t0 with an edge or arcs in both direction of weight 0, and rename wt = t0 . The new terminal set
is the set of the copies of the old terminals. Note that this property implies that every minimal
solution to the Steiner Tree problem contains every terminal as a leaf, and we can consider only
solutions to the Directed Subset TSP problem that visit every terminal exactly once.
A walk in a directed graph G is a sequence (e1 , . . . , ep ) of edges of G such that the head of ei is
the tail of ei+1 , for all i = 1, . . . , p − 1. A walk is closed if additionally the head of ep is equal to the
tail of e1 . The weight of a walk is the sum of the weights of its edges.
For a walk W that visits every terminal exactly once, a permutation π = (t1 , t2 , . . . , t|T | ) of
T is a witnessing permutation of W if it is exactly the (cyclic) order of the terminals visited by
W . A closed walk W is a T -simple walk if it visits every terminal exactly once and the subwalks
of W between the consecutive terminals are actually simple paths. A T -simple walk is T -short
if additionally the subwalks between the consecutive terminals are shortest paths between their
endpoints. Note that a minimum-weight solution to the Directed Subset TSP problem is a
11

T -short walk.
Blow-up of the graph. While working with a directed graph G and the Directed Subset
TSP problem, we modify the graph G into its blow-up as follows: for every edge e of G that is not
incident to any terminal, we replace it with |T | copies with the same head and tail and the same
weight. These copies are embedded in the plane in place of the original edge in the natural manner
so that they are parallel to each other; we say that they form a parallel bunch and that they are
parallel to each other. Note that each bunch is linearly ordered so that every two consecutive edges
form a 2-face. The relation of being parallel naturally extends to paths and walks in G. To simplify
notation, we will also consider every arc incident to a terminal (i.e., an arc of the form (t, wt ) or
(wt , t) for a terminal t) as a parallel bunch on its own.
Replacing a graph G with its blow-up breaks the property of having unique shortest path, but
only in a limited fashion: if G had the unique shortest paths property prior to the blow-up, then
after the blow-up for every two vertices u, v ∈ V (G), every two shortest paths from u to v are
parallel. By slightly abusing the notation, we will still say that G has unique shortest paths even if
the shortest paths are unique up to the choice of parallel paths.
After the blow-up, call a walk W in G clean if each edge of G is used by W at most once. Recall
that every T -simple walk W in G consists of |T | simple paths in G, so in particular each parallel
bunch in G is traversed at most |T | times by W . Hence, it is straightforward to modify any T -simple
walk to a clean parallel one, and hence we can consider only T -simple walks in G that are clean.
In the rest of the graph, we call an instance to Steiner Tree or Directed Subset TSP
preprocessed if it has undergone all the preprocessing steps outlined in this section.
Nooses and branch decompositions. Given a plane graph G, a noose is a closed curve without
self-intersections that meets the drawing of G only in vertices. Contrary to some other sources in
the literature, we explicitly allow a noose to visit one face multiple times, however each vertex is
visited at most once.
A branch decomposition of a graph G is a pair (T , ζ) where T is an unrooted ternary tree and
ζ is a bijection between the leaves of T and the edges of G. For every edge e ∈ E(T ), we define
the cut (or middle set) mid(e) ⊆ V (G) as follows: if T1 and T2 are the two components of T − e,
then v ∈ mid(e) if v is incident both to an edge corresponding to a leaf in T1 and to an edge
corresponding to a leaf in T2 . The width of a decomposition is the maximum size of a middle set,
and the branchwidth of a graph is a minimum width of a branch decomposition of a graph.
It is well known that planar graphs have sublinear branchwidth.
√
Theorem 3.1 (see e.g. [22]). Every planar graph on n vertices has branchwidth bounded by 4.5n.
In planar graphs, one can compute good branch decompositions, where the cuts mid(e) correspond
to nooses. More formally, a triple (T , ζ, γ) is an sc-branch decomposition (for sphere-cut branch
decomposition) if (T , ζ) is a branch decomposition and for every e ∈ E(T ), γ(e) is a noose that
traverses the vertices of mid(e) and separates the edges corresponding to the leaves of the two
components of T − e from each other.
We need the following result of Seymour and Thomas [40], with the algorithmic part following
from [15, 25].
Theorem 3.2 ( [15,25,40]). Given a connected plane graph G, one can in time O(|V (G)|3 ) compute
an sc-branch decomposition of G of width equal to the branchwidth of G.

12

We remark that in [15, 25, 40] one considers nooses that can visit every face at most once,
which makes it necessary to assume also that the graph is bridgeless; see e.g. [36]. It is easy to see
that without this assumption on nooses, one can extended the theorem also to connected graphs
with bridges by first decomposing into bridgeless components, and then decomposing each such
component separately.

4

Nooses

Let G be a plane (directed or undirected) graph with terminal set T and let γ be a noose in G that
visits at most ` vertices. In this section we show that if `  |T |, then there is much less than 2Θ(|T |)
ways of how the noose can partition the terminal set.
More formally, we think of the planar embedding of G as a spherical one (i.e., without distinguished outer face) and with a noose γ we associate a tri-partition of the terminal set (T0 , {T1 , T2 })
where T0 is the set of terminals that lie on γ and T1 and T2 are the sets of terminals that lie in the
two components of the sphere minus γ. Since we consider spherical embeddings and the two sides
of γ are symmetric, the pair {T1 , T2 } is an unordered pair.
Our main claim in this section is that there are only |T |O(`) reasonable partitions for nooses
visiting at most ` vertices.
Lemma 4.1. Assume we are given a plane connected graph G with a terminal set T and an integer `.
Then one can in time |T |O(`) nO(1) compute a family A of |T |O(`) of partitions of T such that, for
every noose of G that visits at most ` vertices, its corresponding tri-partition of the terminals belongs
to A.
Proof. The crucial observation is that deleting an edge or a vertex from G only increases the family
of curves in the plane that are nooses with respect to G. Consequently, if we replace G with any its
connected subgraph that spans all the terminals, and enumerate a family of partitions satisfying the
lemma statement for this subgraph, then the same family will be also a valid output for the original
graph G. Thus, by restricting attention to an inclusion-wise minimal subtree spanning all terminals,
without loss of generality we may assume that G is a tree and every its leaf is a terminal.
Let S be the set of special vertices in G: terminals and vertices of degree at least 3. Clearly,
every leaf of G is in S and |S| < 2|T |. Then G decomposes into |S| − 1 paths Q1 , Q2 , . . . , Q|S|−1
such that each path Qi has both endpoints in S but no internal vertices in S.
Construct now a graph G0 from G by replacing every path Qi with a path Q0i with the same
drawing in the plane, but with exactly ` internal vertices. Furthermore, for every noose γ in G that
visits at most ` vertices of G, construct its shift γ 0 , being a noose with respect to G0 , as follows: for
every path Qi , move all intersections of γ with the internal vertices of Qi to distinct internal vertices
of Q0i , keeping the relative order of the intersections along the paths Qi and Q0i the same. Since
Q0i has ` internal vertices, this is always possible. Furthermore, we can obtain γ 0 from γ by local
modifications within close neighborhoods of the paths Qi , but not near its endpoints. Consequently,
the partitions of the terminals induced by γ and γ 0 are the same.
Observe now that γ 0 is a noose with respect to a tree with less than 2|T |(` + 1) vertices. With
every intersection of γ 0 with G0 , say at a vertex v, we associate three pieces of information: the
vertex v itself, between which pair of edges incident with v the noose γ 0 entered v, and between
which pair of edges it left v. Since there are only O(|T |`) = O(|T |2 ) choices for every piece of
information, there are only |T |O(`) possible combinatorial representations of γ 0 , defined as a sequence
of the aforementioned triples of pieces of information at every vertex traversed γ 0 , in the order of a
walk along γ 0 . Finally, observe that, since the single face of G0 is isomorphic to a disc, knowing the
13

combinatorial representation of γ 0 is sufficient to deduce the tri-partition of the terminals induced
by γ 0 . This finishes the proof.

5

An algorithm for the Directed TSP problem

In this section we provide a full proof of Theorem 1.1.

5.1

Cleaning

Crossings and cleaning. Suppose W = (e1 , . . . , ep ) is a clean closed walk in G. In the following,
we assume the cyclic order of edges on closed walks, that is, ep+1 = e1 . A visit of a vertex v in G is
an index i ∈ {1, . . . , p} such that the head of ei (equivalently, the tail of ei+1 ) is equal to v. Note
that one vertex may have multiple visits on W . Suppose now W 0 = (e01 , . . . , e0p0 ) is another clean
closed walk in G that does not share any edges with W . A crossing of W and W 0 is a pair of indices
(i, j) such that the head of ei is the same vertex v as the head of e0j (that is, i is a visit of v on W
and j is a visit of v on W 0 ), and the clockwise order of edges ei , ei+1 , e0j , e0j+1 in the plane around v
is interlacing: it is ei , e0j , ei+1 , e0j+1 or ei , e0j+1 , ei+1 , e0j (of course, cyclically). A self-crossing of W is
defined in the same manner, but we consider two different visits of the same vertex v on W .
We now show that the crossing pattern of every clean closed walk can be simplified to a
“cactus-like” structure, as described next.
Definition 5.1. Suppose W = (e1 , . . . , ep ) is a clean closed walk in G and suppose (i, j) is a
self-crossing of W . Let W1 and W2 be the two clean closed walks obtained by splitting W at this
self-crossing, that is, W1 = (ei+1 , . . . , ej ) and W2 = (ej+1 , . . . , ei ). The clean closed walk W is called
reduced if for any self-crossing (i, j) of W , the clean closed walks W1 , W2 do not cross.
Lemma 5.2. For every clean closed walk W in G there exists a reduced closed walk Wrd that
traverses exactly the same set of edges as W . Furthermore, given W , such a walk Wrd can be
computed in polynomial time.
Proof. Suppose (f, g) is a pair of edges of G such that the head of f is the same as the tail of g;
call it v. Let (e1 , e2 , . . . , ed ) be the edges of incident to v in the clockwise order around v, and let
1 ≤ i, j ≤ d, i 6= j, be such that f = ei and g = ej . Define the span of (f, g), denoted span(f, g),
as the value |i − j|2 + (d − |i − j|)2 . Note that this value does not depend on the choice of the
enumeration (e1 , e2 , . . . , ed ), which is unique up to a cyclic shift. For a clean closed walk W , define
its span span(W ) as the sum of spans of pairs of consecutive edges on W .
We first show that “uncrossing” a crossing strictly increases the span.
Claim 5.3. Suppose v is a vertex of G, edges f1 , f2 have v as the head, edges g1 , g2 have v as the
tail, and edges f1 , f2 , g1 , g2 appear in this order in the clockwise order of edges incident to v. Then
span(f1 , g1 ) + span(f2 , g2 ) < span(f1 , g2 ) + span(f2 , g1 ).
Proof. Let (e1 , e2 , . . . , ed ) be the edges of incident to v in the clockwise order around v. By
choosing appropriately the cyclic shift of this order, we can assume w.l.o.g. that there are indices
1 ≤ i1 < i2 < j1 < j2 ≤ d such that f1 = ei1 , f2 = ei2 , g1 = ej1 , and g2 = ej2 . Then the claim is
equivalent to the inequality
(j1 −i1 )2 +(j2 −i2 )2 +(d−(j1 −i1 ))2 +(d−(j2 −i2 ))2 < (j1 −i2 )2 +(j2 −i1 )2 +(d−(j1 −i2 ))2 +(d−(j2 −i1 ))2 .

14

After opening brackets and straightforward algebraic manipulations, this is equivalent to
i1 j1 + i2 j2 > i1 j2 + i2 j1 .
This, in turn, is equivalent to (i1 − i2 )(j1 − j2 ) > 0, which holds due to i1 < i2 and j1 < j2 .

y

We proceed with the proof of the lemma. We give a polynomial-time procedure that given W
and a self-crossing (i, j) that witnesses that W is not reduced, outputs a clean closed walk W 0 that
traverses exactly the same set of edges as W , but W 0 has a strictly larger span than W . Since
the span of a clean walk is integral and bounded polynomially by the size of G, by applying this
procedure exhaustively after a polynomial number of iterations we eventually obtain a reduced
closed walk that can be output.
Suppose then W = (e1 , . . . , ep ) has some self-crossing (i, j) such that the subwalks W1 =
(ei+1 , . . . , ej ) and W2 = (ej+1 , . . . , ei ) obtained by splitting W at (i, j) do cross. Observe that the
set of pairs of consecutive edges on W is almost exactly the same as the union of sets of pairs of
consecutive edges on W1 and W2 , except that in this union we have pairs (ei , ej+1 ) and (ej , ei+1 )
instead of (ei , ei+1 ) and (ej , ej+1 ). Since (i, j) is a self-crossing of W , by Claim 5.3 we infer that
span(W1 ) + span(W2 ) > span(W ).

(1)

Now, for t = 1, 2 let pt be the length of Wt (thus p = p1 +p2 ), and let us enumerate Wt = (et1 , . . . , etpt )
so that e1k = ei+k for k = 1, . . . , p1 and e2k = ej+k for k = 1, . . . , p2 . We assumed that W1 and
W2 cross, so let (c1 , c2 ) be any their crossing, where (c1 , c2 ) ∈ {1, . . . , p1 } × {1, . . . , p2 }. Obtain a
closed walk W 0 by cutting W1 at position c1 , cutting W2 at position c2 , and gluing them together.
Formally,
W 0 = (e1c1 +1 , e1c1 +2 , . . . , e1c1 , e2c2 +1 , e2c2 +2 , . . . , e2c2 ).
Note that W 0 is a closed clean walk that uses exactly the same edges as W . Observe further that
the set of pairs of consecutive edges on W 0 is almost exactly the same as the union of sets of pairs
of consecutive edges on W1 and W2 , except that on W 0 we have pairs (e1c1 , e2c2 +1 ) and (e2c2 , e1c1 +1 )
instead of (e1c1 , e1c1 +1 ) and (e2c2 , e2c2 +1 ). Since (c1 , c2 ) is a crossing of W1 and W2 , by Claim 5.3 we
again infer that
span(W 0 ) > span(W1 ) + span(W2 ).
(2)
By combining (1) and (2) we infer that span(W 0 ) > span(W ), which concludes the proof.
Pushing crossings. We now proceed to analyzing T -simple walks. Recall that each T -simple
walk W in G is clean due to the blow-up operation. Note that every T -simple walk in G can be
made reduced using Lemma 5.2.
For technical reasons, we will need some further normalization of T -simple walks. Intuitively, we
want the property that whenever two subpaths between consecutive terminals cross, they cross as
early as possible.
Definition 5.4. A reduced T -simple walk W in G is first-cross reduced if for every two different
subpaths P and Q of W between consecutive terminals on W , and every crossing of P and Q, the
edges on P and Q that precede this crossing are not parallel.
Lemma 5.5. For every reduced T -simple walk W in G there exists a first-cross reduced T -simple
walk Wfc that traverses exactly the same set of edges as W . Furthermore, given W , such a walk Wfc
can be computed in polynomial time.

15

Proof. Let W = (e1 , . . . , ep ), and for i ∈ [p] let ui be the head of ei . For each index i, let the load of
i, denoted τ (i), be the smallest number t such that ui−t is a terminal (recall that indices behave
cyclically). Define the load of W to be
X
τ (W ) =
(τ (i) + τ (j)).
(i,j) : crossing of W

We give a polynomial-time procedure that given a reduced T -simple walk W in G that is not
first-cross, outputs a reduced T -simple walk W 0 that traverses exactly the same set of edges as
W , but W 0 has a strictly smaller load than W . Since the load of a T -simple walk is integral,
nonnegative, and bounded polynomially by the size of G, by applying this procedure exhaustively
after a polynomial number of iterations we eventually obtain a first-cross reduced T -simple walk
that can be output.
Since W is not first-cross, there is a self-crossing (i, j) of W , where edges ei , ej are parallel.
Denote v = ui = uj . Examine the parallel bunch to which ei and ej belong, and recall that
this bunch is linearly ordered. Among self-crossings of W not at terminals and where the edges
predeceasing the crossing are parallel, we choose (i, j) to be the one that minimizes the number of
edges on W , parallel to ei and ej that are between them in their parallel bunch. This minimization
criterion yields the following.
Claim 5.6. None of the edges parallel to ei and ej that are between them in their parallel bunch is
traversed by W .
Proof. For the sake of contradiction, suppose there is some edge ek on W , where k ∈
/ {i, j}, such
that ek is parallel to ei and ej and it appears between them in their parallel bunch. Since (i, j) is a
self-crossing of W at v, and in the cyclic order of edges around v all edges of the parallel bunch
of ei , ej appear consecutive and in the same order as in their bunch, it follows that either (i, k) or
(j, k) is a self-crossing, with both edges preceding the crossing parallel. However, in each of these
two cases, the number of parallel edges between the edges preceding the crossing would be strictly
smaller. This contradicts the choice of (i, j).
y
Consider now a closed walk W 0 obtained from W by swapping edges ei and ej ; that is, W 0 =
ej , and e0j = ei . As ei , ej are parallel, it is clear that
is reduced, it suffices to observe that by Claim 5.6,
the set of self-crossings of W 0 is exactly the same as the set of self-crossings of W , except the
self-crossing (i, j) is replaced with the self-crossing (i − 1, j − 1). Finally, since edges ei , ej are
parallel, we have that v is not a terminal, as terminals have exactly one incoming arc. Hence, we
have τ (i − 1) = τ (i) − 1 and τ (j − 1) = τ (j). It follows that τ (W 0 ) = τ (W ) − 2, hence we are
done.

(e01 , . . . , e0p ), where e0k = ek for k ∈
/ {i, j}, e0i =
W 0 is a T -simple walk in G. To see that W 0

Decomposing T -simple walks. Our goal now is to show that every reduced T -simple walk in
G can be decomposed into a small number of paths that interact with each other only in a limited
way. Moreover, for future use in the algorithm we will require that provided the said T -simple walk
is first-cross and T -short, the endpoints of the paths in the decomposition belong to some subset of
the vertices of size polynomial in the number of terminals. More precisely, each endpoint will be
important in the sense defined next.
First, we declare each terminal important. Next, we consider every quadruple of terminals
t1 , t2 , s1 , s2 , where t1 =
6 t2 , s1 6= s2 , t1 6= s1 , and t2 6= s2 . Choose shortest paths PG (t1 , t2 ) and
PG (s1 , s2 ) picking always the leftmost parallel edge in every traversed bunch. Let F be the set of
16

edges traversed by both these paths. On PG (t1 , t2 ), the edges of F form a family F of intervals.
Take any such interval I ∈ F, which is a subpath of PG (t1 , t2 ), and call it crossing if the following
holds: after contracting I to a single vertex the two edges preceding and succeeding I on PG (t1 , t2 ),
and the two edges preceding and succeeding I on PG (s1 , s2 ), appear in the interlacing order around
the contracted vertex; just as in the definition of crossing. Provided there are intervals in F that
are crossing, or simply PG (t1 , t2 ) crosses with PG (s1 , s2 ) without sharing any edges incident to the
crossing point, choose the crossing interval or the crossing that appears the earliest on PG (t1 , t2 ), and
declare the first (or only, in case it is just a crossing) vertex visited there by PG (t1 , t2 ) important.
Thus, the number of important vertices in G is at most |T |4 , which is polynomial in |T |. We
can now state the decomposition lemma.
Lemma 5.7. Every reduced T -simple walk W in G can be decomposed into ` < 9|T | subpaths
B1 , . . . , B` such that the following conditions are satisfied:
(a) no path Bi contains any terminal as an internal vertex,
(b) each path Bi has a crossing with at most one other path Bj , and
(c) there are fewer than 25|T | self-crossings of W that are not crossings of paths Bi and Bj , for
some i, j ∈ [`], i 6= j.
Furthermore, if W is first-cross reduced and T -short, then the decomposition B1 , . . . , B` may be
chosen so that the following additional condition is satisfied:
(d) each path Bi is a shortest path leading from one important vertex to another important vertex.
Proof. We first focus on defining the decomposition so that conditions ((a))–((c)) are satisfied. At
the end we shall argue why the defined decomposition satisfies also condition (d) in case W is
first-cross and T -short.
Let W = (e1 , . . . , ep ). As W is a T -simple walk, let (t1 , . . . , t|T | ) be the witnessing permutation
of the terminals, that is, W is the concatenation of the simple paths P1 , . . . , P|T | such that each Pi
leads from ti to ti+1 . For each j ∈ {1, . . . , |T |} we choose index ij ∈ {1, . . . , p} such that Pj is equal
to the subwalk (eij +1 , . . . , eij+1 ) of W .
Create an auxiliary graph H on vertex set x1 , . . . , xp , where xi can be thought of a copy of
the head of the edge ei (we also say that xi corresponds to the head of ei ). In H, we put an edge
between xi and xi+1 for each i = 1, 2, . . . , p (where xp+1 = x1 ), and moreover, for each self-crossing
(i, j) of W , we put an edge between xi and xj . The latter edges, corresponding to self-crossings, are
called internal. Note that since each terminal is visited exactly once on W , vertices xi1 , . . . , xi|T |
are the only vertices out of x1 , . . . , xp that correspond to terminals.
Claim 5.8. The graph H is outerplanar and has an outerplanar embedding where the cycle
(x1 , . . . , xp ) is the boundary of the outer face. Moreover, each vertex xij , for j ∈ [|T |], has degree 2
in H.
Proof. To see that H admits the desired outerplanar embedding, it suffices to show that there are
no indices i < i0 < j < j 0 such that both (i, j) and (i0 , j 0 ) are self-crossings of W . However, if this
was the case, then the self-crossing (i0 , j 0 ) would yield a crossing of the closed walks W1 and W2
obtained by splitting W at the self-crossing (i, j). Since W is reduced, this cannot happen.
To see that the vertex xij , corresponding to the terminal tj , has degree 2 in H, observe that
otherwise xij would be incident to some internal edge of H. This means that W would have a
self-crossing at tj , but W visits each terminal at most once; a contradiction.
y
17

Fix an outerplanar embedding of H as in Claim 5.8. Let S be a graph with vertex set consisting
of the inner faces of H, where two faces are considered adjacent if and only if they share an edge in
H. Since H is outerplanar and connected, it follows that S is a tree.
Consider now any leaf f of S. Then the boundary of f consists of one edge of H corresponding
to some self-crossing (i, j) of W , say at vertex v of G, and a subpath Qf of the cycle (x1 , . . . , xp ) in
H. For leaves f of S, the subpaths Qf are pairwise edge disjoint.

Figure 2: The original closed walk W (left panel) and the outerplanar graph H constructed based
on W (right panel). Terminals are depicted by yellow squares, the tree S is depicted in blue, the
cycle (x1 , . . . , xp ) is depicted using solid gray edges, while dashed Gray edges are the internal edges
of H. Special edges are colored orange, while red lines depict places where we put dividing points
for defining blocks. They correspond to vertices depicted by red circles in the left panel, which are
important in case W is T -short and first-cross.
Claim 5.9. For each leaf f of S, the subpath Qf contains at least one vertex xij , for some j ∈ [|T |],
as an internal vertex. Consequently, the tree S has at most |T | leaves.
Proof. For the first claim, observe that Qf corresponds to a closed subwalk Wf of W obtained by
splitting W at a self-crossing. Observe that Wf cannot be entirely contained in any of the paths Pj ,
since Wf visits v twice whereas a simple path cannot visit any vertex more than once. Hence, Qf
contains some vertex xij as an internal vertex. The second claim follows by noting that paths Qf
are pairwise edge disjoint for different leaves f of S, and there are |T | vertices xij .
y
Observe that in the duality of H and S, the edges of S are the dual edges of the internal edges of
H. By somehow abusing the notation, we identify each internal edge of H with its dual edge in S.
We now define the set I ⊆ V (S) of special edges of S as follows. First, for each vertex f of S
of degree at least 3 in W , we mark all edges incident to f special. Second, for each vertex xij , for
j ∈ [|T |], we find such the unique index hj ∈ [p] such that none of vertices xij , . . . , xhj −1 is incident
to any internal edges of H, but xhj is incident to such an edge. Then there is a unique special edge

18

of H that is incident both to xhj and the internal face of H on which xij lies (this face is unique
since xij has degree 2 in H). We mark this internal edge important as well.
Claim 5.10. There are less than 4|T | special edges in S.
Proof. It is well known that in every tree with at most k leaves, the total number of edges incident
to vertices of degree at least 3 is at most 3k − 6. Hence, since S has at most |T | leaves by Claim 5.9,
less than 3|T | edges of S were marked as special in the first step of marking. In the second step of
marking we mark one edge per each terminal, so the total upper bound of less than 4|T | follows. y
We divide the walk W = (e1 , . . . , ep ) into blocks as follows. For any i ∈ [p], declare xi a dividing
point if either xi corresponds to a terminal (i.e. i = ij for some j ∈ [|T |]), or xi is an endpoint of
a special edge. Then blocks are maximal subwalks of W that do not contain any dividing points
as internal vertices. More precisely, the sequence (ei+1 , ei , . . . , ei0 ) is a block if both xi and xi0 are
dividing points, but none of vertices xi+1 , . . . , xi0 −1 is a dividing point. It is clear that blocks form a
partition of W into less than 9|T | subwalks, as there are less than 9|T | dividing points by Claim 5.10.
Let B1 , . . . , B` be the obtained blocks It suffices to verify that the decomposition B1 , . . . , B` has all
the required properties. Observe that condition (a) is holds trivially, as we explicitly took all visits
of terminals by W as dividing points.
For condition (b), let Di be the subpath of the cycle (x1 , . . . , xp ) in H that corresponds to
the block Bi , for i = 1, . . . , `. Note that every crossing of paths Bi and Bi0 , for i 6= i0 , is also a
self-crossing of W that corresponds to an internal edges of H that connects an internal vertex of Di
with an internal vertex of Di0 . Fix now some block Bi ; we want to argue that there is at most one
other block Bi0 such that Bi and Bi0 cross.
Observe that every connected component of S − I, the tree S with the special edges removed,
either consists of one vertex being a leaf or a vertex of degree at least 3 in S, or is a path consisting
only of vertices of degree 2 in S. This is because any edge incident to a leaf of S is always marked
as special by Claim 5.9. By the construction of blocks, the set of internal faces of H incident to the
edges Di can be spanned by a subtree of S that does not contain any special edge. Consequently,
either all the edges of Bi are incident to the same internal face of H (and hence they form an
interval on its boundary), or there is a path R in S, consisting only of vertices of degree 2 connected
by non-special edges, such that all the edges of Di are incident to the faces on this path. In the
former case, Bi does not cross any other block Bj , as all internal vertices of Di have degree 2 in H.
In the latter case, it is easy to see that all the edges of the cycle (x1 , . . . , xp ) that are incident to
some non-endpoint face of R but do not lie on Di , are in fact in the same subpath Di0 for some
i0 6= i. Then all internal edges of H incident to the internal vertices of Di have the second endpoint
on Di0 , so Bi0 is the only block that may cross Bi . This establishes condition ((b)).
For condition (c), we shall use the following claim.
Claim 5.11. Suppose e1 , e2 are two internal edges of H incident to the same vertex xi , and also
incident to a common internal face of H. Then at least one of e1 , e2 is special.
Proof. Let f be the internal face of H incident to both e1 and e2 . Obviously the degree of f in S
is at least 2 due to edges e1 , e2 , and we may assume that it is exactly 2, since otherwise both e1
and e2 would be special. Consequently, e1 , e2 are the only internal edges of H incident to f , so the
boundary of f consists of e1 , e2 , and some subpath L of the cycle (x1 , . . . , xp ) whose internal vertices
have all degree two in H. We may assume that none of the vertices traversed by L corresponds to a
terminal, as otherwise either e1 or e2 would be marked as special. In particular, this implies that all
the edges of L belong to the same block.

19

Let xi1 and xi2 be the second endpoints of e1 and e2 , different from xi , respectively. Then
both (i, i1 ) and (i, i2 ) are self-crossings of W and xi , xi1 , xi2 correspond to the same vertex v of G.
However, we have already argued that each block is entirely contained in one path Pj , for some
j ∈ [|T |], so xi1 and xi2 would correspond to two visits of the same vertex v within the same path
Pj , which is assumed to be simple, as W is a T -simple walk. This is a contradiction.
y
Observe now that self-crossings of W that are not crossings of two distinct blocks are exactly
those self-crossings (i, i0 ) for which either xi or xi0 is a dividing point. Hence, to give an upper
bound on the number of such self-crossings, it suffices to estimate the number of internal edges
of H incident to a dividing point. Take any dividing point xi and examine the internal edges of
H incident to xi in the cyclic order around it, as in the (outerplanar) embedding of H. Then by
Claim 5.11, out of any two consecutive ones, at least one is special. It follows that if xi is incident
to d special edges, then it is incident to at most 2d + 1 internal edges of H. Since every special edge
has two endpoints, it follows that the total number of internal edges incident to a dividing point
is upper bounded by the number of dividing points plus four times the number of special edges.
These quantities are smaller by 9|T | and 4 · 4|T |, respectively, so the upper bound of less than 25|T |
follows.
Thus, we have verified conditions (a), (b), and (c), so we are left with verifying condition (d)
assuming additionally that W is T -short and first-cross. Since W is T -short, each path Pj is the
shortest path from tj to tj+1 , so every its subpath is also the shortest path between its endpoints.
This implies that each block Bi is the shortest path between its endpoints, so it remains to show
that these endpoints are important. To this end, we will use the following claim.
Claim 5.12. Suppose we have indices 1 ≤ j, j 0 ≤ |T |, j 6= j 0 . Suppose further on the subpath
of (xij , xij +1 , . . . , xij+1 ), vertex xk is the first one that is adjacent in H to any of the vertices
xij 0 , xij 0 +1 , . . . , xij 0 +1 via an internal edge of H. Then xk corresponds to an important vertex in G.
Proof. It can be easily seen that if xk corresponds to a vertex v, then v is included in the set of
important vertices when considering the quadruple of terminals (tj , tj+1 , tj 0 , tj 0 +1 ). This is because
W is first-cross, so when the crossing between subpaths from tj to tj+1 and from tj 0 to tj 0 +1 that
is the first in the former path corresponds to a crossing interval on PG (tj , tj+1 ), then the actual
crossing in W occurs on the first vertex of this interval.
y
We now proceed with verification that all the dividing points used in the definition of blocks
correspond to important vertices. This is done explicitly for terminals, so we are left with verifying
this for endpoints of special edges. Suppose that an internal edge e = (xi , xi0 ) of H is special. Then
xi and xi0 correspond to the same vertex v of G such that (i, i0 ) is a self-crossing of W at v. We
have two cases, depending on why e was marked as special.
Suppose first that e was marked as special due to being incident to some internal face f of H of
degree at least 3 in S. This means that in S, f has at least two other incident edges, and suppose
e1 and e2 are the edge incident to f that are directly preceding and succeeding e in the counterclockwise order of edges of S incident to f ; here, we assume that the cycle (x1 , . . . , xp ) is oriented
counter-clockwise in the plane. Further, suppose without loss of generality that e1 , xi , e, xi0 , e2
are in this counter-clockwise order on the boundary of face f . Now, let j 1 ∈ [|T |] be such that
on the subpath (xij 1 , xij 1 +1 , . . . , xi ) no internal vertex corresponds to a terminal, and similarly
let j 2 ∈ [|T |] be such that on the subpath (xi0 , xi0 +1 , . . . , xij 2 ) no internal vertex corresponds to
a terminal. Observe that since each leaf f 0 of S has a vertex corresponding to a terminal among
internal vertices of Qf (Claim 5.9), vertices xij 1 , xij 2 −1 , and xij 2 lie on the following parts of the
cycle (x1 , . . . , xp ):
20

• denoting e1 = xr11 xr21 , where xr11 xr21 , and xi lie in this order on (x1 , . . . , xp ), we have that xij 1
is an internal vertex of (xr11 , . . . , xi );
• xij 2 −1 is an internal vertex of (xi , . . . , xi0 ); and
• denoting e2 = xr12 xr22 , where xi0 , xr12 , and xr22 lie in this order on (x1 , . . . , xp ), we have that
xij 2 is an internal vertex of (xi0 , . . . , xr22 );
In particular, all the vertices xij 1 , xij 2 −1 , and xij 2 are pairwise different, and moreover e is the
internal edge of H connecting (xij 1 , xij 1 +1 , . . . , xij 1 +1 ) with (xij 2 −1 , xij 2 −1 +1 , . . . , xij 2 ) that has the
earliest possible endpoint on the former path. The fact that v is then important follows from
applying Claim 5.12 to j = j 1 and j 0 = j 2 − 1.
Suppose now, without loss of generality, that e was marked special due to the following situation:
i = hj for some terminal tj , and e is the unique edge incident to xi that is also incident to the
internal face f of H on whose boundary lies xij . Then on the subpath (xij , xij +1 , . . . , xi ), all vertices
have degree 2 in H, apart from xi itself, so in particular they are not incident to any internal edge
of H. Suppose now that j 0 ∈ [|T |] is such that on the subpath (xij 0 , xij 0 +1 , . . . , xi0 ) no internal
vertex corresponds to a terminal. By Claim 5.9 it is easy to see that j 6= j 0 . Moreover, from the
previous observation it follows that xi is the earliest vertex on (xij , xij +1 , . . . , xij+1 ) that is adjacent
to any vertex of (xij 0 , xij 0 +1 , . . . , xij 0 +1 ) via an internal edge of H, because the earlier vertices were
not incident to any internal edges at all. The fact that v is then important follows from applying
Claim 5.12 to j and j 0 .

5.2

Enumerating subsets of a clean walk

Our main technical result, proved in this section, is that any√reduced T -short walk can be hierarchically decomposed using closed curves of “complexity” |T |O( |T |) . We first formalize what we mean
by a decomposition. In this section C ≥ 1 is a sufficiently large universal constant, whose value will
emerge from the proof.
Definition 5.13. Let W be a T -short walk and let πW = (t1 , t2 , . . . , t|T | ) be a witnessing permutap
tion. A set A ⊆ T is a good section of (W, πW ) if A can be partitioned into at most C |T | subsets
that form contiguous subsequences of πW .
A good decomposition of W and πW is a pair (T , β) where T is a rooted binary tree and
β : V (T ) → 2T is a function with the following properties:
(1) β(v) is a good section of (W, πW ) for every v ∈ V (T );
(2) β(r) = T for the root r of T ;
(3) every non-leaf node v of T has two children v1 , v2 with β(v1 ) ∩ β(v2 ) = ∅, β(v) = β(v1 ) ∪ β(v2 );
p
(4) every leaf node v of T satisfies |β(v)| ≤ C |T |.
p
Note that both T and every set A ⊆ T of size at most C |T | is always a good section, regardless
of the choice of W and πW .
The main result of this section is the following.
Theorem
5.14. Given a preprocessed Directed Subset
√
√ TSP instance (G, T ), one can in time
O( |T |) O(1)
O( |T |)
T
|T |
n
compute a family B ⊆ 2 of size |T |
such that for every first-cross reduced
T -short walk W and its witnessing permutation πW , there exists a good decomposition (T , β) of
(W, πW ) such that every set β(s) for s ∈ V (T ) belongs to B.
21

The rest of this section is devoted to the proof of Theorem 5.14. Fix the walk W as in the
statement. Recall that in the input graph, we assume that every terminal t has a unique neighbor
wt , connected by two arcs (t, wt ) and (wt , t), while every other arc is copied |T | times; a set of
parallel copies of the same arc is called a parallel bunch. Furthermore, without loss of generality we
assume that G is strongly connected; this is because all terminals have to lie in the same strongly
connected component of G for a solution to exist, and we can restrict our attention to this strongly
connected component. For a terminal t, let ft0 be the 2-face between the arcs (t, wt ) and (wt , t), and
let ft be the other face incident with t.
We start with the following augmentation of the input graph; see Figure 3 for an illustration.
First, we temporarily collapse every parallel bunch of G back into a single edge.
Second, we select an arbitrary minimal tree T ? in the dual of G that spans all faces ft and does
not contain any face ft0 for t ∈ T . We fix some drawing of T ? such that every face of G contains at
most one vertex of T ? and every arc of T ? intersects exactly one arc of G, namely its dual, in one
point. For every t ∈ T , we connect the vertex ft of T ? with the terminal t with an arc (t, ft ).
Third, we add to G the tree T ? with all arcs (t, ft ), t ∈ T , in the natural manner: we add all
vertices of T ? to G and, whenever an arc of T ? intersects its dual arc in G, we subdivide both
arcs and add a new vertex at the point of intersection. During the subdivision, we distribute the
weight of the arc of G arbitrarily between its parts, while all the new arcs of T ? , as well as its
f denote the tree in the augmented
connections to the terminals, are assigned weight +∞. Let W
?
graph G consisting of the (subdivided) arcs of T together with the arcs (t, ft ), t ∈ T . In this
f is a tree spanning all terminals in G. We remark here that, due to the weight +∞ on
manner, W
f , the directions of arcs of W
f are irrelevant to the algorithm. Intuitively, the purpose
the arcs of W
f
of W is to control the homotopy types of closed curves in the plane punctured at the terminals, by
f.
examining how they cross with W
f ) that is not incident to a terminal |T | times, and
Finally, we duplicate every arc of G − E(W
project W onto the modified graph accordingly: if W traversed the i-th copy of an arc e before the
collapse of parallel bunches, then after the modifications it traverses the i-th copies of all the arcs
into which e has been subdivided. This operation does not break the property that W is first-cross
reduced. As before with the arcs incident with terminals, for notational convenience we treat every
f as a parallel bunch on its own. Observe that, since we added only arcs of weight +∞ and
arc of W
G is strongly connected, we maintain the property that G has unique shortest paths and that W is
T -short.
f , that is, new vertices drawn inside
Let VF be the set of vertices of T ? that become vertices of W
former faces of G (but not the vertices drawn at the crossing points of arcs of T ? and their duals).
By Lemma 5.7, the walk W can be decomposed into ` = O(|T |) paths B1 , B2 , . . . , B` such that
every Bi crosses at most one other path Bj . Furthermore, since W is first-cross reduced and T -short,
we can assume that every endpoint of a path Bi is an important vertex of G.
Graph lift. We extend graph G to a lift G• as follows; see Figure 4 for an illustration. We start
with G• equal to G. For every vertex v ∈
/ T ∪ VF , we draw a small circle Cv with center in v. For
every intersection of Cv with the drawing of G, we subdivide the corresponding arc and place the
subdividing vertex at this intersection. The full weight of the original arc is kept on the part outside
Cv . Next, we remove from the graph all the edges whose drawings are inside the circle Cv . For
every pair of newly introduced vertices x, y on Cv , where x lies on an in-arc and y lies on an out-arc
of v, we add an edge (x, y) of weight 0 embedded using a straight-line chord between embeddings of
x and y inside Cv . By slightly shifting the drawing of G beforehand, we may assume that no three
such chords intersect at the same point. To make the embedding planar, at every intersection of

22

f . Terminals are yellow squares, the tree
Figure 3: Augmentation of the graph G to add the tree W
f
f
W is depicted in blue. The directions of the arcs of W are irrelevant to the algorithm, and hence
omitted in the figure.

23

Figure 4: From G to G• . The panel on the left shows a vertex v ∈ V (G) with two incoming parallel
bunches and two outgoing. The panel on the right shows the corresponding circle Cv and the chords
drawn inside; at every intersection of two chords there is a vertex of G• . Two parts of a walk W
(red and blue) that correspond to a crossing at v are lifted to red and blue paths on the right in G• .
two chords we place a new vertex and use it to subdivide the chords.
There is a natural projection of vertices, edges, and paths from G• to G, by collapsing, for every
v ∈ V (G) \ T , the circle Cv together with all vertices and arcs on and inside it onto the vertex v.
We denote this projection by η. Furthermore, every arc e = (u, v) ∈ E(G) has its lift η −1 (e), which
is an edge in G• : the one going from either u (if u ∈ T ∪ VF ) or the point at the intersection of e
with Cu (if u ∈
/ T ∪ VF ) to either v (if v ∈ T ∪ VF ) or the point of the intersection of e with Cv (if
v∈
/ T ∪ VF ).
The walk W has its naturally defined lift to a walk W • in G• : follow W starting and some
terminal and, for every visited nonterminal vertex v, if the drawing of W around v intersects the
cycle Cv in x before v and in y after v, then we go from x to y along the chord (x, y) in the
f • of W
f analogously. Note that W
f • is a tree in G• , while W • is a
lift W • . We define the lift W
walk, whose self-intersections are in one-to-one correspondence with self-crossings of W ; here, by
a self-intersection of a walk we mean a pair of two different visits of the same vertex. Moreover,
f.
for every self-intersection of W • at a nonterminal vertex v, the projection η(v) does not lie on W
Finally, W • visits every vertex of G• at most twice. We will follow the convention that W has
self-crossings while W • has self-intersections; note here that every self-intersection of W • is also its
self-crossing.
Untwisting pairs of paths. We now define a family of paths P that are subpaths of the paths
Bi . First, we insert into P every path Bi that does not cross any other path Bj . For pairs of paths
Bi and Bj that cross each other and i < j, we proceed as follows. Let v1 and v2 be the vertices of
the first and last crossing of Bi and Bj , where first and last refer to the order on Bj . These two
crossing points split each of Bi and Bj into three subpaths (two, if v1 = v2 ). We insert into P all
three subpaths of Bi and the two side subpaths of Bj (i.e., except the one between v1 and v2 ); in
the case v1 = v2 , we insert into P all the four subpaths. See Figure 5 for an illustration.

24

Bj

v2
v1

Bi

Bj

v2
v1

Bi

Figure 5: Construction of the family P. For every two paths Bi and Bj with i < j that cross (red
and blue paths in the figure), we insert into P all but one subpaths into which v1 and v2 (the first
and the last crossing of Bi and Bj w.r.t. the order on Bj ) split Bi and Bj . The omitted subpath is
the part of Bj between v1 and v2 , depicted by dashed blue in the figure. From the fact that Bi and
Bj are shortest paths in G, one could argue that the situation in the bottom panel is impossible,
and the two crossing paths always look as in the top panel. However, we will not use this fact in
the proof, and hence we do not formally prove it.

25

Observe that P is a family of O(|T |) subpaths of W that are pairwise noncrossing. Let S be
the set of endpoints of the paths in P. Furthermore, the fact that the paths Bi have endpoints in
important vertices implies the following.
Claim 5.15. We can compute a set S̄ ⊆ V (G) of size at most O(|T |18 ) that contains S.
Proof. We first insert into S̄ all important vertices (which, in particular, includes all terminals);
recall that there are at most |T |4 of them. This covers the endpoints of all paths Bi that do not
intersect every other path Bj and were directly inserted into P. To cover the endpoints of subpaths
of paths Bi and Bj , i < j, that intersect each other, we proceed as follows. We first iterate over all
tuples (si , ti , sj , tj ) of four important vertices (these are |T |16 options), and focus on the case where
the path Bi leads from si to ti and Bj leads from sj to tj . By the assumption that G has unique
shortest paths, we can compute a path Bi0 parallel to Bi and Bj0 parallel to Bj . Second, we iterate
over all pairs (ei , ej ), where ei is an arc parallel to the last arc of Bi0 and ej is an arc parallel to the
last arc of Bj0 ; there are |T |2 choices of such a pair. We focus on the case where ei is the last arc of
Bi and ej is the last arc of Bj .
We observe that the assumption that W is first-cross reduced allows us to infer all vertices
where Bi and Bj cross from the paths Bi0 , Bj0 , and arcs ei and ej , similarly as in the definition of
important vertices. That is, the crossings happen at vertices v for which there is an arc ei,v on Bi0
with head v and an arc ej,v on Bj0 with head v, such that ei,v and ej,v are not parallel and, if Bi,v
and Bj,v are the maximal parallel subpaths of Bi0 and Bj0 starting at v that do not contain the last
0 lie on different sides of B 0 (that is, after
arcs ei and ej , then the arcs preceding and succeeding Bi,v
j
0
contracting Bi,v we see a crossing at the contracted vertex). We insert the first and the last such
crossing vertex on Bj0 into S̄ for every choice of (si , ti , sj , tj ) and (ei , ej ).
y
We now lift the paths P to a family of paths P • in G• . First, for every path Bi , we define
its lift Bi• to be the subpath of W • from the lift of the first arc of Bi to the lift of the last arc
of Bj , inclusive. We define the set S • ⊆ V (G• ) to be the set of all terminals and all vertices at
self-intersections of W • except for the following: for every pair of paths Bi and Bj that cross each
other, i < j, we insert into S • only the first and the last intersections of the lifts Bi• and Bj• into S •
(where, again, first and last refer to the order on Bj ). Observe that we have η(S • ) = S, but there
may be many different vertices v ∈ S • with the same projection η(v) ∈ S.
Claim 5.15 allows us to enumerate a small set of candidates for endpoints in S • .
Claim 5.16. We can compute a set S̄ • ⊆ V (G• ) of size bounded by O(|T |54 ) that contains S • .
Proof. Consider a self-intersection of W • at vertex v. This self-intersection corresponds to a selfcrossing of W at η(v), which consists of two different visits of η(v) on W . Say that (e1 , e3 ) are the
arcs traversed by W preceding and succeeding the first considered visit of η(v), while (e2 , e4 ) are
the arcs preceding and succeeding the second considered visit. Observe that the vertex v is uniquely
determined by e1 , e2 , e3 , and e4 : it is the intersection of the chord from the head of η −1 (e1 ) to
the tail of η −1 (e3 ), and the chord from the head of η −1 (e2 ) to the tail of η −1 (e4 ). Furthermore,
the number of options this quadruple edges is bounded by O(|T |54 ) as follows. We can first pick
any η(v) ∈ S̄ for S̄ coming from Claim 5.15 (O(|T |18 ) options), and then every arc ej can be
inferred from the knowledge of: the endpoints of the path Bi it lies on (which requires guessing two
important vertices, at most |T |8 options) and its index in the parallel bunch to which it belongs
(|T | options).
y
Observe that |S • | = O(|T |), due to the fact that W has only O(|T |) crossings that are not
crossings of pairs of paths Bi and Bj (Lemma 5.7).
26

We define the family P • to be the family of paths into which S • splits the walk W • , except for
the following subpaths. For every pair of paths Bi and Bj that cross at least twice and i < j, the
lifts Bi• and Bj• contain exactly two vertices of S • , corresponding to the first and the last crossings
of Bi and Bj along Bj . Denote the vertices of these self-intersections of W • as uj , vj ∈ V (G• ), and
let Bimid and Bjmid be the subpaths of Bi• and Bj• between uj and vj . We do not put Bjmid into P • ,
similarly as we did not put the subpath of Bj between η(uj ) and η(vj ) into P.
Note that every path P ∈ P has its corresponding path (called henceforth lift as well) P • ∈ P •
with η(P • ) = P . However, observe two delicate matters. First, apart from the lifts of the paths from
P, the family P • may contain short paths between two consecutive crossings inside one circle Cv .
Second, even if P = Bi for some P ∈ P, the lift P • may be slightly longer than the lift Bi• defined
earlier, as P • may contain some edges inside Cu and Cv for u and v being the endpoints of P . Since
we will no longer use the lifts Bi• in this proof, we allow this slight abuse of notation.
Graphs H, H × , and an sc-branch decomposition. We define a subgraph H of G• as the
f • and all paths from P • .
union of W
Although H is a plane graph, it can have unbounded number of vertices and potentially large
branchwidth. Let H × be the graph obtained from H by contracting, for every Q ∈ P • , all internal
vertices of Q into one vertex uQ . Thus, Q gets contracted into a path Q× consisting of two edges and
three vertices: the former endpoints and uQ . Recall that since the paths of P • are vertex-disjoint
except for possibly having common endpoints, the contractions on different paths Q ∈ P • do not
interfere with each other.
We have the following bound.
p
Claim 5.17. The graph H × admits an sc-branch decomposition (T , ζ, γ) of width O( |T |).
Proof. First, note that H × is connected. Let H 0 be the graph H × with all vertices of degree 2
suppressed (i.e., every maximal path with internal vertices of degree 2 replaced by a single edge).
It suffices to show that H 0 admits such a decomposition, as it is straightforward to adjust the
decomposition for H 0 to a decomposition
of H × of the same width. By Theorem 3.2, it suffices to
p
show only that H 0 has branchwidth O( |T |). To this end, note that every vertex of H 0 is either a
terminal, or one of the three vertices of the contracted path Q× for some Q ∈ P • . As |P • | = O(|T |),
we have that |V (H 0 )| = O(|T |), and the claim follows from Theorem 3.1.
y
Let (T , ζ, γ) be the sc-branch decomposition of H × given by Claim 5.17. Recall that, given a
closed curve γ without intersections, by a tri-partition of the terminals induced by γ we mean a
tuple (T0 , {T1 , T2 }) where T0 is the set of terminals on γ, and T1 and T2 are sets of terminals on
the two sides of γ. With a noose γ(f ) for some f ∈ E(T ) we can also associate another partition
{T10 , T20 } with T = T10 ] T20 , called henceforth the arc-induced partition: a terminal t belongs to
T10 or T20 depending on the side of γ that contains the arc (t, wt ). Observe that, if γ(f ) induces a
tri-partition (T0 , {T1 , T2 }) and arc-induces a partition {T10 , T20 }, then we have Ti ⊆ Ti0 ⊆ Ti ∪ T0 for
i = 1, 2, provided we assume that Ti and Ti0 correspond to the same side of γ(f ).
Branch decomposition gives good decomposition. We now show that a good decomposition
of W inferred from the sc-branch decomposition (T , ζ, γ). Root the tree T at an arbitrary leaf
r such that ζ(r) is not of the form (t, wt ) for a terminal t and define β(r) = T . For every node
s ∈ V (T ) \ {r} with a parent edge f , we define β(s) as follows. Let {T10 , T20 } be the partition of the
terminals arc-induced by γ(f ) and assume that the side of γ(f ) that contains ζ(r) corresponds to
the set T20 . Then, we put β(s) = T10 .

27

In the next two claims we verify that (T , β) is a good decomposition of W (formally, after
removing the root in order to have a binary tree). We first verify that arc-induced partitions of
nooses are actually good sections of W .
Claim 5.18. If C is a sufficiently large universal constant, then for every edge f ∈ E(T ), if
(T0 , {T1 , T2 }) is the tri-partition induced by γ(f ), then every set T 0 with Ti ⊆ T 0 ⊆ T0 ∪ Ti for some
i = 1, 2 is a good section of W and πW .
p
Proof. Intuitively, the claim follows from the fact that γ(f ) visits only O( |T |) vertices of H × ,
and each such vertex can be modeled as only one crossing with W . However, we need to be a bit
careful with the formal proof, because in the construction of P and, consequently, H, we sometimes
drop part of a path Bj if there was another path Bi crossing it.
We proceed to the formal argumentation. Let us take the graph H and forget the directions of
the edges; denote the obtained undirected graph by H 0 . From a walk W • , we construct a walk W 0
as follows: for every pair of paths Bi and Bj that cross, where i < j, consider subpaths Bimid and
Bjmid as defined in the previous paragraph. We replace the subpath Bjmid with (possibly traversed in
the reverse direction) path Bimid . Note that W 0 is a walk in H 0 , visits every vertex of H 0 a constant
number of times, and visits the terminals in the same order as Wp
.
We now show that there is a noose γ 0 that intersects W 0 in O( |T |) vertices and that keeps the
same set of terminals of G inside, on, and outside as γ(f ). First, set γ 0 to be an “uncontraction” of
γ(f ), defined as follows (see Figure 6).
• Whenever γ(f ) traverses a face f0 of H × from a vertex v1 to v2 , γ 0 traverses the corresponding
face f00 of H between the vertices v10 and v20 that were contracted onto v1 and v2 , respectively.
• Whenever γ(f ) traverses a vertex uQ of H × , for some Q ∈ P • , the curve γ 0 goes along a
subpath of Q.
• Whenever γ(f ) traverses a vertex v of H × that is not of the form uQ , for some Q ∈ P • , γ 0
traverses v as well.
Note that while at this point γ 0 is formally not a noose, due to possibly travelling along subpaths of
paths Q ∈ P • , it is a closed curve in the plane without self-intersections. This is because the paths
in P • are vertex-disjoint except for possible common endpoints.
Second, we shift γ 0 slightly along every traversed subpath of a path Q ∈ P • so that γ 0 follows Q
parallely in a small neighborhood of Q, crossing it once
p at a vertex if needed, and not more than
• at O( |T |) vertices, it follows that γ 0 intersects
once. Since
γ
intersected
the
embedding
of
G
p
W 0 at O( |T |) vertices. Since no path in Q ∈ P • has a terminal as an internal vertex, the above
operations do not change the set of terminals inside, on, p
and outside γ(f ) and γ 0 .
0
0
Note that since γ is a curve that intersects W at O( |T |) vertices and W 0 visits
p every vertex
0
0
0
a constant number of times, the intersections of γ with W split W into O( |T |) subwalks
W10 , W20 , . . .. Each subwalk Wj0 visits terminals of T0 ∪ T1 or T0 ∪ T2 only, depending on the side of
γ 0 it lies on. Furthermore, the terminals at endpoints of walks Wj0 are exactly all terminals of T0 .
To conclude, assume T 0 ⊆ T is such that Ti ⊆ T 0 ⊆ T0 ∪ Ti for some i ∈ {1, 2}. Define a family
R of subsets of T as follows: we take every subwalk Wj0 that lies on the same side of γ 0 as Ti , remove
from Wj0 any endpoint that belongs to T0 \ T 0 , thus obtaining a walk Wj00 , and insert into R the set
of terminals traversed by Wj00 . Observe that R is a partition of T 0 into subsets that form contiguous
intervals in the cyclic order of terminals visited by W 0 . Since the order of visiting terminals is the
same on W and on W 0 , we infer the same conclusion for W . This finishes the proof of the claim. y
Second, we verify the remaining properties of a good decomposition.
28

Figure 6: Uncontraction performed in the proof of Claim 5.18. The first two panels show a path
Q ∈ P • in H and its corresponding two-arc path in H × , with the new vertex uQ in red. A visit
of the vertex uQ by the green curve γ(f ) in the third panel gets uncontracted to the part of γ 0
depicted in green in the fourth panel.

29

Claim 5.19. (T − r, β) is a good decomposition of W and πW .
Proof. Let us verify the properties of a good decomposition one-by-one. Property (1) is ensured by
Claim 5.18. We have β(r) = T by definition, and note that by the choice of ζ(r) we have β(r0 ) = T
for the unique child r0 of r in T . This ensures property (2) For property (3), pick a non-leaf non-root
node s of T , and observe that it has always exactly two children, say s1 and s2 . Let f be the edge
of T connecting s with its parent, and let f1 , f2 be edges connecting s with s1 , s2 , respectively. By
the properties of a branch decomposition, the set of edges on the side of γ(f ) that does not contain
ζ(r) is partitioned into sets defined in the same manner for γ(f1 ) and γ(f2 )}. As β(s), β(s1 ), β(s2 )
are defined by including every terminal t depending on whether the edges (t, wt ) is included in the
sets above, property (3) follows. Finally, for property (4), note that for a leaf s with parent edge f ,
the noose γ(f ) encloses a single edge, and thus |β(s)| ≤ 1.
y
Thus, our goal now is to construct a small family of subsets of T that contains all sets Ti0 for
partitions {T10 , T20 } arc-induced by nooses γ(f ) for f ∈ E(T ).
Guessing parts of the walk W . Intuitively, the idea now is that a noose γ = γ(f ) for some
f ∈ E(T ), or more precisely the tri-partition of terminals it induces, may be guessed as follows.
Curve γ, as a noose in H × , may be uncontracted to a noose γ 0 as in the proof of Claim 5.18; this
modification does not change the set of enclosed terminals. Now γ 0 travels alternately via faces of
•
H and
between these two modes
palong subpaths of paths from P , and the number of alternations
•
is O( |T |). Intuitively, the traversed subpaths of paths from P may be guessed efficiently by
guessing the endpoints and drawing shortest paths; we know that the endpoints belong to the set
S̄ • given by Claim 5.16, a set of size bounded polynomially in |T |. Having guessed these paths, we
are left with guessing the rest of γ. However, as we are only interested in the tri-partition induced
f • plus the guessed paths, with the internal parts of
by γ, so it remains to apply Lemma 4.1 to W
p
the guessed paths contracted. Then the number of crossing points we are interested in is O( |T |).
One of the technical problems we encounter is that, even if we know two endpoints of a path
Q ∈ P • with the help of Claim 5.16, and we can deduce a path parallel to the projection η(Q) since
it is a shortest path between its endpoints, we do not know how exactly η(Q) travels in the graph
G• , as we do not know which arcs in parallel bunches η(Q) uses. However, we will now rely on the
fact that the paths in P do not cross each other to show that, up to some shifts, there are only
|T |O(|L|) ways to embed L paths from P • .
Let Q ⊆ P • be a family of L paths, and let Q0 be a family of paths in G• that are pairwise
vertex-disjoint apart from possibly sharing endpoints. We say that Q0 is a shift of Q if there is a
bijection that maps every Q ∈ Q to a corresponding path Q0 ∈ Q0 with the following properties:
1. η(Q) and η(Q0 ) are parallel, and start and end with the same arc;
2. Q and Q0 have the same starting vertices, and travel along the same subpath up to η −1 (e)
(inclusive), where e is the first arc on η(Q), equivalently the first arc on η(Q0 );
3. a symmetric property holds for the ending vertices of Q and Q0 ; and
4. the bijection Q 7→ Q0 preserves the order of the paths inside the lift of every parallel bunch of
arcs. In other words, if Q1 , . . . , Qp are paths from Q such that η(Q1 ), . . . , η(Qp ) all traverse
some parallel bunch, then the relative orders of arcs within this bunch that are used by
η(Q1 ), . . . , η(Qp ), respectively, and that are used by η(Q01 ), . . . , η(Q0p ), respectively, coincide.
In particular, if Q is one of the short paths completely contained in one circle Cv , then Q = Q0 .
We prove the following enumeration statement.
30

Claim 5.20. Given an integer L, one can in time (|T |L)O(|L|) nO(1) compute a family of (|T |L)O(L)
families of paths in G• such that for every set Q ⊆ P • of size L there exists a shift of Q in the
computed family.
Proof. It is convenient for us to describe the enumeration as a guessing procedure that guesses,
with the total number of subcases being (|T |L)O(L) , a family of paths Q0 that is a shift of a fixed
family Q ⊆ P • of size L.
Let Q = {Q1 , Q2 , . . . , QL }. For every path Qi we guess the following information. First, we
guess the endpoints ui and vi of η(Qi ); by Claim 5.16, we may guess this vertices from the set S̄ • ,
so the number of options is O(|T |108 ). If both ui and vi lie in the same circle Cη(ui ) , then Qi is a
subpath of the unique chord that contains both ui and vi , that is, is completely determined by its
endpoints. Hence, we can from this point ignore such paths Qi .
For other paths, we compute a shortest path Pi0 in G from η(ui ) to η(vi ); observe that Pi0 is
parallel to Pi := η(Qi ). Given Pi0 , we guess the first and the last arc of Pi ; there are |T | options
for each, as they need to be parallel to the first and the last arc of Pi0 , respectively. Denote these
arcs eui and evi , respectively. Note that the knowledge of ui , vi , eui , and evi allows us to deduce the
prefix of Qi up to η −1 (eui ) and the suffix from η −1 (evi ) to the end: these are subpaths of appropriate
chords within Cη(ui ) and Cη(vi ) , respectively. Finally, we define ι[u, ←] ∈ [L] ∪ {⊥} as follows: we
look at the parallel bunch of eui , find the first arc in the counter-clockwise direction from eui that
belongs to some path in Q, and pick ι[u, ←] to be the index of this path. We pick ι[u, ←] = ⊥ if
there is no such path. Similarly we define ι[u, →] for the clockwise direction, and ι[v, ←], ι[v, →] for
the arc evi . There are L + 1 options for each of the indices ι[u, ←], ι[u, →], ι[v, ←], and ι[v, →].
We now show that the guessed information is sufficient to uniqely determine a shift of Q. Recall
that for every path Qi ∈ Q we already know its endpoints and a path Pi0 in G parallel to η(Qi );
without loss of generality, we can assume that Pi0 starts with eui and ends with evi . Observe that it
suffices to determine, for every parallel bunch in G, the order in which the projections of the paths
in Q traverse it.
We deduce this information in polynomial time by the following resolution procedure. From the
guessed information, we can deduce the following; for simplicity, we use “left” and “right” instead
of “counter-clockwise” and “clockwise”.
(endpoints rule) In the bunch of eui , the path Qi is to the right of Qι[u,←] , and similarly for
ι[u, →], ι[v, ←], and ι[v, →].
(diverge rule) Assume that for some indices a and b, Pa0 and Pb0 contain parallel edges e0a and e0b ,
respectively, but the preceding arcs on Pa0 and Pb0 are not parallel. Then from the order of
these preceding arcs in the cyclic order of arcs around the tail of e0a we can deduce the relative
order of η(Qa ) and η(Qb ) on the parallel bunch of e0a . This is because η(Qa ) and η(Qb ) do not
cross.
Second, we have the following straightforward deduction rules.
(parallel rule) If we know that Qa is to the left of Qb and Qb is to the left of Qc in some parallel
bunch, then Qa is to the left of Qc in the bunch in question.
(serial rule) If the projections of Qa and Qb have two-edge subpaths Ra and Rb that are parallel,
and we know the relative order of η(Qa ) and η(Qb ) on one of the bunches of the edges from
Ra and Rb , then, since η(Qa ) and η(Qb ) do not cross, we can deduce the order on the second
bunch of the edges of Ra and Rb .

31

We claim that after applying these deduction rules exhaustively (which can clearly be done in
polynomial time), we know the relative order of Qa and Qb for every Qa , Qb ∈ Q and every parallel
bunch of G their projections traverse jointly. Assume this is not true, and pick Qa , Qb , and a
parallel bunch traversed by η(Qa ) and η(Qb ) via arcs ea and eb , respectively, where we did not
deduce the relative order of ea and eb , with the following minimization criteria: the number of arcs
between ea and eb in their bunch that are in the projections of other paths of Q is minimized, and,
subject to that, the number of arcs on η(Qa ) before ea is minimized.
From the parallel rule we infer that actually no projection of a path of Q uses any arc between
ea and eb in their parallel bunch. From the endpoints rule we infer that ea and eb are not the first
arcs of η(Qa ) and η(Qb ), respectively. From the diverge rule we infer that the preceding arcs e0a and
e0b of ea and eb on η(Qa ) and η(Qb ) are parallel, too. From the minimality we infer that there is
another arc e0c in the parallel bunch between e0a and e0b that is part of η(Qc ) for some other path
Qc ∈ Q. Since the projections of paths of Q are noncrossing, η(Qc ) needs to end at the head of e0c ,
i.e., e0c is the last arc of η(Qc ). From the endpoints rule, we know both paths of Q that traverse the
bunch of e0c next to e0c . Since this applies to any arc e0c between e0a and e0b in their parallel bunch,
the parallel rule allows us to deduce the relative order of e0a and e0b in their bunch and, subsequently,
the serial rule would allow us to deduce the relative order of ea and eb . This contradiction finishes
the proof of the claim.
y
Enumeration algorithm. Armed with Claim 5.20, we can finish our enumeration procedure.
√
√
Claim 5.21. In time |T |O( |T |) nO(1) one can enumerate a family A of |T |O( |T |) tri-partitions of
the terminals such that for every edge f ∈ E(T ), A contains the tri-partition induced by γ(f ).
a branching algorithm that guesses
Proof. Consider a noose γ(f ) for some f ∈ E(T ). We present
√
O( |T |)
the tri-partition induced by γ(f ) by branching into |T |
subcases.
•
Let Qf be the family of those paths Q ∈ Ppsuch that uQ lies on γ(f ). We have L := |Qf | =
p
O( |T |). We guess the number L (one of O( |T |) options).
Then we invoke the algorithm of
√

Claim 5.20 for parameter L, giving us a family of √
size |T |O( |T |) that includes some shift of Qf . By
guessing one member of this family (one of |T |O( |T |) options), we may proceed assuming that we
have correctly guessed a family Q0f that is a shift of Qf .
f • and all paths
We construct a graph H10 defined as a subgraph of G• equal to the union of W
0
0
0
0
0
from Qf . Compute a graph H2 from H1 as follows: for every path Q ∈ Qf contract all the internal
vertices of Q0 into a single vertex u0Q0 , similarly as in the process of construction H × . Finally, we
apply Lemma 4.1 to H20 and parameter L, obtaining a family A0 of tri-partitions of the terminal
set. To conclude the proof of the claim, it suffices to show that, provided the
√ previous guesses are
O( |T |)
0
0
correct, A contains a tri-partition induced by γ(f ). Indeed, as |A | = |T |
, we may then just
guess one element of A0 and return it.
Let H1 and H2 be defined as H10 and H20 , but with the family Qf instead of Q0f . The crucial
observation is that since the paths in P • are vertex-disjoint except for endpoints, and Q0f is a shift of
Qf , then H1 and H10 become isomorphic after suppressing non-terminal vertices of degree 2. Moreover,
f • under the suppresion,
this isomorphism fixes the terminals as well as the image of the tree W
and the embedding of H1 may be transformed into an embedding of H10 by a homeomorphism of
the plane that moves paths of Qf to the corresponding shifts from Q0f . The existence of such an
isomorphism can be easily seen from the definition of a shift; recall here that paths of Q0f have
exactly the same endpoints as the corresponding paths from Qf . Now, the construction of H2 from
H1 is done by applying an isomorphic set of contractions as in the construction of H20 from H10 . It
32

follows that H2 after suppressing degree-2 nonterminal vertices is isomorphic to H20 after suppressing
degree-2 vertices, and again the embeddings of these two graphs can be transformed to each other
by means of a homeomorphism of the plane. Observe now that, by applying this homeomorphism
to the noose γ(f ) in H2 , we obtain a noose γ(f )0 in H20 that induces the same tri-partition of the
terminals as γ(f ). By Lemma 4.1, this tri-partition was included in the enumerated family A0 , so
the proof of the claim is finished.
y
To conclude the proof of Theorem 5.14, note p
that every tri-partition (T0 , {T1 , T2 }) induced by a
noose γ(f ) for some f ∈ E(T ) satisfies |T0 | = O( |T |). Thus, we can compute a family B of subsets
of terminals as follows:
we compute the family A using Claim 5.21 and, for every (T0 , {T1 , T2 }) ∈ A
p
with |T0 | = O( |T |), every j = 1, 2, and every T 0 with Tj ⊆ T 0 ⊆ T0 ∪ Tj , we insert T 0 into B.
Claim 5.21 ensures that the family B is of correct size, is computed within the promised running
time bound, and that it contains the sets β(s) for every s ∈ V (T ). Furthermore, by Claim 5.19,
(T − r, β) is a good decomposition of W and πW . This finishes the proof of Theorem 5.14.

5.3

Dynamic programming algorithm

In this section we show that, given the family B obtained
using Theorem 5.14, one can find a shortest
√
walk visiting all terminals in time |B|O(1) · |T |O( |T |) · nO(1) by a standard dynamic programming
approach. More formally, we show the following lemma.
Subset TSP instance (G, T ) and a family B of
Lemma 5.22. Given a preprocessed Directed
√
O( |T |)
O(1)
O(1)
subsets of T , one can in time |B|
· |T |
compute a T -short walk W0 of total length not
·n
greater than the minimum length of a T -short walk W for which there exists a good decomposition
(T , β) satisfying {β(s) : s ∈ V (T )} ⊆ B.
p
Proof. A state consists of a set A ∈ B and a family M of O(
√ |T |) ordered pairs of (not necessarily
different) terminals from A. Note that there are |B| · |T |O( |T |) states.
A realization of a state (A, M) is a mapping P that assigns to every pair (t, t0 ) ∈ M a walk
0
(t, t ) from t to t0 in G in such a manner that the walks {P (u, v) : (t, t0 ) ∈ M} together visit all
terminals of A. The weight of a realization is the sum of the weights of all walks in it. In our
dynamic programming algorithm we shall compute a realization P(A,M) for every state (A, M), in
the order of increasing size of A.
Given two walks Q1 and Q2 , a concatenation of Q1 and Q2 is a walk consisting of the walk Q1 ,
then a shortest path from the ending point of Q1 to the starting vertex of Q2 , and then the walk
Q2 . This definition naturally
√ generalizes to concatenations of longer sequences of walks.
For states with |A| ≤ C T , we compute a minimum weight realization by a standard dynamic
programming algorithm that builds walks P (u, v) by extending them by terminals one-by-one. More
precisely, the realization for a state (A, M) is chosen by taking any pair (t, t0 ) ∈ M with t 6= t0 , and
selecting the minimum-weight realization among the following candidates: for each a state of the
form (A \ {t0 }, M \ {(t, t0 )} ∪ {(t, t00 )}) for some t00 ∈ A \ {t0 }, take its precomputed realization P
and append a shortest path from t00 to t0 to P (t, t00 ). When t = t0 for all M, the minimum-weight
realization clearly consists of a one-vertex path for every pair from M, which has total weight 0.
For states (A, M) with larger sets A, we iterate over all partitions of the form A = A1 ] A2
with A1 , A2 ∈ B and |A1 |, |A2 | < |A|, and all states (A1 , M1 ) and (A2 , M2 ) with precomputed
realizations
P1 and P2 , respectively. With a standard dynamic programming algorithm, in time
√
O( |T |) O(1)
2
n
we find a minimum-weight realization P of (A, M) whose walks are concatenations of
the walks of P1 and P2 in such a manner that each walk of P1 and P2 is used exactly once. The state

33

of this dynamic programming algorithm keeps track of which walks of P1 and P2 were already used.
We build walks of P one-by-one, by concatenating a walk of P1 or P2 one at a time, maintaining
the current endpoint of the so-far constructed walk.
Finally, we iterate over all states (T, {(t, t0 )}) for terminals t, t0 ∈ T and set πt,t0 to be the order
in which P(T,{(t,t0 )}) (t, t0 ) traverses the terminals. For each such choice, compute a T -short walk
Wt,t0 with the witnessing permutation πt,t0 , and return the minimum-weight walk found.
Clearly, the algorithm returns a T -short walk. Consider a T -short walk W for which there exists
a witnessing permutation πW and a good decomposition (T , β) such that {β(v) : v ∈ V (T )} ⊆ B.
From the definition
of a good decomposition, for every node s ∈ V (T ) there exists a collection Ps of
p
at most C |T | subwalks of W that visit exactly the terminals of β(s). Furthermore, we can choose
these collections in such a manner that every subwalk starts and ends at a terminal, for the root r
the collection Pr consists of a single subwalk of W from the first to the last terminal of πW , and for
every node s with children s1 and s2 , the walks of Ps are concatenations of some walks of Ps1 and
Ps2 , where every walk in Ps1 and Ps2 is used exactly once. Then a standard inductive argument
shows that the realization for (β(s), Ms ) is of weight at most the total weight of the walks in Ps .
Consequently, if t, t0 are the first and the last terminal on πW , then the computed realization of
(T, {(t, t0 )}) is of weight at most the weight of the subwalk of W from t to t0 . Hence the T -short
walk computed for πt,t0 is of weight not larger than the weight of W , which concludes the proof.

5.4

Wrap up

We conclude the proof of Theorem 1.1. As discussed in Section 3, without loss of generality we
assume that the input graph G has unique shortest paths, that every terminal t has a unique
neighbor wt connected via arcs (wt , t) and (t, wt ), and that every arc not incident to a terminal is
copied |T | times.
Observe that the walk W we are looking for is always a T -short walk. Lemmas 5.2 and 5.5 imply
that we can assume that the walk W we are looking for is not only T -short, but also first-cross
reduced and visits every edge at most once.
√
We invoke the algorithm Theorem 5.14, yielding a family B of size |T |O( |T |) . By the properties
of the sought walk W , there exists a good decomposition (T , β) of W and its witnessing permutation
πW such that β(s) ∈ B for every s ∈ V (T ). Consequently, the algorithm of Lemma 5.22, applied to
B, finds a walk of total length not longer than W . By the optimality of W , the resulting walk is a
shortest closed walk visiting T . This concludes the proof of Theorem 1.1.

6

Dynamic programming algorithm for the Steiner tree problem

This section is devoted to the proof of Theorem 1.3. On high level, we follow the approach of Fomin
et al. [20] used for designing a subexponential algorithm for the rectilinear Steiner Tree problem,
and we adjust the technique from there to the more general graph setting. More precisely, we argue
that the union of some optimum solution and a local-search optimum has low treewidth, which
yields a small family of states for a dynamic programming procedure assembling the optimum.
Let G be an edge-weighted undirected planar graph, and let T ⊆ V (G) be a set of terminals.
Without loss of generality we can assume that G is connected (by deleting connected components
that do not contain terminals) and that every weight of G is positive (by contracting edges of weight
0). A solution is a subset of edges of G that induces a tree containing all terminals. Given a solution
A, a vertex v ∈ V (A) is special if it is a terminal or it has degree at least 3 in A. An inner path in
a solution A is a path in the tree A that does not contain any special vertex as an inner vertex.

34

An `-local search step from a solution A is defined as follows: we delete at most ` inner paths in
the tree A and reconnect the remaining connected components in a minimum-cost way. A solution
A is an `-local search optimum if there is no `-local search step that leads to a solution of strictly
smaller cost.
Our main combinatorial engine of the proof is the following statement.
Theorem 6.1. Let G be an edge-weighted undirected planar graph with positive weights and let
T ⊆ V (G) be a set of terminals. Furthermore, let A be a 2-local search optimum and let A? be a
minimum-weight solution thatp
additionally minimizes the number of edges of A? \ A. Then, the
graph A ∪ A? has treewidth O( |T |).
We prove Theorem 6.1 in Section 6.1 and then, in Section 6.2, we conclude the proof of
Theorem 1.3 by a relatively standard dynamic programming routine.

6.1

Treewidth bound

We now prove Theorem 6.1. Let H0 be the graph induced by the edges of A ∪ A? , and let H be a
minor of H0 constructed by suppressing all non-terminal vertices of degree two. That is, we replace
every maximal path of H0 containing only non-terminal vertices of degree two as inner vertices by a
single edge in H.
Note that H is a planar graph.
p To prove Theorem 6.1, it suffices to show that H has O(|T |)
vertices, as that would imply a O( |T |) bound on the treewidth of H and, consequently, the same
bound for the treewidth of H0 .
Since A is a 2-local search optimum, it is in particular an inclusion-wise minimal solution (a
single edge is always an inner path and edge weights are positive). Similarly, A? is an inclusion-wise
minimal solution. Consequently, if v is a non-terminal vertex of H0 of degree at most 2, then v
has degree exactly 2 in H0 and both its incident edges belong either both to A or none to A, and
belong both to A? or none to A? . This observation allows us to project the sets A and A? onto sets
AH , A?H ⊆ E(H) in the following manner. We start with AH = A ∩ E(H) and A?H = A? ∩ E(H).
Furthermore, when, in the process of constructing H from H0 , we replace a maximal path P in H0
with an edge eP ∈ E(H), the edge set of P is either fully contained in A or disjoint with A, and
similarly for A? . We put eP ∈ AH if E(P ) ⊆ A and we put eP ∈ A?H if E(P ) ⊆ A? .
We now define important vertices in H. A vertex v ∈ H is important if either v is a special
vertex of A or A? (recall that V (H) ⊆ V (H0 )). Let S be the set of important vertices. The fact
that both A and A? are trees with all leaves in T ensures that there are not that many important
vertices and not that many bridges in H.
Lemma 6.2. There are less than 3|T | important vertices and less than 2|T | bridges in H. Furthermore,
X
degH (v) < 14|T |.
v∈S

Proof. By inclusion-wise minimality, every leaf of both A and A? is a terminal. This implies that
both A and A? have less than |T | vertices of degree at least 3 each (in particular, less than 2|T |
special vertices each), giving the 3|T | bound on the number of important vertices. Furthermore, it
also implies that
X
max(0, degA (v) − 2) < |T |,
v∈V (A)

X
v∈V

max(0, degA? (v) − 2) < |T |.

(A? )

35

With the above, the second claim of the lemma follows, as
X
X
degH (v) ≤
(degA (v) + degA? (v))
v∈S

v∈S

≤ 4|S| +

X

max(0, degA (v) − 2) +

X
v∈V

v∈V (A)

max(0, degA? (v) − 2)

(A? )

< 12|T | + |T | + |T | = 14|T |.
For the bound on the number of bridges, let B be the set of bridges in H, and let C be a connected
component of H − B. We claim that C contains a special vertex of A; since A has less than 2|T |
special vertices, this would prove the bound |B| < 2|T |. Assume the contrary. By the minimality of
A and A? , we have B ⊆ AH ∩ A?H . Consequently, since C does not contain a vertex of degree at
least 3 in A (as such vertices are special in A), we have that C is incident to at most 2 bridges of B.
Since C does not contain a terminal and A is inclusion-wise minimal, C is incident to exactly two
bridges in B, say e1 and e2 with endpoints v1 , v2 ∈ V (C), respectively. Then the optimality of A
and A? asserts that both A and A? contain a minimum-weight path from v1 to v2 . However, the
condition that A? minimizes the number of edges of A? \ A implies that A and A? use the same
path from v1 to v2 and, consequently, C is a path. This is a contradiction, as then in the process of
constructing H we would contract C, e1 , and e2 onto a single edge. This finishes the proof of the
lemma.
We now make a crucial observation that faces of H either are incident to an important vertex or
are long in a specific sense.
Lemma 6.3. Every face of H is either incident to an important vertex, to a bridge of H, or to at
least six edges of the symmetric difference AH 4A?H .
Proof. Assume the contrary. Let f be a face that is not incident to any important vertex nor bridge
of H and is incident to at most 5 edges from AH 4A?H . Since H is connected, f is homeomorphic to
an open disc. Let W be the closed walk around H. Since f is not incident to a bridge of H, every
edge of H appears in W at most once. This in particular implies that, as A and A? are trees, we
have E(W ) 6⊆ AH and E(W ) 6⊆ A?H , that is, there exists an edge of AH \ A?H and of A?H \ AH on
the walk W .
We now greedily partition the walk W into walks W1 , W2 , . . . , W` as follows. We start with an
edge e1 ∈ E(W ) \ A?H ⊆ AH \ A?H and take W1 to be the maximal subwalk of W containing e1
and contained in AH . As E(W ) \ AH is nonempty, W1 is a proper subwalk of W , and on both its
endpoints is incident to an edge of E(W ) \ AH ⊆ A?H \ AH . We pick e2 to be one of these edges,
and define W2 to be a maximal subwalk of W − W1 that contains e2 and is contained in A?H . The
walk W2 has one endpoint at the endpoint of W1 , and the second endpoint either at the second
endpoint of W2 or at some edge e3 ∈ E(W ) \ A?H . We continue defining edges ei and walks Wi
in this manner such that ei ∈ Wi , for odd indices i we have ei ∈ E(W ) \ A?H and E(Wi ) ⊆ AH
while for even indices i we have ei ∈ E(W ) \ AH and E(Wi ) ⊆ A?H . The process ends when we
S
hit the second endpoint of W1 , and then E(W ) = `i=1 E(Wi ). Furthermore, by the maximality of
W1 , both edges of W incident to the endpoints of W1 but not on W1 belong to E(W ) \ A?H and,
consequently, the number of steps ` is even.
Recall that f is not incident to an important vertex of H, consequently, every walk Wi corresponds
to an inner path Pi in A for i odd and in A? for i even; in particular, every Wi is in fact a simple
path in H.

36

v2

P3

P2

P1

v3 = v4

v2

P4

P2

v1

v1

P3

v3

P4

P1

v4

Figure 7: The replacement argument used in the proof of Lemma 6.3 for ` = 4. The solution A is
green and the solution A? is red. The left picture shows the first subcase, when there is a corner
vertex that is not close; note that the connections may be a bit different (e.g., v1 = v4 ), but the
replacement stays the same. The right picture shows the second subcase, when every corner vertex
is close in one of the trees.
Since every walk Wi contains a distinct edge of AH 4A?H , we have ` ≤ 5. As ` is even, we have
` = 2 or ` = 4. We will reach a contradiction in both cases.
Assume first ` = 2, that is, P1 and P2 are two paths in G with the same endpoints. Then,
by the fact that no vertex on W is important and A is a 2-local search optimum, we have that
ω(P1 ) ≤ ω(P2 ). However, then (A? \ E(P2 )) ∪ E(P1 ) is a solution of weight at most the weight of
A? , while having a smaller number of edges not belonging to A due to the edge e2 ∈ A?H \ AH on
W2 . This is the desired contradiction.
Consider now the more involved case ` = 4. Since both P1 and P3 are inner paths in a tree A
and are edge-disjoint, we define the close endpoint v1 of P1 to be the endpoint of P1 that is closer
to P3 in the tree A. Symmetrically, define the close endpoint v3 of P3 to be the endpoint closer to
P1 in A. We similarly define the close endpoints v2 and v4 on P2 and P4 with respect to the tree
A? . We now distinguish two subcases, depending on whether there exists an endpoint v of one of
the paths Pi that is not close for the incident two paths.
For the first case, by symmetry assume that the common endpoint of P1 and P2 , denoted v, is
different than v1 and v2 (see the left panel on Figure 7). Then we observe that (A \ E(P1 )) ∪ E(P2 )
is a solution and, by the local search optimality of A, we have ω(P1 ) ≤ ω(P2 ). However, we have
then that (A? \ E(P2 )) ∪ E(P1 ) is a solution of weight not larger than the weight of A? that has
strictly less edges outside A due to the existence of the edge e2 ∈ A?H \ AH on W2 .
For the second case, observe that there are two options: either vi is the common endpoint
of Pi and Pi+1 for i = 1, 2, 3, 4 (with P5 = P1 ) or vi is the common endpoint of Pi and Pi−1 for
i = 1, 2, 3, 4 (with P0 = P4 ). The arguments are symmetric, so let us assume the first alternative.
The key observation now is that the following are solutions (see the right panel on Figure 7):
Ā := (A \ (E(P1 ) ∪ E(P3 ))) ∪ E(P2 ) ∪ E(P4 ),
Ā? := (A? \ (E(P2 ) ∪ E(P4 ))) ∪ E(P1 ) ∪ E(P3 ).
Consequently, the 2-local search optimality of A implies that ω(P1 ) + ω(P3 ) ≤ ω(P2 ) + ω(P4 ),
yielding ω(Ā? ) ≤ ω(A? ). However, Ā? has strictly less edges outside A than A? due to the edges e2
and e4 , giving the desired contradiction.
Since we have reached a contradiction in all subcases, the lemma is proven.
Armed with the above two lemmas, we now conclude the proof of Theorem 6.1 by a discharging
argument.
37

We set up the initial charge in two steps. First, every vertex and every face receives a charge
of −6, while every edge receives a charge of +6. Second, every important vertex v receives an
additional charge of +6 degH (v) + 7 and every bridge of H receives an additional charge of +6. By
Euler’s formula, the total charge assigned in the first step is negative, while Lemma 6.2 implies that
the second step assigns a total charge of less than
6 · 14|T | + 7 · 3|T | + 6 · 2|T | = 117|T |.
Consequently, the total charge in the graph is less than 117|T |.
Let us now proceed with the discharging rules.
• Every important vertex v sends a charge of 6 to every incident face.
• Every edge e ∈ E(H) that belongs to both AH and A?H sends a charge of +3 to each of the
two incident vertices.
• Every edge e ∈ E(H) that belongs to AH 4A?H sends a charge of +2 to each of the two incident
vertices and a charge of +1 to each of the two incident faces (they are distinct, as an edge of
AH 4A?H cannot be a bridge of H).
• Every bridge e ∈ E(H) sends the additional charge of +6 to the unique incident face.
Clearly, at the end of the process every edge has charge zero.
We claim that every face f has a nonnegative charge; recall that initially it received a charge
of −6. If f is incident to an important vertex or a bridge of H, it received a charge of +6 from it.
Otherwise, Lemma 6.3 implies that f is incident to at least 6 edges from AH 4A?H , and receives a
charge of +1 from each such edge.
Finally, we claim that every vertex v has a strictly positive charge; recall that initially it received
also a charge of −6. If v is important, then it received an additional charge of 6 degH (v) + 7 and
sent 6 degH (v) to the incident faces, leaving a charge of −6 + 7 = +1.
Hence, we are left with the case when v is not important. Then v received a charge of +2 or +3
from each of its incident edges. Since v is not important, in particular it is not a terminal, and it is
of degree at least 3 in H by the construction of H. If v is of degree at least 4, then the incident
edges send a charge of at least +8, and the final charge is at least −6 + 8 = +2. Otherwise, when
degH (v) = 3, observe that exactly two edges incident to v belong to AH and exactly two edges
incident to v belong to A?H . This implies that v is incident to an edge of H that belongs both to
AH and A?H , and such an edge sends a charge of +3. Consequently, v receives a charge of at least
+3 + 2 + 2 = +7, and the final charge is at least −6 + 7 = +1.
To sum up, we have distributed an initial charge of less than 117|T | in such a manner that every
edge has zero charge, every face has a nonnegative charge, and every vertex has a charge of at least
+1. This implies that H has less than 117|T | vertices, finishing the proof of Theorem 6.1.

6.2

Dynamic programming

We now present the algorithm promised by Theorem 1.3. We use the principle of the dynamic
programming based on the combinatorial result of Theorem 6.1.
Let A be a 2-local search optimum that can be computed in time W · nO(1) where W is the
maximum edge weight. Let A? be a minimum-weight solution that minimizes the number of edges
of A? \ A and let H0 = A ∪ A? . Fix a spherical embedding of G; this naturally induces a spherical
embedding of H0 aspwell. By Theorems 6.1 and 3.2, there exists an sc-branch decomposition (T , ζ, γ)
of H0 of width O( |T |).
38

With every edge e ∈ E(T ) and its noose γ(e), we associate a tuple (T0 , {T1 , T2 }), called henceforth
a partition of the terminals, where T0 is the set of terminals lying on γ(e), and {T1 , T2 } are the
sets of terminals contained in the two parts of the sphere minus γ(e). Since we consider spherical
embeddings in this section, {T1 , T2 } is an unordered pair.
As discussed in Section 4, given A, one can enumerate a relatively small family of candidates for
partitions.
√
√
Claim 6.4. One can in time |T |O( |T |) nO(1) enumerate a family A of |T |O( |T |) subsets of T such
that for every e ∈ E(T ), if (T0 , {T1 , T2 }) is the partition corresponding to e, then T0 ∪ T1 and T0 ∪ T2
belong to A.
p
Proof. We apply Lemma 4.1 to the graph A, the terminal set T , and a bound ` = O( |T |).
y
With the family A given by Claim 6.4, we now describe
p our dynamic programming algorithm. A
state is a triple (S, I, R), where S ∈ √
A, I is a set of O( |T |) vertices of G, and R is an equivalence
√

relation on I. Clearly, there are nO( |T |) states and they can be enumerated within time nO( |T |) .
For every state (S, I, R), we say that a subgraph B is feasible for (S, I, R) if the following holds:
S ⊆ V (B), every connected component of B contains at least one vertex of I, and two vertices
u, v ∈ I that are in relation R belong to the same connected component of R. For every state
(S, I, R), the algorithm will compute along the way a number of feasible subgraphs and choose as
the value B(S, I, R) the one of minimum
pweight.
For a state (S, I, R) with |S| = O( |T |), we can compute B(S, I, R) to be the subgraph of
minimum weight among all feasible subgraphs by the following direct argument. We iterate over
all functions σ : S → I and compute a minimum-weight Steiner forest that connects t to σ(t)
√ for
O( |T |)
every t ∈ S and that connects every u, v ∈ I that are in relation R. Since there are |T | p
functions σ and, for each σ the question can be phrased as a Steiner
forest instance with O( |T |)
√
connection requests, all computations can be done in time nO( |T |) by a standard Dreyfus-Wagner
dynamic programming algorithm. Furthermore, note that if B is the sought feasible subgraph of
minimum weight, then for the case when σ assigns to every t ∈ S a fixed representative σ(t) ∈ I of
the connected component of B that contains t, then the found Steiner forest is a feasible
p solution of
weight at most ω(B). This finishes the description of the computations for |S| = O( |T |).
For states (S, I, R) with larger sets S, we proceed as follows. We make |E(T )| = O(n) rounds,
in each round computing a number of feasible subgraphs for every state (S, I, R), and at every
round choosing as B(S, I, R) the minimum-weight feasible subgraph among all found subgraphs and
the subgraph B(S, I, R) from the previous round. The number of rounds is chosen so that it is not
larger than the number of edges of T , which is O(n). In every round, for every state (S, I, R), we
iterate over all pairs of states (S1 , I1 , R1 ) and (S2 , I2 , R2 ) and take B(S1 , I1 , R1 ) ∪ B(S2√
, I2 , R2 ) as
O( |T |)
a candidate if it is a feasible subgraph for (S, I, R). Clearly, the computations take n
time.
After the computation, we will iterate over all states (T, I, I × I) (i.e., with only one equivalence
class in R) and choose the minimum-weight subgraph B(T, I, I × I) found. Since a feasible subgraph
for a state (S, I, I × I) needs to be connected, the algorithm returns a connected subgraph spanning
T . We have already argued about the running time bound.
To show the optimality of the returned solution, we show the following claim.

Claim 6.5. Let e ∈ E(T ), let (T0 , {T1 , T2 }) be the partition corresponding to the noose γ(e), and
let Ti for i = 1, 2 be the connected component of T − e that corresponds to the set Ti of terminals.
Furthermore, let A?i be the subgraph of A? with edges corresponding to the leaves of Ti (i.e., lying on
the same side of γ(e) as Ti ), let I be the set of vertices of V (A? ) that lie on γ(e), and let Ri be the
equivalence relation of lying in the same connected component of A? .
39

Then, for i = 1, 2, the subgraph A?i is a feasible subgraph for the state (T0 ∪Ti , I, Ri ). Furthermore,
after |E(Ti )| rounds of the algorithm, the weight of B(T0 ∪ Ti , I, Ri ) is at most ω(A?i ).
Proof. The fact that A?i is a feasible subgraph for (T0 ∪ Ti , I, Ri ) follows directly from the definitions.
For the second claim, we perform induction on the number of edges of Ti . For the base case, that is,
Ti being a single vertex, we have that γ(e) encloses a single edge of H0 , and hence |T0 ∪ Ti |, |I| ≤ 2.
This is covered by the base case of the computation, where B(T0 ∪ Ti , I, Ri ) is a minimum-weight
feasible subgraph before the first round of the computations.
For the inductive case, let wi be the endpoint of e in Ti and let e1 and e2 be the two other edges
of T incident with wi . Furthermore, for j = 1, 2, let T j be the connected component of T − ej that
does not contain wi , let A?,j be the subgraph of A? consisting of the edges corresponding to the
leaves of T j , let I j be the set of vertices of A? that lie on γ(I j ), let Rj be the equivalence relation
on I j of lying in the same connected component of A?,j , and let S j be the set of terminals that lie
on γ(I j ) or on the same side as the edges corresponding to the leaves of T j .
Observe that the edge set A?i is a disjoint union of A?,1 and A?,2 . By the induction hypothesis,
after round |E(T j )| the subgraph B(S j , I j , Rj ) has weight at most ω(A?,j ) for j = 1, 2. A direct
check from the definition shows that B(S 1 , I 1 , R1 )∪B(S 2 , I 2 , R2 ) is feasible for B(T0 ∪Ti , I, Ri ) (this
is easy to see from the fact that all three considered states were defined from the behavior of A? , and
A?i is a disjoint union of A?,1 and A?,2 ). Consequently, since |E(Ti )| > |E(T j )| for j = 1, 2, we have
that after round |E(T j )| the subgraph B(Si , I, Ri ) has weight at most ω(A?,1 ) + ω(A?,2 ) = ω(A?i ),
finishing the proof of the claim.
y
We conclude the proof of the correctness of the algorithm, and the whole proof of Theorem 1.3
as follows. Observe that we may assume that there is an edge e0 of the graph that is not in A?
but is incident with a vertex in A? , for otherwise the whole connected component containing all
the terminals must consist only of a minimal tree spanning them. This edge e0 corresponds to leaf
w ∈ V (T ); that is, e0 = ζ(w). Let e be the edge of T incident with w and let T1 and T2 be the
connected components of T − e0 such that {w} = V (T2 ) and T1 = T − w. Note that the set I of
vertices of V (A? ) that lie on γ(e) is nonempty and has at most 2 elements, by the choice of e0 .
Let (T0 , {T1 , T2 }) be the partition corresponding to the noose γ(e). Note that T2 = ∅, as γ(e)
separates ζ(w) from the rest of H0 . Furthermore, as ζ(w) ∈
/ A? , we have A?1 = A? , and A?1 is a
feasible subgraph for the state (T, I, I × I). By Claim 6.5, after |E(T )| = O(n) rounds, the subgraph
B(T, I, I × I) is of weight at most ω(A?1 ) = ω(A? ), and thus of minimum possible weight. This
finishes the proof of Theorem 1.3.

7

A lower bound for the Steiner tree problem

In this section we present the proof of Theorem 1.2. More precisely, we prove the following stronger
technical result.
Theorem 7.1. Suppose ETH holds. Then for every γ > 0 there exists a positive real dγ > 0 with
limγ→0 dγ = ∞ such that there is no algorithm solving Planar Steiner Tree with unit weights
in time O(2γ|T | · |V (G)|dγ ) for an input instance (G, T ).
Note that in the statement of Theorem 1.2, for large γ we may set dγ < 1, which just trivially
excludes sublinear algorithms. The statement becomes meaningful when γ approaches 0, as then it
asserts that the degree of the polynomial factor necessarily needs to grow to infinity, assuming ETH.
Observe that Theorem 7.1 in particular implies that there is no algorithm solving Planar
Steiner Tree in time O(2o(|T |) · |V (G)|c ) for any constant c, which is the statement of Theorem 1.2,
40

but it does not exclude tradeoffs between the base of the exponent 2γ and the degree of the
polynomial factor. Similar tradeoffs for the size parameterization were described by Tazari [42],
so it is conceivable that they might exist also in the case of the stronger parameterization by the
number of terminals.
For the proof of Theorem 7.1 we will need the following abstraction for ETH that can be derived
from the Sparsification Lemma [26]. See also [12] for a broader discussion.
Theorem 7.2 (Theorem 14.4 of [12]). Unless ETH fails, there is a constant δ > 0 such that there is
no algorithm solving 3SAT in time 2δ(n+m) · (n + m)O(1) , where n, m respectively denote the number
of variables and clauses of the input formula.
Theorem 7.1 will be proved by a reduction from Theorem 7.2, encapsulated in the following lemma.
Lemma 7.3. For every ε > 0 there is an algorithm that given an instance ϕ of 3SAT, say with
n variables and m clauses, constructs an instance (G, T ) of the Steiner Tree problem with unit
weights and an integer budget k, such that
• G is planar and has O(2ε(n+m) · (n + m)c ) vertices for some universal constant c;
• |T | ≤ Cε−1 (n + m) for some universal constant C; and
• ϕ is satisfiable if and only if (G, T ) admits a Steiner tree of total weight at most k.
Moreover, the algorithm runs in time linear in the size of the output instance.
Before we proceed to the proof of Lemma 7.3, we first verify that Theorem 7.1 indeed follows by
combining Theorem 7.2 with Lemma 7.3.
Proof of Theorem 7.1 assuming Lemma 7.3. Let δ > 0 be such that there is no algorithm for 3SAT
with running time 2δ(n+m) · (n + m)O(1) ; such δ exists by Theorem 7.2. We prove that for every γ > 0
there is no algorithm solving Planar Steiner Tree with unit weights in time O(2γ|T | · |V (G)|dγ )
for dγ = δ 2 /(4γC), where C is the constant from Lemma 7.3. Note that lim supγ→0 dγ = ∞.
For the sake of contradiction assume otherwise: there is γ > 0 and an algorithm as above
with running time O(2γ|T | · |V (G)|dγ ) for dγ = δ 2 /(4γC). Consider the following algorithm for
solving 3SAT. Given the input formula ϕ, first construct the instance (G, T ) of Planar Steiner
Tree together with budget k using the reduction of Lemma 7.3 for ε = (2γC)/δ. Then apply the
hypothetical algorithm for Planar Steiner Tree to verify whether (G, T ) admits a Steiner tree
of total weight at most k, thereby deciding whether ϕ is satisfiable. Observe that supposing n, m
denote the number of variables and clauses of ϕ, this algorithm works in time




d 
γ|T |
dγ
γCε−1 (n+m)
ε(n+m)
c γ
O 2
· |V (G)|
= O 2
· 2
· (n + m)


= O 2δ/2·(n+m) · 2δ/2·(n+m) · (n + m)c·dγ = 2δ(n+m) · (n + m)O(1) .
This is a contradiction with the choice of δ.
We are left with proving Lemma 7.3. In the reduction we use edges with positive integral weights.
Such a weighted edge can be emulated by replacing it with a path of length equal to the weight,
consisting of unit-weight edges. At the end of the construction we argue that this replacement does
not blow up the size of the graph too much, so that we achieve the promised bounds.
We first give some auxiliary gadget constructions.
41

7.1

Gadgets

For our gadgets we will use seven magnitudes of weights of edges: M1 , . . . , M7 , defined as Mt = M t−1
for some large integer M > 1, to be defined later. The value of M will be chosen so that it is linear
in the total output size. This implies that all weights of edges are bounded by a degree-6 polynomial
of the total output size, which will be useful for limiting the instance blow-up when reducing to the
unit-weight setting.
Connector gadgets. The first construction is a simple connector gadget that passes information
without creating a connection in the intended solution. A connector gadget CG consists of 12
vertices, out of which 4 are terminals: there are
• four interface vertices xNW , xNE , xSE , xSW ,
• four terminals tN , tE , tS , tW , and
• four normal vertices uNW , uNE , uSE , uSW .
Moreover, we connect uNW with xNW , tN , and tW using edges of the same weight, and similarly for
the other three corners; see Figure 8 for a reference.
In the construction to follow, connector gadgets will be combined with other gadgets by identifying
the interface vertices with some other vertices. Thus, the only vertices from a connector gadget that
may have some edges going outside of this gadget are the interface vertices. The following simple
claim explains the optimum behavior in the connector gadget. Its proof follows by a straightforward
case study, so we leave it to the reader.
Lemma 7.4. Suppose that H is a subgraph of the connector gadget CG such that in H each terminal
is connected to some interface vertex. Then H has at least 6 edges. Moreover, if H has exactly 6
edges, then H either consists of all edges incident to uNW and to uSE , or of all edges incident to
uNE and to uSW .
In particular, Lemma 7.4 shows that any such optimum connection within a connector gadget
does not connect any of the northern interfaces xNW and xNE with any of the southern interfaces
xSW and xSE . In future constructions, we will use connector gadgets where the weight of each edge
is M7 (the largest magnitude). Note that then Lemma 7.4 asserts that the minimum weight of a
subgraph connecting each terminal to any interface is 6M7 , and the only such subgraphs having
this weight are as described in the lemma statement.
xNE

xNW
N

t
uNW

uNE

tW

tE
uSE

uSW
tS

xSE

xSW

Figure 8: Connector gadget CG. Terminals are depicted by yellow squares.

42

Verification gadgets. In a nutshell, our reduction will pass information about the chosen variable
assignment via multiple long west-east paths, arranged one above the other. Whether each clause is
satisfied will be checked by a column of verification gadgets, where the consistency between them
will be verified by connecting them using connector gadgets along each column. See Figure 11 to
support this intuition. While this whole grid of verification gadgets is not defined yet, we now
describe one verification gadget and its functionality.
The verification gadget of order N , denoted VGN , is constructed as follows; see Figure 9 for
reference. First, take an N × N grid composed of vertices v[i, j] for i, j ∈ [N ], where there is an
edge between v[i, j] and v[i0 , j 0 ] iff |i − i0 | + |j − j 0 | = 1. Place this grid in the plane so that vertices
v[1, ·] form the west side, vertices v[·, 1] form the north side, vertices v[N, ·] form the east side, and
vertices v[·, N ] form the south side. Remove all vertical edges in the upper-right triangle; that is,
remove the edge between v[i, j] and v[i, j − 1] whenever i ≥ j. Next, add one vertex w connected to
all vertices from the south side. Finally, for each i ∈ [N ], add vertices y[i] and z[i], and connect y[i]
with v[1, i] and z[i] with v[N, i]. The vertices w, y[i], z[i] will be called the interface vertices of the
verification gadget VGN , and similarly as in the case of the connector gadgets, verification gadgets
will be connected to the rest of the construction by identifying interfaces with some vertices from
the outside of the gadget.
v[1, 1]

v[N, 1]
z[1]

y[1]

iM3

iM2

z[i]

y[i]

M3

M4

v[1, N ]

z[N ]

iM 2
M5 −

y[N ]

v[N, N ]

w

Figure 9: Verification gadget of order N , VGN . An intended solution connecting y[i], z[i], and w is
highlighted in blue.
This defines the shape of the verification gadget, we now assign weights to the edges. From now
on we assume that 10N < M for all considered verification gadgets, as this will be the case for the
final choice of M .
• Horizontal (i.e. west-east) edges in the grid have weight M4 each.

43

• Vertical (i.e. north-south) edges in the grid have weight M3 each.
• For each i ∈ [N ], the edge between y[i] and v[1, i] has weight iM2 .
• For each i ∈ [N ], the edge between z[i] and v[N, i] has weight iM3 .
• For each i ∈ [N ], the edge between w and v[i, N ] has weight M5 − iM2 .
This concludes the construction of the verification gadget. The intuition is that in the intended
solution to the constructed instance, inside each verification gadget we will need to connect three
interfaces: one among interfaces y[i] for i ∈ [N ], one among interfaces z[j] for j ∈ [N ], and the
interface w. The following lemmas describe the behavior of the gadget.
Lemma 7.5. For each i ∈ [N ], the verification gadget VGN contains a tree of total weight M5 +
(N − 1)M4 + (N − 1)M3 that connects y[i], z[i], and w.
Proof. Take the union of paths (y[i], v[1, i], . . . , v[N, i], z[i]) and (v[i, i], . . . , v[i, N ], w). It is easy to
verify that its weight is exactly M5 + (N − 1)M4 + (N − 1)M3 .
Lemma 7.6. Suppose that H is a subgraph of the verification gadget VGN such that H is a
(connected) tree and contains w, y[i] for some i ∈ [N ], and z[j] for some j ∈ [N ]. Then the total
weight of the edges of H is at least M5 + (N − 1)M4 + (N − 1)M3 . Furthermore, if this total weight
is equal to M5 + (N − 1)M4 + (N − 1)M3 , then i = j and H contains the edge between w and v[i, N ].
Proof. Suppose H is such a subtree, and suppose the total weight of H is at most M5 + (N −
1)M4 + (N − 1)M3 . First, observe that M5 + (N − 1)M4 + (N − 1)M3 < 32 M5 , but every edge of
VGN incident to w has weight at least 34 M5 . Therefore, H contains at most one edge incident to w.
As H has to connect w with y[i] and z[j], it follows that H contains exactly one edge incident to w,
say wv[k, N ] for some k ∈ [N ]. This edge has weight M5 − kM2 , which means that the other edges
of H have weight at most (N − 1)M4 + (N − 1)M3 + kM2 < (N − 1)M4 + (N − 1)M3 + 14 M3 .
Since H connects y[i] with z[j], and H has only one edge incident to w, it follows that H contains
the edges y[i]v[1, i] and v[N, j]z[j], which have weights iM2 and jM3 respectively, as well as at least
one edge between any pair of consecutive columns of the grid. The abovementioned edges have
weight (N − 1)M4 + iM2 + jM3 in total. Since (N − 1)M3 + 14 M3 < 12 M4 , we infer that H cannot
contain any more edges of weight M4 , that is, horizontal edges of the grid. We infer that H has
exactly one edge between each pair of consecutive columns of the grid.
Since in the upper-right triangle there are no vertical edges, it follows that H has to contain the
whole path (v[j, j], v[j + 1, j], . . . , v[N, j]). Moreover, since H connects w with y[i] and z[j], and
wv[k, N ] is the only edge of H incident to w, H actually connects v[k, N ] with y[i] and z[j]. Observe
that, again due to the lack of vertical edges in the upper right triangle, if we had that k > j, then
at least one additional horizontal edge of the grid would need to be used to connect v[k, N ] with
v[j, j], between two columns of the grid where one edge on the path (v[j, j], v[j + 1, j], . . . , v[N, j])
was already picked. This would be a contradiction with the constraint on the total weight of H, so
we infer that k ≤ j.
Now, in order to connect v[k, N ] with y[i] and z[j] we need to use at least (N − 1) − min(i, j)
vertical edges of the grid, each of which has weight M3 . So in total, we see that the weight of H has
to be at least
[(N − 1)M4 + iM2 + jM3 ] + ((N − 1) − min(i, j)) · M3 + M5 − kM2 ,

44

where the consecutive terms come from horizontal edges, vertical edges, and the edge wv[k, N ].
After refactoring this is equal to
M5 + (N − 1) · M4 + (N − 1) · M3 + (j − min(i, j))M3 + (i − k)M2 .
If we had j > i, then j − min(i, j) > 0, and since M3 > 10N · M2 , the whole sum would be strictly
larger than M5 + (N − 1)M4 + (N − 1)M3 . Hence j ≤ i and j − min(i, j) = 0. On the other
hand, we have that k ≤ j, hence in fact k ≤ j ≤ i. So in order to have the total weight at most
M5 + (N − 1)M4 + (N − 1)M3 , we need to have k = j = i. We infer that no tree connecting y[i],
z[j], and w can have weight smaller than M5 + (N − 1)M4 + (N − 1)M3 , and for any tree of exactly
this weight we need to have i = j and the edge wv[i, N ] included in the tree.
Suppose we have an arbitrary subset S ⊆ [N ]. We define the S-restriction of the verification
gadget VGN as follows: take VGN and remove all edges between w and v[i, N ] for i ∈
/ S. From
Lemmas 7.5 and 7.6 it follows that the set of subtrees of VGN connecting y[i] for some i ∈ [N ], z[j]
for some j ∈ [N ], and w contains no trees of weight less than M5 +(N −1)M4 +(N −1)M3 . Moreover,
when VGN is restricted by S ⊆ [N ], such a tree of weight exactly M5 + (N − 1)M4 + (N − 1)M3
exists if and only if i = j and i ∈ S.
Paired verification gadgets. We will use verification gadgets in pairs, called paired verification
gadgets. Such a paired verification gadget of order N , denoted PVGN , consists of two verification
gadgets VG1N and VG2N of order N ; see Figure 10 for reference. We will follow the convention that
vertices in VG1N and VG2N are named as when describing one verification gadget, and the index of
the gadget (1 or 2) appears in the superscript; e.g., v 1 [i, j] denotes the vertex of the grid in the
first gadget in the ith column and jth row. Place VG1N and VG2N next to each other, and for each
i ∈ [N ], add an edge between z 1 [i] and y 2 [i] with weight M5 − iM3 − iM2 . Further, for each i ∈ [N ]
add a new interface vertex p[i] and q[i], connected as follows: p[i] is adjacent to y[i] via an edge
of weight iM1 , while q[i] is adjacent to z[i] via an edge of weight M2 − iM1 . The interfaces of the
paired verification gadget are vertices p[·], q[·], and w1 , w2 .
p[1]

z 2 [1]

M5 − iM3 − iM2

iM1

p[N ]

y 2 [1]

z 1 [1]

y[1]

z 1 [N ]

y 1 [N ]

q[1]

M2 − iM1

y 2 [N ]

z 2 [N ]

q[N ]

w2

w1

Figure 10: The paired verification gadget of order N . Old interfaces y t [·] and z t [·] are depicted in
gray. An intended solution connecting p[i], q[i], and w1 is highlighted in blue.
The following lemmas explain the optimum behavior in a paired verification gadget.

45

Lemma 7.7. For each i ∈ [N ] and each t ∈ {1, 2}, the paired verification gadget PVGN contains a
tree of total weight 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 that connects p[i], q[i], and wt .
Proof. Take the union of paths (p[i], y 1 [i], v 2 [1, i], . . . , v 1 [N, i], z 1 [i], y 2 [i], v 2 [1, i], . . . , v 2 [N, i], z 2 [i], q[i])
and (v t [i, i], . . . , v t [i, N ], wt ). It is easy to verify that its weight is exactly 2M5 + 2(N − 1)M4 + (N −
1)M3 + M2 .
Lemma 7.8. Suppose that H is a subgraph of the paired verification gadget PVGN such that H is
a (connected) tree and contains wt for some t ∈ {1, 2}, p[i] for some i ∈ [N ], and q[j] for some
j ∈ [N ]. Then the total weight of the edges of H is at least 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 .
Furthermore, if this total weight is equal to 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 , then i = j and
H contains the edge between wt and v t [i, N ].
Proof. Suppose that the total cost of H is at most 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 . Obviously,
H has to contain edges p[i]y 1 [i] and z 2 [j]q[j], which have weight M2 + (i − j)M1 in total, so in
particular H connects y 1 [i], z 2 [j], and wt . Observe further that H has to contain the edge z 1 [k]y 2 [k]
for some k ∈ [N ], which has weight M5 − kM3 − kM2 > 34 M5 , as well as at least one edge incident
to wt , which has weight at least M5 − N · M2 > 34 M5 . Thus, these two edges alone have weight
larger than 32 M5 . If H contained at least one more edge between vertices y 2 [·] and z 1 [·], its total
weight would be larger than 94 M5 , so in particular larger than 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 .
Hence, z 1 [k]y 2 [k] is the only edge between VG1N and VG2N included in H.
Let H s be the restriction of H to the verification gadget VGsN , for s = 1, 2. Recall that H
connects p[i], q[j], and wt ; from now on suppose that t = 1, since the proof for the second case is
symmetric. Since z 1 [k]y 2 [k] is the only edge between the gadgets included in H, it follows that H 1
connects y 1 [i], z 1 [k], and w1 , whereas H 2 connects y 2 [k] with z 2 [j]. By Lemma 7.6, the total weight
of H 1 is at least M5 + (N − 1)M4 + (N − 1)M3 , and the equality can occur if and only if i = k.
Moreover, since H 2 connects y 2 [k] with z 2 [j], it must contain at least N − 1 horizontal edges and at
least |j − k| vertical edges of the grid in the second gadget. It follows that the total weight of H 2 is
at least
kM2 + jM3 + (N − 1)M4 + |k − j|M3 = (N − 1)M4 + kM3 + kM2 + (j − k)M3 + |j − k|M3 .
It follows that this value is never smaller than (N − 1)M4 + kM3 + kM2 , and the equality holds only
if k ≥ j. Further, if k < j, then this values is larger by at least M3 than (N − 1)M4 + kM3 + kM2 .
We conclude that the total weight of H has to be at least
M5 + (N − 1)M4 + (N − 1)M3 + (M5 − kM3 − kM2 ) + ((N − 1)M4 + kM3 + kM2 ) + M2 + (i − j)M1 ,
where the consecutive terms come from H 1 , the edge z 1 [k]y 2 [k], H 2 , and edges p[i]y 1 [i] and z 2 [j]q[j]
This is equal to
2M5 + (2N − 2)M4 + (N − 1)M3 + M2 + (i − j)M1 .
On the other hand, the total weight of H is assumed to be at most 2M5 +2(N −1)M4 +(N −1)M3 +M2 ;
this may be smaller or equal than the value above only if i ≤ j, and then it is smaller by |(i − j)M1 |.
Observe now that |(i − j)M1 | < M3 , so the contribution from H 2 cannot be larger by at least M3
than the value (N − 1)M4 + kM3 + kM2 we counted. As we argued, this implies that k ≥ j. Further,
recall that the contribution from H 1 can be equal to M5 + (N − 1)M4 + (N − 1)M3 only if i = k and
H 1 uses the edge w1 v 1 [i, N ]. All weights within the first gadget VG1N are multiples of M2 , so if this
contribution is larger than M5 + (N − 1)M4 + (N − 1)M3 , then it is larger by at least M2 . However,
|(i − j)M1 | < M2 as well, so we infer that i = k and H 1 uses the edge w1 v 1 [i, N ]. Since i = k and
46

k ≥ j, we have i ≥ j, so i − j ≥ 0. It follows that the term (i − j)M1 is nonnegative, and it is zero
only if i = j. So all in all, the weight of H has to be at least 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ,
and the equality can hold if and only if i = j = k and H uses the edge w1 v 1 [i, N ].
Similarly as with single verification gadgets, we can restrict a paired verification gadget by a
pair of subsets S1 , S2 ⊆ [N ]. This means that for each i ∈ [N ] \ S1 we remove the edge w1 v 1 [i, N ]
and for each i ∈ [N ] \ S2 we remove the edge w2 v 2 [i, N ]. By Lemmas 7.7 and 7.8, this restricts the
space of solutions of the optimum weight 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 to trees connecting
p[i], q[i], and w1 for i ∈ S 1 , and trees connecting p[i], q[i], and w2 for i ∈ S 2 .

7.2

Partitioning variables into groups and the intuition

For simplicity and without loss of generality, by making ε slightly smaller we assume that ε = 1/L
for some fixed integer L. Let ϕ be the input formula, let V, C denote the variable and clause set
of ϕ, respectively, and let n = |V| and m = |C|. By adding dummy variables if necessary, we can
assume without loss of generality that n is divisible by L.
We partition the variables into L groups V1 , . . . , VL , of size n/L each. For each t ∈ [L], let Λt be
the set of all variable assignments for the group Vt , that is, functions from Vt to {T, F}. Note that
|Λt | = 2|Vt | = 2n/L for each t ∈ [L].
We now describe the intuition behind the rest of the construction; see Figure 11 for reference.
We create one root terminal r placed on the very west of the whole construction. Then, for each
variable group Vt we create a row consisting of 4m verification gadgets of order 3 · 2n/L , grouped
into m columns with 4 verification gadgets per row in each column. These four verification gadgets
are paired into two paired verification gadgets. The western pair is placed normally, as defined
in the previous section, so that its interfaces w1 and w2 are placed southward. The eastern pair
is rotated by 180◦ so that its interfaces are placed northward. The western and eastern pairs are
combined naturally within each quadruple, but the connections between quadruples will be slightly
more complicated for technical reasons that will become clear later. At the eastern end of each
row we create one terminal. The columns of quadruples of verification gadgets are then connected
via connector gadgets as follows: identify the northern interfaces of the connector gadget with
(southbound) interfaces wt of the western pair of the northern quadruple, and identify the southern
interfaces of the connector gadget with the (northbound) interfaces wt of the eastern pair in the
southern quadruple.
Since each edge within a connector gadget is far more expensive than all the other edges in
total, within each connector gadget we need to pick one of two optimum solutions. This enables
coordination of choices throughout columns without creating vertical paths, and the optimum
solution must send one horizontal path through each row that “collects” terminals from neighboring
connector gadgets on the way. The forced optimum behavior within verification gadgets ensures us
that these paths need to be indeed horizontal — within each row they need to choose the same
index i within each verification gadget. The choice of this index i within row t corresponds to
choosing the variable assignment for group Vt from Λt . Then the satisfaction of clauses is verified by
appropriately restricting each verification gadget, so that each column of quadruples of verification
gadgets is responsible for checking one clause. Here we use the one-bit information transported via
connector gadgets to implement this check.
We proceed with implementing this plan formally.

47

7.3

Construction

We now give the full construction. For simplicity of presentation, we aim at constructing a graph
of size bounded by O(2Kε(n+m) · (n + m)c ) for some universal constants K, c, because at the very
end we can rescale ε by factor K; that is, we actually apply the whole construction for ε/K instead
of ε. Denote N = 3 · 2n/L , which is equal to 3|Λt | for all t = 1, . . . , L. For the embedding of the
construction in the plane, we refer to Figure 11.
PVGW
1,1

PVGW
1,3

PVGE
1,1

PVGE
1,3

h1

CG1,3

CG1,2

CG1,1

h2

r

CG2,2

CG2,1

CG2,3

h3

PVGW
3,1

PVGE
3,1

PVGW
3,3

PVGE
3,3

Figure 11: The whole construction for m = 3, L = 3, and n/L = 2. A possible solution is highlighted
in blue. It corresponds to a variable assignment where c1 is satisfied by a variable from the V3 , c2 is
satisfied by a variable from V1 , and c3 is satisfied by a variable from V2 .
Create first a terminal r, and a terminal ht for each t ∈ [L].
For each t ∈ [L] and each j ∈ [m], create two paired verification gadgets of order N , denoted
E
W
PVGW
t,j and PVGt,j . We will follow the convention that the interface vertices of the gadget PVGt,j
W,1
W,2
W
will be denoted by pW
t,j [i] for i ∈ [N ], qt,j [i] for i ∈ [N ], and wt,j , wt,j ; similarly for the gadget
W [i] and q E [N + 1 − i].
PVGEt,j . For each i ∈ [N ], identify vertices qt,j
t,j
For each t ∈ [L], j ∈ [m], and s ∈ [2n/L ] create a vertex gt,j [s]. Connect each vertex gt,j [s] with
the following vertices via edges of weight M6 :
• pW
t,j [3s − `] for ` = 0, 1, 2, and
• pEt,j−1 [N + 1 − (3s − `)] for ` = 0, 1, 2, unless j = 1.
Moreover, connect vertices gt,1 [s] to r via edges of weight M6 . Also, for each t ∈ [L] connect ht to
all vertices pEt,m [i] via edges of weight M6 , for i ∈ [N ].
For each t ∈ [L − 1] and each j ∈ [m] create a connector gadget CGt,j . We will follow the
NE
SE
SW
convention that the interface vertices of this gadget will be denoted by xNW
t,j , xt,j , xt,j , and xt,j .
We identify:
W,1
• xNW
t,j with wt,j ;
W,2
• xNE
t,j with wt,j ;

48

E,1
• xSE
t,j with wt+1,j ; and
E,2
• xSW
t,j with wt+1,j .
E,1
W,2
Moreover, for each j ∈ [m], we make vertices w1,j
and wL,j
into terminals.
Finally, we remove some edges from the constructed graph by restricting the paired verification
gadgets in order to encode the input formula ϕ. For each variable group Vt , choose an arbitrary
enumeration (λt,1 , . . . , λt,2n/L ) of Λt . Moreover, let (c1 , . . . , cm ) be an arbitrary enumeration of C.
For each t ∈ [L] and j ∈ [m] we perform the following restrictions. Suppose R ⊆ [2n/L ] is the subset
of all indices s for which the assignment λt,s satisfies the formula cj ; that is, there is a variable in Vt
that appears in cj and setting it according to λt,s satisfies cj Define
W,1
St,j
= {3s − 1 : s ∈ [2n/L ]}

and

W,2
St,j
= {3s : s ∈ R} ∪ {3s − 2 : s ∈ [2n/L ]},

W,1
W,2
and restrict the paired verification gadget PVGW
t,j by the pair (St,j , St,j ). Similarly, define
E,1
St,j
= {(N +1)−3s : s ∈ R}∪{(N +1)−(3s−1) : s ∈ [2n/L ]}

and

E,2
St,j
= {(N +1)−(3s−2) : s ∈ [2n/L ]},

E,2
E,1
, St,j
).
and restrict the paired verification gadget PVGEt,j by the pair (St,j
We set M to be 10 times larger than the total number of edges used in the construction; this
automatically defines the weights M1 through M7 . Finally, we set the budget for the intended
Steiner tree to be

k = 6m(L − 1)M7 + (2m + 1)LM6 + 2mL(2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ).
This finishes the construction. The following claim follows directly from the construction, where the
plane embedding is as in Figure 11.
Lemma 7.9. The obtained instance (G, T ) of Steiner Tree is planar, and we have
|G| ≤ O(22εn · (n + m))

and

|T | ≤ 6ε−1 (n + m).

Moreover, the instance (G, T ) can be constructed in time linear in its size.

7.4

Correctness

Hence, we are left verifying the following claim.
Lemma 7.10. The instance (G, T ) admits a Steiner tree of total weight at most k if and only if ϕ
is satisfiable.
The remainder of this section is devoted to the proof of Lemma 7.10. We split the proof into
two implications: we first show that if ϕ is satisfiable then (G, T ) has a Steiner tree of appropriate
weight, and next we show the converse implication.
From a satisfying assignment to a Steiner tree. Suppose λ : V → {T, F} is an assignment
that satisfies ϕ. For each t ∈ [L] pick the index st ∈ [2n/L ] such that λt,st is the restriction of λ to
Vt . Next, for each j ∈ [m] arbitrarily pick an index tj such that a variable belonging to Vtj satisfies
ϕ under λ.
We now construct the tree as follows. For each t ∈ [L] and j ∈ [m], pick it,j = 3 · st − a, where
a = 1 if t < tj , a = 2 if t > tj , and a = 0 if t = tj . Then take into the solution the following:
49

W,a
W,2
W
W
• the subtree of PVGW
t,j connecting pt,j [it,j ], qt,j [it,j ], and (wt,j if a 6= 0 and wt,j if a = 0) with
total weight 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ; and
E [(N + 1) − i ], pE [(N + 1) − i ], and (w W,a if a 6= 0 and
• the subtree of PVGEt,j connecting qt,j
t,j
t,j
t,j
t,j
W,1
wt,j
if a = 0) with total weight 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 .
W [i ] = q E [(N + 1) − i ], so the union of
These subtrees exist by Lemma 7.7. Note also that qt,j
t,j
t,j
t,j
W,a
W,2
E
these two trees is a tree connecting pW
t,j [it,j ], pt,j [(N + 1) − it,j ], (wt,j if a 6= 0 and wt,j if a = 0),
W,a
W,1
and (wt,j
if a 6= 0 and wt,j
if a = 0).
Further, for each t ∈ [L] and each j ∈ [m], add to the solution the edge between gt,j [st ] and
E
pW
[i
t,j t,j ], and the edge between gt,j [st ] and pt,j−1 [(N + 1) − it,j ] provided j > 1, and between gt,1 [st ]
and r for j = 1. All these edges exist since it,j = 3 · st − a for some a ∈ {0, 1, 2}. Also, for each
t ∈ [L] add the edge between pEt,m [(N + 1) − it,m ] and ht . Finally, for each connector gadget CGt,j ,
for t ∈ [L − 1] and j ∈ [m], we add the solution of weight 6M7 connecting terminals within CGt,j to
SE
NE
SW
xNW
t,j and xt,j in case t < tj , and to xt,j and xt,j in case t ≥ tj . It is straightforward to verify that
the solution obtained in this manner has total weight exactly k and connects all terminals to the
root terminal r.

From a Steiner tree to a satisfying assignment. Suppose the instance (G, T ) admits a
Steiner tree F , treated as a subset of edges of G, of total weight at most k. The edges of F can be
partitioned into three subsets:
• edges FCG that reside in connector gadgets CGt,j for t ∈ [L − 1] and j ∈ [m];
E
• edges FPVG that reside in paired verification gadgets PVGW
t,j and PVGt,j for t ∈ [L] and j ∈ [m];

• the remaining edges Frest .
We now investigate these subsets basing the analysis on the fact that F has total weight at most k.
First, we consider connector gadgets CGt,j for all t ∈ [L − 1] and j ∈ [m]. Since each terminal
within CGt,j has to be connected to r by F , it follows that FCG ∩ E(CGt,j ) connects each terminal
within CGt,j to one of its interface vertices. By Lemma 7.4, this means that each set FCG ∩ E(CGt,j )
consists of at least 6 edges, implying that the total cost of FCG is at least 6m(L−1)M7 . If at least one
more edge of weight M7 was taken to FCG , then its total weight would be at least 6m(L − 1)M7 + M7 ,
which is larger than k; this would be a contradiction. We infer that within each connector gadget
CGt,j , the set FCG selects exactly 6 edges, which connect each terminal of this gadget to one of its
interfaces. By Lemma 7.4, we have that within each CGt,j , the set FCG either connects two terminals
SE
NE
SW
to xNW
t,j and two to xt,j , or it connects two terminals to xt,j and two to xt,j . Call connector gadgets
conforming to the former case of type 1, while connector gadgets conforming to the latter case shall
be called of type 2. Note that in particular, FCG ∩ CGt,j does not connect any northern interface of
CGt,j with any southern interface.
We thus have that the total weight of FCG is exactly 6m(L − 1)M7 , so the total weight of
Frest ∪ FPVG is at most (2m + 1)LM6 + 2mL(2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ). Observe
now that for each terminal ht for t ∈ [L], the tree F has to contain a path from r to ht . By the
construction and the above discussion of the behavior of F within each connector gadget, the path
E
connecting F with ht must be contained in the union of paired verification gadgets PVGW
t,j , PVGt,j
for j ∈ [m], edges incident to ht , and edges incident to vertices gt,j [s] for j ∈ [m] and s ∈ [2n/L ]. In
particular, for each t ∈ [L] we have that Frest has to contain:
• at least one edge incident to ht ;
50

• at least one edge between r and a vertex gt,1 [s] for some s ∈ [2n/L ];
• for each j ∈ [m] \ {1}, at least one edge between a vertex gt,j [s] for some s ∈ [2n/L ] and a
vertex pEt,j−1 [i] for some i ∈ [N ].
• for each j ∈ [m], at least one edge between a vertex gt,j [s] for some s ∈ [2n/L ] and a vertex
pW
t,j [i] for some i ∈ [N ].
Above we have counted at least (2m + 1)L distinct edges within Frest , each of weight M6 . Since we
have that the total weight of Frest ∪ FPVG is at most (2m + 1)LM6 + 2mL(2M5 + 2(N − 1)M4 + (N −
1)M3 + M2 ), which is smaller than (2m + 1)LM6 + M6 , we infer that Frest contains exactly one edge
of each of the above mentioned kinds, and does not contain any other edges outside of the connector
and paired verification gadget. In particular, the total weight of Frest is exactly (2m + 1)LM6 , and
for each t ∈ [L] and j ∈ [m] we can choose an index st,j ∈ [2n/L ] so that Frest contains:
• an edge between gt,j [st,j ] and pEt,j−1 [(N + 1) − (3st,j − a)] for some a ∈ {0, 1, 2} (or between
gt,1 [st,1 ] and r if j = 1); and
• an edge between gt,j [st,j ] and pW
t,j [3st,j − a] for some a ∈ {0, 1, 2}.
Since the total weight of Frest is exactly (2m + 1)LM6 , we infer that the total weight of FPVG
is at most 2mL(2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ). Observe now that the edges of FPVG
E
reside in 2mL paired verification gadgets PVGW
t,j and PVGt,j for t ∈ [L] and j ∈ [m]. By the already
established shape of sets FCG and Frest , the intersection of FPVG with each gadget PVGW
t,j has to be a
W [i0 ] for some i0 ∈ [N ], and one
tree that connects an interface pW
[i]
for
some
i
∈
[N
],
an
interface
q
t,j
t,j
W,1
W,2
of the interfaces wt,j
, wt,j
. The latter is because two terminals from the adjacent connector gadget
W,2
CGt,j have to be connected to r via PVGW
t,j , or when t = L, the terminal wL,j has to be connected
to r. By Lemma 7.8 this implies that the weight of the intersection of FPVG with PVGW
t,j has to be
at least 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 . A symmetric analysis yields the same conclusion
for the gadget PVGEt,j . Since there are 2mL such gadgets in total and the weight of FPVG is at most
E
2mL(2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 ), we infer that within each gadget PVGW
t,j and PVGt,j ,
the set FPVG has to select edges of total weight exactly 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 .
Furthermore, there are no more edges in F than all the ones counted in the above analysis.
By Lemma 7.8, this means that for each t ∈ [L] and each j ∈ [m] we can select an index it,j ∈ [N ]
W,1
W
W
so that FPVG ∩ PVGW
t,j connects pt,j [it,j ], qt,j [it,j ], and either wt,j (in case j < L and CGt,j is of
W,2
type 1) or wt,j
(in case j = L or CGt,j is of type 2). Also, the index it,j has to be in the respective
W,1
W,2
restricting set St,j
or St,j
. Similarly, we can select an index i0t,j ∈ [N ] so that FPVG ∩ PVGEt,j
E,1
0
W
0
connects pW
t,j [(N + 1) − it,j ], qt,j [(N + 1) − it,j ], and either wt,j (in case j = 1 or CGt,j is of type 1)
E,2
or wt,j
(in case j > 1 and CGt,j is of type 2). Again, the index i0t,j has to be in the respective
W,1
W,2
restricting set St,j
or St,j
.
Now observe that in order to have that the edges of F within each row of the construction
contain a path from r to respective ht , we need to have the following equality of indices for all
t ∈ [L]:

• it,j = i0t,j for all j ∈ [m];
• st,j = st,j 0 for all j, j 0 ∈ [m] (henceforth we denote this common value as st );
• it,j = 3 · st − at,j for some at,j ∈ {0, 1, 2}.
51

For t ∈ [L], let λ[t] = λt,st ∈ Λt be the variable assignment that corresponds to the index st ∈ [2n/L ].
Further, let λ be the variable assignment for ϕ obtained by taking the union of assignments λ[t] for
t ∈ [L]. We claim that λ is a satisfying assignment for ϕ. To this aim, we examine the properties of
the offsets at,j ∈ {0, 1, 2}.
Claim 7.11. If at,j = 0 for some t ∈ [L] and j ∈ [m], then λ[t] satisfies cj .
Proof. Since at,j = 0, we have that it,j = 3st . By the construction, if λ[t] = λt,st did not satisfy cj ,
W,1
W,2
E,1
E,2
then neither it,j would be included in St,j
∪ St,j
, nor (N + 1) − it,j would be included in St,j
∪ St,j
.
W
As we argued, from Lemma 7.8 it follows that the intersection of SPVG with PVGt,j would have
weight more than 2M5 + 2(N − 1)M4 + (N − 1)M3 + M2 , and the same holds also for and PVGEt,j .
This is a contradiction.
y
Claim 7.12. For all t ∈ [L − 1] and j ∈ [m], the pair (at,j , at+1,j ) belongs to the following set:
{(1, 1), (1, 0), (0, 2), (2, 2)}. Moreover, a1,j 6= 2 and aL,j 6= 1 for all j ∈ [m].
W,1
Proof. Suppose first that at,j = 1. Then it,j = 3st − 1, and this number is included only in St,j
,
W,2
W,1
NW
and not in St,j
. It follows that F ∩ PVGW
t,j connects the interface wt,j = xt,j to r, which implies
that the connector gadget CGt,j must be of type 1 in order to have its terminals connected to r. In
E,1
particular, F ∩ PVGEt+1,j has to connect wt,j+1
= xSE
t,j to r. By the construction of the restricting set
E,1
St+1,j
, this implies that it+1,j = 3st+1 or it+1,j = 3st+1 − 1, which means that at+1,j ∈ {0, 1}. We
can analogously prove that if at,j ∈ {0, 2}, then at+1,j = 2.
E,1
W,2
To see that a1,j =
6 2 and aL,j 6= 1 for all j ∈ [m], recall that both w1,j
and wL,j
are terminals.
These terminals need to be connected to r. If we had a1,j = 2 then we would have i1,j = 3s1 − 2, but
E,1
the value (N + 1) − (3s1 − 2) is not included in the restricting set S1,j
; this would be a contradiction.
The case aL,j = 1 leads to a contradiction in a symmetric manner.
y

By Claim 7.12, for each j ∈ [m] the sequence (a1,j , a2,j , . . . , aL,j ) has the following structure:
first a (possibly empty) prefix of entries 1, then a single entry 0, and then a (possibly empty) suffix
of entries 2. In particular, for each j ∈ [m] there exists some tj ∈ [L] such that atj ,j = 0. By
Claim 7.11, this implies that λ[tj ] satisfies the clause cj . Since j was taken arbitrarily, we conclude
that λ satisfies ϕ.
Removing the weights and wrapping up the proof. All in all, we have obtained an instance
(G, T ) with the following properties:
• |G| ≤ O(22εn · (n + m));
• edges in G have weights bounded by O(|G|7 );
• |T | ≤ 6ε−1 (n + m); and
• (G, T ) admits a Steiner tree of total weight at most k if and only if ϕ is satisfiable.
We now replace each edge of weight ` by a path of length ` consisting of unit-weight edges; it is
easy to see that this yields an instance with the same value of the optimum. Observe that thus the
size of G grows to O(216εn · (n + m)8 ), the number of terminals does not change, and in the final
instance all the edges have unit weights. Hence, by performing the whole reduction for parameter
ε/16 instead of ε we obtain an instance of size O(2εn · (n + m)8 ), at most 96ε−1 (n + m) terminals,
and all edges of unit weight. This concludes the proof.
52

References
[1] P. Aboulker, N. Brettell, F. Havet, D. Marx, and N. Trotignon. Colouring graphs with
constraints on connectivity. CoRR, abs/1505.01616, 2015.
[2] M. Bateni, E. D. Demaine, M. Hajiaghayi, and D. Marx. A PTAS for planar Group Steiner
Tree via spanner bootstrapping and prize collecting. In STOC 2016, pages 570–583. ACM,
2016.
[3] M. Bateni, M. Hajiaghayi, P. N. Klein, and C. Mathieu. A polynomial-time approximation
scheme for planar Multiway Cut. In SODA 2012, pages 639–655. SIAM, 2012.
[4] M. Bateni, M. T. Hajiaghayi, and D. Marx. Approximation schemes for steiner forest on planar
graphs and graphs of bounded treewidth. J. ACM, 58(5):21:1–21:37, 2011.
[5] G. Borradaile and P. N. Klein. The two-edge connectivity survivable-network design problem
in planar graphs. ACM Trans. Algorithms, 12(3):30:1–30:29, 2016.
[6] G. Borradaile, P. N. Klein, D. Marx, and C. Mathieu. Algorithms for optimization problems in
planar graphs (Dagstuhl seminar 13421). Dagstuhl Reports, 3(10):36–57, 2013.
[7] G. Borradaile, P. N. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner
tree in planar graphs. ACM Trans. Algorithms, 5(3):31:1–31:31, 2009.
[8] J. Chen, B. Chor, M. Fellows, X. Huang, D. W. Juedes, I. A. Kanj, and G. Xia. Tight lower
bounds for certain parameterized NP-hard problems. Inf. Comput., 201(2):216–231, 2005.
[9] R. H. Chitnis, M. Hajiaghayi, and D. Marx. Tight bounds for Planar Strongly Connected
Steiner Subgraph with fixed number of terminals (and extensions). In SODA 2014, pages
1782–1801. SIAM, 2014.
[10] M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh,
and M. Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1–
41:24, 2016.
[11] M. Cygan, F. V. Fomin, B. M. P. Jansen, L. Kowalik, D. Lokshtanov, D. Marx,
M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Open problems for FPT School 2014, 2014.
http://fptschool.mimuw.edu.pl/opl.pdf.
[12] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized Algorithms. Springer, 2015.
[13] M. Cygan, M. Pilipczuk, and M. Pilipczuk. Known algorithms for Edge Clique Cover are
probably optimal. SIAM J. Comput., 45(1):67–83, 2016.
[14] E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866–893,
2005.
[15] F. Dorn, E. Penninkx, H. L. Bodlaender, and F. V. Fomin. Efficient exact algorithms on planar
graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790–810, 2010.
[16] S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195–207, 1971.
53

[17] D. Eisenstat, P. N. Klein, and C. Mathieu. An efficient polynomial-time approximation scheme
for Steiner forest in planar graphs. In SODA 2012, pages 626–638. SIAM, 2012.
[18] D. Eisenstat, P. N. Klein, and C. Mathieu. Approximating k-center in planar graphs. In SODA
2014, pages 617–627. SIAM, 2014.
[19] J. Erickson, P. N. Klein, D. Marx, and C. Mathieu. Algorithms for optimization problems in
planar graphs (Dagstuhl seminar 16221). Dagstuhl Reports, 6(5):94–116, 2016.
[20] F. V. Fomin, S. Kolay, D. Lokshtanov, F. Panolan, and S. Saurabh. Subexponential algorithms
for rectilinear Steiner tree and arborescence problems. In SoCG 2016, volume 51 of LIPIcs,
pages 39:1–39:15. Schloss Dagstuhl — Leibniz-Zentrum fuer Informatik, 2016.
[21] F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth
pattern covering. In FOCS 2016, pages 515–524. IEEE Computer Society, 2016.
[22] F. V. Fomin and D. M. Thilikos. New upper bounds on the decomposability of planar graphs.
Journal of Graph Theory, 51(1):53–81, 2006.
[23] K. Fox, P. N. Klein, and S. Mozes. A polynomial-time bicriteria approximation scheme for
planar bisection. In STOC 2015, pages 841–850. ACM, 2015.
[24] M. R. Garey and D. S. Johnson. The rectilinear steiner tree problem in NP complete. SIAM
Journal of Applied Mathematics, 32:826–834, 1977.
[25] Q. Gu and H. Tamaki. Optimal branch-decomposition of planar graphs in O(n3 ) time. ACM
Trans. Algorithms, 4(3):30:1–30:13, 2008.
[26] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity?
J. Comput. Syst. Sci., 63(4):512–530, 2001.
[27] P. N. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with
edge-weights. SIAM J. Comput., 37(6):1926–1952, 2008.
[28] P. N. Klein and D. Marx. Solving Planar k-Terminal Cut in O(nc
volume 7391 of LNCS, pages 569–580. Springer, 2012.

√

k)

time. In ICALP 2012,

[29] P. N. Klein and D. Marx. A subexponential parameterized algorithm for Subset TSP on planar
graphs. In SODA 2014, pages 1812–1830. SIAM, 2014.
[30] P. N. Klein, C. Mathieu, and H. Zhou. Correlation clustering and two-edge-connected augmentation for planar graphs. In STACS 2015, volume 30 of LIPIcs, pages 554–567. Schloss
Dagstuhl — Leibniz-Zentrum fuer Informatik, 2015.
[31] D. Lokshtanov, D. Marx, and S. Saurabh. Slightly superexponential parameterized problems.
In SODA 2011, pages 760–776. SIAM, 2011.
[32] D. Lokshtanov, S. Saurabh, and M. Wahlström. Subexponential parameterized odd cycle
transversal on planar graphs. In FSTTCS 2012, volume 18 of LIPIcs, pages 424–434. Schloss
Dagstuhl — Leibniz-Zentrum fuer Informatik, 2012.
[33] D. Marx. A tight lower bound for Planar Multiway Cut with fixed number of terminals. In
ICALP 2012, volume 7391 of LNCS, pages 677–688. Springer, 2012.
54

[34] D. Marx. What’s next? future directions in parameterized complexity. In The Multivariate
Algorithmic Revolution and Beyond, volume 7370 of LNCS, pages 469–496. Springer, 2012.
[35] D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location
problems using Voronoi diagrams. In ESA 2015, volume 9294 of LNCS, pages 865–877. Springer,
2015.
[36] D. Marx and M. Pilipczuk. Optimal parameterized algorithms for planar facility location
problems using Voronoi diagrams. CoRR, abs/1504.05476, 2015.
[37] J. Nederlof. Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner
tree and related problems. In ICALP 2009 (1), volume 5555 of LNCS, pages 713–725. Springer,
2009.
[38] M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen. Subexponential-time
parameterized algorithm for Steiner tree on planar graphs. In STACS 2013, volume 20 of
LIPIcs, pages 353–364. Schloss Dagstuhl — Leibniz-Zentrum fuer Informatik, 2013.
[39] M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen. Network sparsification for
Steiner problems on planar and bounded-genus graphs. In FOCS 2014, pages 276–285. IEEE
Computer Society, 2014.
[40] P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217–241,
1994.
[41] O. Suchý. Extending the kernel for Planar Steiner Tree to the number of Steiner vertices. In
IPEC 2015, volume 43 of LIPIcs, pages 151–162. Schloss Dagstuhl — Leibniz-Zentrum fuer
Informatik, 2015.
[42] S. Tazari. Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free
graphs. Theor. Comput. Sci., 417:95–107, 2012.

55

