Planar Disjoint-Paths Completionab

arXiv:1511.04952v2 [] 17 Nov 2015

Isolde Adlerc

Stavros G. Kolliopoulosd

Dimitrios M. Thilikosef

Abstract
We introduce Planar Disjoint Paths Completion, a completion counterpart of
the Disjoint Paths problem, and study its parameterized complexity. The problem
can be stated as follows: given a, not necessarily connected, plane graph G, k pairs
of terminals, and a face F of G, find a minimum-size set of edges, if one exists,
to be added inside F so that the embedding remains planar and the pairs become
connected by k disjoint paths in the augmented network. Our results are twofold:
first, we give an upper bound on the number of necessary additional edges when a
solution exists. This bound is a function of k, independent of the size of G. Second,
we show that the problem is fixed-parameter tractable, in particular, it can be solved
in time f (k) · n2 .

Keywords: Completion Problems, Disjoint Paths, Planar Graphs.

1

Introduction

Suppose we are given a planar road network with n cities and a set of k pairs of them.
An empty area of the network is specified and we wish to add a minimum-size set of
a

The second and the third author where co-financed by the European Union (European Social Fund
– ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning”
of the National Strategic Reference Framework (NSRF) - Research Funding Program: “Thalis. Investing
in knowledge society through the European Social Fund”.
b
Emails: Isolde Adler: iadler@informatik.uni-frankfurt.de, Stavros Kolliopoulos: sgk@di.uoa.gr, Dimitrios M. Thilikos: sedthilk@thilikos.info
c
Institut für Informatik, Goethe-Universität, Frankfurt, Germany.
d
Department of Informatics and Telecommunications, National and Kapodistrian University of
Athens, Athens, Greece.
e
Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece.
f
AlGCo project-team, CNRS, LIRMM, France.

1

intercity roads in that area so that the augmented network remains planar and the pairs
are connected by k internally disjoint roads. In graph-theoretic terms, we are looking for
a minimum-size edge-completion of a plane graph so that an infeasible instance of the
Disjoint Paths problem becomes feasible while maintaining planarity. In this paper
we give an algorithm that solves this problem in f (k) · n2 steps. Our algorithm uses
a combinatorial lemma stating that, whenever such a solution exists, its size depends
exclusively on k.
The renowned Disjoint Paths Problem (DP) is defined as follows.
DP(G, s1 , t1 , . . . , sk , tk )
Input: An undirected graph G and k pairs of terminals
s1 , t1 , . . . , sk , tk ∈ V (G).
Question: are there k pairwise internally vertex-disjoint paths
Q1 , . . . Qk in G such that path Qi connects si to ti ?
(By pairwise internally vertex-disjoint we mean that two paths can
only intersect at a vertex which is a terminal for both.)
DP is NP-complete even on planar graphs [14] but, when parameterized by k, the
problem belongs to the parameterized complexity class FPT, i.e., it can be solved in time
f (k) · nO(1) , for some function f. More precisely, it can be solved in f (k) · n3 time by the
celebrated algorithm of Robertson and Seymour [19] from the Graph Minors project.
For planar graphs, the same problem can be solved in f (k) · n [16].
We introduce a completion counterpart of this problem, Planar Disjoint Paths
Completion (PDPC), which is of interest on infeasible instances of DP, and we
study its parameterized complexity, when parameterized by k. We are given an embedding of a, possibly disconnected, planar graph G in the sphere, k pairs of terminals
s1 , t1 , . . . , sk , tk ∈ V (G), a positive integer `, and an open connected subset F of the
surface of the sphere, such that F and G do not intersect (we stress that the boundary
of F is not necessarily a cycle). We want to determine whether there is a set of at most
` edges to add, the so-called patch, so that
(i) the new edges lie inside F and are incident only to vertices of G on the boundary of
F,
(ii) the new edges do not cross with each other or with G, and
(iii) in the resulting graph, which consists of G plus the patch, DP has a solution.
PDPC is NP-complete even when ` is not a part of the input and G is planar by
the following simple reduction from DP: add a triangle T to G and let F be the interior

2

of T. That way, we force the set of additional edges to be empty and obtain DP as a
special case.
Notice that our problem is polynomially equivalent to the minimization problem
where we ask for a minimum-size patch: simply solve the problem for all possible values
of `. Requiring the size of the patch to be at most ` is the primary source of difficulty.
In case there is no restriction on the size of the patch and we simply ask whether one
exists, the problem is in FPT by a reduction to DP, which is summarized as follows.
For simplicity, let F be an open disk. Let G0 be the graph obtained by “sewing” along
the boundary of F an O(n) × O(n)-grid. By standard arguments, PDPC has a solution
on G if and only if DP has a solution on G0 . A similar, but more involved, construction
applies when F is not an open disk.
Parameterizing completion problems. Completion problems are natural to define:
take any graph property, represented by a collection of graphs P, and ask whether it is
possible to add edges to a graph so that the new graph is in P. Such problems have been
studied for a long time and some of the most prominent are the following: Hamiltonian
Completion [8, GT34], Path Graph Completion [8, GT36] Proper Interval
Graph Completion [9] Minimum Fill-In [20] Interval Graph Completion [8,
GT35].
Kaplan et al. in their seminal paper [12] initiated the study of the parameterized
complexity of completion problems and showed that Minimum Fill-In, Proper Interval Graph Completion and Strongly Chordal Graph Completion are in
FPT when parameterized by the number of edges to add. Recently, the problem left
open by [12], namely Interval Graph Completion was also shown to be in FPT [11].
Certainly, for all these problems the testing of the corresponding property is in P, while
for problems such as Hamiltonian Completion, where P is the class of Hamiltonian
graphs, there is no FPT algorithm, unless P=NP. For the same reason, one cannot expect
an FPT-algorithm when P contains all YES-instances of DP, even on planar graphs. We
consider an alternative way to parameterize completion problems, which is appropriate
for the hard case, i.e., when testing P is intractable: we parameterize the property itself.
In this paper, we initiate this line of research, by considering the parameterized property
Pk that contains all YES-instances of DP on planar graphs with k pairs of terminals.
Basic concepts. As open sets are not discrete structures, we introduce some formalism
that will allow us to move seamlessly from topological to combinatorial arguments. The
definitions may look involved at first reading, but this is warranted if one considers, as we
do, the problem in its full generality where the input graph is not necessarily connected.

3

Let G be a graph embedded in the sphere Σ0 . Embeddings are always without crossings and we view the graph G as a subset of Σ0 . Given a set X ⊆ Σ0 , let clos(X),
int(X), and ∂X denote the closure, the interior, and the boundary of X, respectively.
We define V (X) = V (G) ∩ ∂X. A noose is a Jordan curve of Σ0 that meets G only on
vertices. Let D be a finite collection of mutually non-intersecting open disks of Σ0 whose
boundaries are nooses and such that each point that belongs to at least two such nooses
S
is a vertex of G. We define ID = D∈D D and define ΓD as the Σ0 -embedded graph
whose vertex set is V (ID ) and whose edge set consists of the connected components of
the set ∂ID \V (ID ). Notice that, in the definition of ΓD , we permit multiple edges, loops,
or vertex-less edges.
Let J be an open subset of Σ0 . J is a cactus set of G if there is a collection D as
above such that J = ID , all biconnected components of the graph ΓD are cycles, V (G) ⊆
clos(J), and each edge of E(G) is a subset of J. Given such a J, we define ΓJ = ΓD . Two
cactus sets J and J0 of G are isomorphic if ΓJ and ΓJ0 are topologically isomorphic.
Throughout this paper, we use the standard notion of topological isomorphism between
planar embeddings, see Section 2.

Figure 1: A cactus set J and the vertices of V (J). Next to each vertex v we give its multiplicity
µ(v).

Given a cactus set J, we define for each vertex v ∈ V (J) its multiplicity µ(v) to be
equal to the number of connected components of the set ΓJ \ {v}, minus the number of
P
connected components of ΓJ , plus one. We also define µ(J) = v∈V (J) µ(v). Observe
that, given a cactus set J of G, the edges of G lie entirely within the interior of J. See
Figure 1. The boundary of J corresponds to a collection of simple closed curves such
that

4

(i) no two of them intersect at more than one point and
(ii) they intersect with G only at (some of) the vertices in V (G).
Cactus sets are useful throughout our paper as “capsule” structures that surround G
and thus they abstract the interface of a graph embedding with the rest of the sphere
surface.
We say that an open set F of Σ0 is an outer-cactus set of G if Σ0 \ clos(F) is a cactus
set of G. See Fig. 2.(ii). For example, if G is planar, any face F of G can be used to
define an outer-cactus set, whose boundary meets G only at the vertices incident to F.
Our definition of an outer-cactus set is more general: it can be a subset of a face F,
meeting the boundary of F only at some of its vertices.
Let G be an input graph to DP, see Figure 2.(i). Given an outer-cactus set F of G,
an F-patch of G is a pair (P, J) where (i) J is a cactus set of G, where Σ0 \ clos(J) ⊆ F
and (ii) P is a graph embedded in Σ0 without crossings such that E(P ) ⊆ Σ0 \ clos(J),
V (P ) = V (J) (see Figures 2.(iii) and 2.(iv)). Observe that the edges of P do not cross
any edge in E(G). In the definition of the F-patch, the graph P contains the new edges we
add. The vertices in V (F) define the vertices of G which we are allowed to include in P.
V (J) is meant to contain those vertices of V (F) that become vertices (possibly isolated)
of P. In terms of data structures, we assume that a cactus set J is represented by the
(embedded) graph ΓJ . Similarly an outer-cactus set F is represented by the (embedded)
graph ΓΣ0 \clos(F) .
We restate now the definition of the Planar Disjoint Paths Completion problem
as follows:
PDPC(G, s1 , t1 , . . . , sk , tk , `, F)
Input: A graph G embedded in Σ0 without crossings, terminals
s1 , t1 , . . . , sk , tk ∈ V (G), a positive integer `, and an outer-cactus set F of
G.
Parameter: k
Question: Is there an F-patch (P, J) of G, such that |P | ≤ ` and
DP(G ∪ P, s1 , t1 , . . . , sk , tk ) has a solution? Compute such an F-patch
if it exists.

If such an F-patch exists, we call it a solution for PDPC. In the corresponding optimization problem, denoted by min-PDPC, one asks for the minimum ` for which PDPC has
a solution, if one exists. See Fig. 2 for an example input of PDPC and a solution to it.
Our results. Notice that in the definition of PDPC the size of the patch does not
depend on the parameter k. Thus, it is not even obvious that PDPC belongs to the
5

Figure 2: An example input of the PDPC problem and a solution to it when ` = 8: (i) The
graph embedding in the input and the terminals s1 , t1 , s2 , t2 , s3 , t3 . The closure of the grey area
contains the graph G and the big vertices are the terminals. The white area is a face of G. (ii)
The input of the problem, consisting of G, the terminals and the outer-cactus set F. The solid
black vertices are the vertices of G that are also vertices of V (F). (iii) The solution of the problem
consists of the F-patch (P, J) where the edges of P are the dashed lines and J = J1 ∪ J2 ∪ J3 .
(iv) The input and the solution together where the validity of the patch is certified by 3 disjoint
paths.

parameterized complexity class XP, i.e., it has an algorithm of time nf (k) for some function f. Our first contribution, Theorem 2, is a combinatorial one: we prove that if a
k
patch exists, then its size is bounded by k 2 . Therefore, we can always assume that ` is
bounded by a function of k. This bound is the departure point for the proof of the main
algorithmic result of this paper:
Theorem 1. PDPC ∈ FPT. In particular, PDPC can be solved in f (k)·n2 steps, where
f is a function that depends only on k. Therefore, min-PDPC can be solved in g(k) · n2
steps.
We present now the proof strategy and the ideas underlying our results.
6

1.1

Proof strategy

Combinatorial Theorem. In Theorem 2, we prove that every patch whose size is
k
larger than k 2 , can be replaced by another one of strictly smaller size. In particular,
we identify a region B of F that is traversed by a large number of segments of different
paths of the DP solution. Within that region, we apply a global topological transformation that replaces the old patch by a new, strictly smaller one, while preserving its
embeddability in F. The planarity of the new patch is based on the fact that the new
segments are reflections in B of a set of segments of the feasible DP solution that previously lied outside B. This combinatorial result allows us to reduce the search space of
k
the problem to one whose size is bounded by min{`, k 2 }. Therefore, the construction of
the corresponding collection of “candidate solutions” can be done in advance, for each
given k, without requiring any a priori knowledge of the input graph G.
We note that the proof of our combinatorial theorem could be of independent interest.
In fact, it is one of the ingredients of the proof of the main result of [1].
The algorithm for PDPC. As the number of patches is bounded by a function of k,
we need to determine whether there is a correct way to glue one of them on vertices of
the boundary of the open set F so that the resulting graph is a YES-instance of the DP
problem. For each candidate patch P̃ , together with its corresponding candidate cactus
set J̃, we define the set of compatible graphs embedded in J̃. Each compatible graph
H̃ consists of unit-length paths and has the property that P̃ ∪ H̃ contains k disjoint
paths. Intuitively, each H̃ is a certificate of the part of the DP solution that lies within
G when the patch in F is isomorphic to P̃ . It therefore remains to check for each H̃
whether it can be realized by a collection of actual paths within G. For this, we set up
a collection H of all such certificates. Checking for a suitable realization of a member
of H in G is still a topological problem that depends on the embedding of G: graphs
that are isomorphic, but not topologically isomorphic, may certify different completions.
For this reason, our next step is to enhance the structure of the members of H so that
their realization in G reduces to a purely combinatorial check. (Cf. Section 4.1 for the
definition of the enhancement operation). We show in Lemma 6 that for the enhanced
certificates, this check can be implemented by rooted topological minor testing. For this
check, we can apply the recent algorithm of [10] that runs in h1 (k) · n3 steps and obtain
an algorithm of overall complexity h2 (k) · n3 .
We note that the use of the complicated machinery of the algorithm in [10] can be
bypassed towards obtaining a simpler and faster f (k) · n2 algorithm. This is possible
because the generated instances of the rooted topological minor problem satisfy certain
structural properties. This allows the direct application of the Irrelevant Vertex Tech7

nique introduced in [19] for solving, among others, the Disjoint Paths Problem. The
details of this improvement are in Section 5.

2

Preliminaries

We consider finite graphs. For a graph G we denote the vertex set by V (G) and the
edge set by E(G). If G is embedded in the sphere Σ0 , the edges of G and the graph G
refer also to the corresponding sets of points in Σ0 . Clearly the edges of G correspond
to open sets and G itself is a closed set. We denote by F (G) the set of all the faces of
G, i.e., all connected components of Σ0 \ G. Given a set S ⊆ V (G), we say that the pair
(G, S) is a graph rooted at S. We also denote as P(G) the set of all paths in G with at
least one edge. Given a path P ∈ P(G), we denote by I(P ) the set of internal vertices of
P. Given a vertex v ∈ V (G) and a positive integer r, we denote by NGr (v) the set of all
vertices in G that are within distance at most r from v. Given a vertex v of a graph G
with exactly two neighbors x and y, the result of the dissolution of v in G is the graph
obtained if we remove v from G and add, if it does not already exist, the edge {x, y}.
Rooted topological minors. Let H and G be graphs, SH be a subset of vertices
in V (H), SG be a subset of vertices in V (G), and ρ be a bijection from SH to SG .
We say that (H, SH ) is a ρ-rooted topological minor of (G, SG ), if there exist injections
ψ0 : V (H) → V (G) and ψ1 : E(H) → P(G) such that
1. ρ ⊆ ψ0 ,
2. for every e = {x, y} ∈ E(H), ψ1 (e) is a (ψ0 (x), ψ0 (y))-path in P(G), and
3. all e1 , e2 ∈ E(H) with e1 6= e2 satisfy I(ψ1 (e1 )) ∩ V (ψ1 (e2 )) = ∅.
In words, when H is a topological minor of G, G contains a subgraph which is
isomorphic to a subdivision of H. In addition, when (H, SH ) is a ρ-rooted topological
minor of (G, SG ) then this isomorphism respects the bijection ρ between the vertex sets
SH and SG .
Contractions. Let G and H be graphs and let σ : V (G) → V (H) be a surjective mapping such that
1. for every vertex v ∈ V (H), the graph G[σ −1 (v)] is connected;
2. for every edge {v, u} ∈ E(H), the graph G[σ −1 (v) ∪ σ −1 (u)] is connected;
3. for every {v, u} ∈ E(G), either σ(v) = σ(u), or {σ(v), σ(u)} ∈ E(H).

8

We say that H is a σ-contraction of G or simply that H is a contraction of G if such a
σ exists.
Observation 1. Let H and G be graphs such that H is a σ-contraction of G. If x, y ∈
V (G), then the distance in G between x and y is at least the distance in H between σ(x)
and σ(y).
We also need the following topological lemma.
Lemma 1. Let G be a Σ0 -embedded graph and let J be a cactus set of it. Let also M
be a Σ0 -embedded graph such that M ∩ J = ∅ and V (M ) ⊆ V (J). Then there is a closed
curve K in Σ0 \ clos(J) meeting each edge of M twice.
Proof. We consider the dual graph of ΓJ ∪ M and we remove from it all vertices lying
inside J. We denote by Q the resulting graph and notice that Q is connected because the
set Σ0 \ clos(J) is connected. Next, construct the graph Q0 by subdividing once every
edge of Q such that the subdivision vertex is the intersection point of the edge and its
dual. Let T be a spanning tree of Q0 and let K be a closed curve such that T is inside
one of the connected components of the set Σ0 \ K and J in the other. If we further
require K to intersect M a minimum number of times, we obtain the claimed curve.
Topological isomorphism. Given a graph G embedded in Σ0 , let f be a face in F (G)
whose boundary has ξ connected components A1 , . . . , Aξ . We define the set π(f ) =
{π1 , . . . , πξ } such that each πi is the cyclic ordering of V (Ai ), possible with repetitions,
defined by the way vertices are met while walking along Ai in a way that the face f is
always on our left side. Clearly, repeated vertices in this walk are cut-vertices of G.
Let G and H be graphs embedded in Σ0 . We say that G and H are topologically
isomorphic if there exist bijections φ : V (G) → V (H) and θ : F (G) → F (H) such that
1. φ is an isomorphism from G to H, i.e. for every pair {x, y} of distinct vertices in
V (G), {x, y} ∈ E(G) iff {φ(x), φ(y)} ∈ E(H).
2. For every face f ∈ F (G), φ(π(f )) = π(θ(f )).
In the definition above, by φ(π(f )) we mean {φ(π1 ), . . . , φ(πξ )}, where, if πi = (x1 , . . . ,
xζi , x1 ), then by φ(πi ), we mean (φ(x1 ), . . . , φ(xζi ), φ(x1 )). Notice that it is possible for
two isomorphic planar graphs to have embeddings that are not topologically isomorphic
(see [6, page 93] for such an example and further discussion on this topic).
Treewidth. A tree decomposition of a graph G is a pair (X , T ) where T is a tree with
nodes {1, . . . , m} and X = {Xi | i ∈ V (T )} is a collection of subsets of V (G) (called
bags) such that:

9

S
1. i∈V (T ) Xi = V (G),
2. for each edge {x, y} ∈ E(G), {x, y} ⊆ Xi for some i ∈ V (T ), and
3. for each x ∈ V (G) the set {i | x ∈ Xi } induces a connected subtree of T.
The width of a tree decomposition ({Xi | i ∈ V (T )}, T ) is maxi∈V (T ) {|Xi | − 1}. The
treewidth of a graph G denoted tw(G) is the minimum width over all tree decompositions
of G.

3

Bounding the size of the completion

In this section we show the following.
Theorem 2. If there is a solution for PDPC(G, s1 , t1 , . . . , sk , tk , `, F), then there is a
k
solution (P, J) with |E(P )| ≤ k 2 .
For the proof, we need the following combinatorial lemma.
Lemma 2. Let Σ be an alphabet of size |Σ| = k. Let w ∈ Σ∗ be a string over Σ. If
|w| > 2k , then w contains an infix y with |y| ≥ 2, such that every letter occurring in y,
occurs an even number of times in y.
Proof. Let Σ = {a1 , . . . , ak }, and let w = w1 · · · wn with n > 2k . Define vectors
zi ∈ {0, 1}k for i ∈ {1, . . . , n}, and we let the jth entry of vector zi be 0 if and only if
letter aj occurs an even number of times in the prefix w1 · · · wi of w and 1 otherwise. Since
n > 2k , there exist i, i0 ∈ {1, . . . , n} with i 6= i0 , such that zi = zi0 . Then y = wi+1 · · · wi0
proves the lemma.
We also need the following easy topological lemma.
Lemma 3. Let G be a connected outerplanar graph that may have loops but no multiple
edges (or loops) and let Γ be an embedding of G in Σ0 such that all its vertices belong to
the boundary of a face f . Let also Ein be the set of all the edges or loops of G that do
not belong to the boundary of f . Then there is a unique (up to topological isomorphism)
embedding Γ0 of G such that Γ ∩ Γ0 is the boundary of f and that all edges of Ein are
embedded inside f .
Proof. Let Γ̃ be the boundary of f . Let F be the set of all connected components of
Σ0 \ Γ̃, except from f .
For each e ∈ Ein we denote by Se the set of endpoints of e. For each edge e ∈ Ein
we define a set ē that will be the image of e in the new embedding Γ0 . We distinguish
the following two cases.
10

Case 1. |Se | = 2. Notice that Se is a separator of G. Notice also that G \ Se contains
two connected components. Also there exists a (unique) cycle Ce containing the edge e
and no other points of Γ such that each of these connected components belong each to a
distinct disk among the two disks that are bounded by Ce . We define ē = Ce \ clos(e).
Case 2. |Se | = 1. Notice that there exists a unique cycle Ce defining two disks D and
D0 such that (i) Ce ∩ Γ = Se and (ii) Γe ⊆ D where Γe is the (unique) member of F that
contains the loop e. We define ē = Ce \ Se .
Notice that it is possible to define all ē’s, one by one, such that they do not intersect.
S
Given the above definitions, it follows that Γ̃ ∪ e∈Ein ē is the required embedding.
Proof of Theorem 2. Let (P, J) be a solution for PDPC(G, s1 , t1 , . . . , sk , tk , `, F) with
|E(P )| minimal. Consider the embedding of G ∪ P in the sphere Σ0 , and let Q1 , . . . , Qk
be the paths of a DP solution in G ∪ P. By the minimality of |E(P )| we can assume that
S
the edges of P are exactly the edges of i∈{1,...,k} Qi that are not in G. For the same
reason, two edges in P have a common endpoint x that is not a terminal only if x is a
cut-vertex of ΓJ .
Let P ∗ denote the graph obtained from the dual of P ∪ ΓJ , after removing the
vertices corresponding to the faces of ΓJ that are disjoint from F. We first show that the
maximum degree of P ∗ is bounded by k. Assume, to the contrary, that P ∗ has a vertex
incident to two edges e∗1 and e∗2 such that e1 and e2 belong to the same path, say Qx ,
in {Q1 , . . . , Qk }. Then it is possible to choose an endpoint p1 of e1 and an endpoint p2
of e2 such that, (P 0 , J0 ) is also a solution such that |E(P 0 )| < |E(P )|. Indeed, p1 and
p2 are the vertices incident to e1 and e2 belonging to the two connected components of
Qx \ {e1 , e2 } that contain respectively sx and tx . Therefore we established that for every
i ∈ [k], no vertex of P ∗ is incident to two distinct edges of Qi , thus all vertices of P ∗
have degree at most k.
Here P 0 = P \ {e1 , e2 } ∪ {{p1 , p2 }} and J0 is defined such that ΓJ0 is obtained from
ΓJ after dissolving the vertices that became isolated during the construction of P 0 .
Our next aim is to prove that the diameter of P ∗ is bounded by 2k . Then |E(P ∗ )| =
k
|E(P )| ≤ k 2 and we are done.
Note that every edge in E(P ∗ ) corresponds to an
edge in exactly one path of Q1 , . . . , Qk . Hence, given a path R = (r0 , . . . , rζ ) in P ∗ , it
corresponds to a string w ∈ {Q1 , . . . , Qk }∗ in a natural way. It is enough to prove the
following claim.
Claim. The string w contains no infix y with |y| ≥ 2, such that every letter occurring
in y occurs an even number of times in y.

11

Proof of the Claim. Towards a contradiction, suppose that w contains such an infix
y. We may assume that w = y. Let ER ⊆ E(P ) be the set of edges corresponding to the
edges of the path R ⊆ P ∗ . Then |ER | ≥ 2 because w (and hence R) has length at least
2. Let B ⊆ Σ0 be the open set defined by the union of all edges in ER and all faces of
the graph P ∪ ΓJ that are incident to them. Clearly, B is an open connected subset of
F with the following properties:
(a) B contains all edges in ER and no other edges of P ,
(b) the ends of every edge in ER lie on the boundary ∂B, and
(c) every edge in E(P ) \ ER has empty intersection with B.
We consider an ‘up-and-down’ partition (U = {u1 , . . . , ur }, D = {d1 , . . . , dr }) of the
endpoints of the edges in ER as follows: traverse the path R in P ∗ in some arbitrary
direction and when the ith edge ei ∈ ER is met, the endpoint ui of ei on the left of this
direction is added to U and the right endpoint di is added to D. Notice that U and D
may be multisets because it is not necessary that all vertices in P have degree 1. For
each i ∈ {1, . . . , r} we say that ui is the counterpart of di and vice versa.
Because the paths Q1 , . . . , Qk are vertex-disjoint, the following holds.
Observation: If x ∈ V (P ) has degree larger than one, then either x is a terminal and
has degree at most k or x is a cutpoint of ΓJ and has degree exactly 2.
By assumption, every path Qi crosses R an even, say 2ni , number of times. Now
for every path Qi satisfying E(Qi ) ∩ ER 6= ∅, we number the edges in E(Qi ) ∩ ER
by ei1 , . . . , ei2ni in the order of their appearance when traversing Qi from si to ti and
we orient them from si to ti . We introduce shortcuts for Qi as follows: for every odd
number j ∈ {1, . . . , 2ni }, we replace the subpath of Qi from tail(eij ) to head(eij+1 ) by a
new edge fji in D (see Figure 3).
After having done this for all odd numbers j ∈ {1, . . . , 2ni }, we obtain a new path
0
Qi from si to ti that uses strictly less edges in B than Qi . Having replaced all paths
Qi with E(Qi ) ∩ ER 6= ∅ in this way by a new path Q0i , we obtain from P a new graph
P 0 by replacing every pair of edges eij , eij+1 ∈ E(P ) by fji for all i ∈ {1, . . . , k} with
0 the set of all
E(Qi ) ∩ ER 6= ∅, and for all j ∈ {1, . . . , 2ni }, j odd. We denote by ER
replacement edges fji . We also remove every vertex that becomes isolated in P 0 during
this operation.
Then it is easy to verify that:
• None of the edges of ER survives in E(P 0 ).
• |E(P 0 )| < |E(P )| .
12

Figure 3: Example of the transformation in the proof of the Claim in the proof of
Theorem 2; P is on the left and P 0 is shown on the right. The dashed lines represent
the edges of C.
• DP(G ∪ P 0 , s1 , t1 , . . . , sk , tk ) has a solution.
If we show that, for some suitable cactus set J0 of G, (P 0 , J0 ) is an F-patch, then we are
done, because |E(P 0 )| < |E(P )|. In what follows, we prove that P 0 can also be embedded
without crossings in clos(F) such that E(P 0 ) ⊆ Σ0 \ ∂F. For this it suffices to prove that
0 can be embedded in B without crossings.
the edges in ER
For every path Qi with E(Qi )∩ER 6= ∅ let Fji denote the subpath of Qi from head(eij )
to tail(eij+1 ), for j ∈ {1, . . . , 2ni }, j odd (this path may be edgeless only in the case where
head(eij ) = tail(eij+1 ) is a cut-vertex of ΓJ ). We replace Fji by a single edge cij (when
the corresponding path is edgeless, the edge cij is a loop outside B). We consider the
graph C with vertex set V (P ) and edge set {cij | i ∈ {1, . . . , k}, E(Qi ) ∩ ER 6= ∅, j ∈
{1, . . . , 2ni }, j odd}.
Our strategy consists of a two-step transformation of this embedding. The first step
creates an embedding of C inside clos(B) without moving the vertices. Indeed, notice
that C is embedded in Σ0 \ B without crossings such that all the endpoints of the edges
in C lie on the boundary of B. As for every odd j in [2ni ], j + 1 also belongs to [2ni ],
it follows that none of the endpoints of Fji can be a terminal. This, together with the
observation above, implies that no two edges of C have a common endpoint.
By applying Lemma 3 on the Σ0 -embedded outerplanar graph Γ = ΓJ ∪ C where B
plays the role of the face f , we obtain a new non-crossing embedding Γ0 . Notice that
Γ0 \ ΓJ is a new non-crossing embedding of C where all of its edges lie inside B. (Recall
that none of the edges of ER is present in this embedding.) This transformation maps
every edge cij to a new edge inside B with the same endpoints.
The second step “reflects” the resulting embedding along the axis defined by the
path R such that each vertex is exchanged with its counterpart. Now define (cij )0 so
13

that it connects tail(eij ) and head(eij+1 ) – these are exactly the counterparts of head(eij )
and tail(eij+1 ). Due to symmetry, the (cij )0 are pairwise non-crossing, and none of them
crosses a drawing of an edge in E(P ) \ ER . Hence the (cij )0 together with the drawing
of edges in E(P ) \ ER provide a planar drawing of P 0 (where (cij )0 is the drawing of fji ).
We finally define (up to isomorphism) the cactus set J0 of G such that ΓJ0 is obtained
from ΓJ after dissolving the vertices of P ∩ ΓJ that are isolated in P 0 . It is easy to verify
that (P 0 , J0 ) is an F-patch of G. This concludes the proof of the Claim.
Using the Claim above and from Lemma 2, it follows that |w| ≤ 2k , and hence the
diameter of P ∗ is bounded by 2k . The proof of Theorem 2 is now complete.
k

Let L be a list of all simple plane graphs with at most min{`, k 2 } edges and no
isolated vertices. We call a graph in L a completion. As a first step, our algorithm for
PDPC computes the list L. Obviously, the running time of this process is bounded by
a function depending only on k.

4

The algorithm for Planar-Dpc

The fact that the size of L is bounded by a function of k implies that PDPC is in XP.
Indeed, given the list L, for each completion P̃ ∈ L we define the graph QP̃ = (V (P̃ ), ∅)
and we consider all cactus sets J̃ of QP̃ where (P̃ , J̃) is a (Σ0 \ clos(J̃))-patch of QP̃
and V (J̃) = V (P̃ ). We denote the set of all such pairs (P̃ , J̃) by J and observe that the
number of its elements (up to topological isomorphism of the graph P̃ ∪ ΓJ̃ ) is bounded
by a function of k.
For each pair (P̃ , J̃) ∈ J , we check whether there exists an F-patch (P, J) of G such
that P̃ ∪ ΓJ̃ and P ∪ ΓJ are topologically isomorphic and DP has a solution in the graph
G∪P. As there are nz(k) ways to choose (P, J) and each check can be done in O(z1 (k)·n3 )
steps, we conclude that PDPC can be solved in nz2 (k) steps. In the remainder of the
paper, we will prove that the problem is actually in FPT.
The main bottleneck is that there are too many ways to identify V (J̃) with vertices
of V (F), because we cannot bound |V (F)| by a function of k. To overcome this, we
associate with a positive instance of PDPC a rooted topological minor (H̃, T̃ ) of the
original graph G, that witnesses the fact that (P̃ , J̃) corresponds to the desired F-patch
of G. For convenience, we assume from now on that Γint(Σ0 \F) does not contain any
loops or multiple edges. In other words, none of the open disks corresponding to the
connected components of Σ0 \ F contains less than 3 vertices in its boundary. If the
input instance violates this property we may enforce it by adding isolated vertices in G

14

Figure 4: In the leftmost image the dotted lines are the edges of P̃ . Together with the interior of
the grey areas they form a pair (P̃ , J̃) ∈ J . J̃ has two weakly connected components. V (J̃) consists of the 12 vertices on the boundary of the grey areas. The solid lines that intersect the open
set J̃ are the edges of the graph H̃, which is compatible with (P̃ , J̃). Let T̃ = {s1 , t1 , . . . , s4 , t4 }.
The triple τ = (J̃, H̃, T̃ ) ∈ H has two parts. The middle and the leftmost pictures show how
each of these parts is enhanced in order to construct the graphs Rτ1 and Rτ2 .

and modify F such that the new vertices belong to its boundary. Similarly, we restrict
J to contain only pairs (P̃ , J̃) where ΓJ̃ does not contain any loops or multiple edges.
Given a pair (P̃ , J̃) ∈ J , we say that a rooted simple graph (H̃, T̃ = {a1 , b1 , . . . ,
ak , bk }) embedded in Σ0 , is compatible with (P̃ , J̃) when
1. for every e ∈ E(H̃), e ⊆ J̃,
2. the vertices of H̃ that are also vertices of ΓJ̃ are |V (P̃ )|, while the vertices of H̃
that are not vertices of ΓJ̃ are all vertices of T̃ ,
3. V (H̃) \ T̃ ⊆ V (J̃) ⊆ V (H̃),
4. DP(P̃ ∪ H̃, a1 , b1 , . . . , ak , bk ) has a solution.
We define
H = {(J̃, H̃, T̃ ) | there exists a (P̃ , J̃) ∈ J
such that (H̃, T̃ ) is compatible with (P̃ , J̃)
and notice that |H| is bounded by some function of k. See the leftmost part of Fig. 4 for
an example of a triple in H.
Assuming that (P, J) is a solution for PDPC(G, s1 , t1 , . . . , sk , tk , `, F), consider the
parts of the corresponding disjoint paths that lie within G. The intuition behind the
15

definition above is that H̃ is a certificate of these “partial paths” in G. Clearly, the
number of these certificates is bounded by |H| and they can be enumerated in f0 (k)
steps, for some suitable function f0 . For example, for the solution depicted in Fig. 4,
H̃ consists of 7 disjoint edges, one for each subpath within G. Our task is to find an
FPT-algorithm that for every such certificate checks whether the corresponding partial
paths exist in G.
Given an open set O, a weakly connected component of O is the interior of some
connected component of the set clos(O). Notice that a weakly connected component is
not necessarily a connected set.
Let F̄1 , . . . , F̄λ be the weakly connected components of the set Σ0 \ clos(F). We call
such a component F̄i active if clos(F̄i ) ∩ T 6= ∅. We denote the collection of all active
components by FF . A crucial observation is that if an F-patch exists we can always
replace it by one that bypasses the inactive components.
Lemma 4. Let (G, s1 , t1 , . . . , sk , tk , F) be an instance for the PDPC problem and
S
S
let G0 = G[ F̄i ∈FF clos(F̄i ) ∩ V (G)] and F0 = Σ0 \ F̄i ∈FF clos(F̄i ). Then
(G0 , s1 , t1 , . . . , sk , tk , F0 ) is an equivalent instance.
Proof. For the non-trivial direction, we assume that G has an F-patch (P, J) such
that G ∪ P contains a collection {P1 , . . . , Pk } paths that certify the feasibility of DP(G ∪
S
P, s1 , t1 , . . . , sk , tk ). Let P 0 be the graph obtained if in ( i=1,...,k Pi )∩clos(F0 ) we dissolve
all vertices that are in F0 . Let also J0 be the union of all weakly connected components
of the set J that contain some open set from FF . Observe that (P 0 , J0 ) is an F0 -patch of
G0 .
By Lemma 4, we can assume from now on that the number λ of the weakly connected
components of the set Σ0 \ clos(F) is at most 2k. Also we restrict H so that it contains
only triples (J̃, H̃, T̃ ) such that the weakly connected components of the set J̃ are exactly
λ.

4.1

The enhancement operation

Consider the triple τ = (J̃, H̃, T̃ ) ∈ H. Let J̃1 , . . . , J̃λ be the weakly connected components of the set J̃. Then we define C̃ i = ΓJ̃i ∪ (clos(J̃i ) ∩ H̃) for i ∈ {1, . . . , λ} and
we call them parts of τ. Also we set T̃ i = T̃ ∩ V (C̃ i ), 1 ≤ i ≤ λ. We now apply the
following enhancement operation on each part of τ : For i = 1, . . . , λ, we consider the
sequence Rτ = (Rτ1 , . . . , Rτλ ) where Rτi is the rooted graph (Rτ0i , T̃ i ∪ {xinew }) such that
Rτ0i is defined as follows. Take the disjoint union of the graph C̃ i and a copy of the wheel
Wµ(J̃i ) with center xinew and add µ(J̃i ) edges, called i-external, between the vertices of
16

V (J̃i ) and the peripheral vertices of Wµ(J̃i ) such that the resulting graph remains Σ0 embedded and each vertex v ∈ V (J̃i ) is incident to µ(v) non-homotopic edges not in J̃.
As the graph ΓJ̃i is connected and planar, the construction of Rτ0i is possible. Observe
also that Rτ0i \ J̃i is unique up to topological isomorphism. To see this, it is enough to
verify that for every two vertices in Rτ0i \ J̃i of degree ≥ 3 there are always 3 disjoint
paths connecting them (here we use our assumption that ΓJ̃ does not contain any loops
or multiple edges).
We define R = {Rτ | τ ∈ H} and observe that |R| is bounded by a function of k
because the same holds for |H|. (For an example of the construction of Rτ , see Fig. 4)
We now define (C 1 , . . . , C λ ) such that C i = ΓF̄i ∪ (clos(F̄i ) ∩ G), i ∈ {1, . . . , λ}. We
call the graphs in (C 1 , . . . , C λ ) parts of G and let T i = T ∩ V (C i ), 1 ≤ i ≤ λ, where
T = {s1 , t1 , . . . , sk , tk }. As above we define the enhancement of the parts of G as follows.
0i
For each i = 1, . . . , λ we define the rooted graph G∗i = (G0i , T i ∪ {x∗i
new }) where G is
∗
defined as follows: take the disjoint union of C i and the wheel Wµ(
with center x∗i
new
F̄i )
i
i
and add µ(F̄ ) edges, called ∗i-external, between the vertices of V (F̄ ) and the peripheral
∗
vertices of Wµ(
such that the resulting graph remains Σ0 -embedded and each vertex
F̄i )
i
v ∈ V (F̄ ) is incident to µ(v) non-homotopic edges. As above, each G0i is possible to
construct and G0i \ F̄i is unique up to topological isomorphism.
The purpose of the above definitions is twofold. First, they help us to treat separately
each of the parts of G and try to match them with the correct parts of τ. Second, the
addition of the wheels to each part gives rise to a single, uniquely embeddable interface,
between the part and its “exterior” and this helps us to treat embeddings as abstract
graphs. Therefore, to check whether a part of τ is realizable within the corresponding
part of G, we can use the rooted version of the topological minor relation on graphs as
defined in Section 2.

4.2

The stretching lemma

A bijection ρ from T̃ = {a1 , b1 , . . . , ak , bk } to T = {s1 , t1 , . . . , sk , tk } is legal if for every
i ∈ {1, . . . , k}, there exists some j ∈ {1, . . . , k} such that ρ((ai , bi )) = (sj , tj ).
Let τ ∈ H and let ρ be a legal bijection from T̃ to T and let ρi be the restriction
of ρ in T̃i . We say that Rτ = (Rτ1 , . . . , Rτλ ) is ρ-realizable in G if there exists a bijection
φ : {1, . . . , λ} → {1, . . . , λ} such that for i = 1, . . . , λ, Rτi is a ρ̂i -rooted topological minor
∗φ(i)
of G∗φ(i) were ρ̂i = ρi ∪ {(xinew , xnew )}.
By enumerating all possible bijections φ, we enumerate all possible correspondences
between the parts of of G and the parts of τ. In order to simplify notation, we assume
in the remainder of this section that φ is the identity function.
The following lemma is crucial. It shows that when Rτi is a topological minor of G∗i
17

we can always assume that all vertices and edges of C̃ i are mapped via ψ0 and ψ1 to
vertices and paths in clos(F̄i ); the wheel Wµ(J̃i ) is mapped to a “sub-wheel” of Wµ(F̄i )
while i-external edges are mapped to ∗i-external edges. This will be useful in the proof
of Lemma 6, as the i-external edges represent the interface of the completion P̃ with
C̃ i . The topological minor relation certifies that the same interface is feasible between
the corresponding part C i of G and its “exterior”. Lemma 5 establishes also that the
image of ΓJ̃i can be “stretched” so that it falls on ΓF̄i . As all the vertices in V (F̄i ) are
∗i
within distance 2 from the artificial terminal x∗i
new in G , this allows us later in the
proof of Lemma 9 to locate within G∗i the possible images of V (Rτ0i ) in a neighborhood
of the terminals. It is then safe to look for an irrelevant vertex “far away” from this
neighborhood.
Lemma 5. Let Rτi be a ρ̂i -rooted topological minor of G∗i where ρ̂i = ρi ∪{(xinew , x∗i
new )},
i
i
for i = 1, . . . , λ. Let also ψ0 and ψ1 be the functions (cf. Section 2) certifying this topological minor relation. Then ψ0i and ψ1i can be modified so that the following properties
are satisfied.
1. if ẽ is an edge of the wheel Wµ(J̃i ) incident to xinew , then ψ1i (ẽ) is an edge incident
to x∗i
new .
2. if ẽ is an edge of the wheel Wµ(J̃i ) not incident to xinew , then ψ1i (ẽ) is an x∗i
new ∗
∗
avoiding path of Wµ(F̄i ) . Moreover, each edge in Wµ(F̄i ) is contained in a path
ψ i (f˜) for some edge f˜ of the cycle W ∗
\ xi .
1

µ(J̃i )

new

3. if ẽ is an i-external edge between V (J̃i ) and V (Wµ(J̃i ) ) \ {xinew }, then ψ1 (e) is a
path consisting of an ∗i-external edge between V (F̄i ) and V (Wµ(F̄i ) ) \ {x∗i
new }.
4. ψ0i (V (J̃i )) ⊆ V (F̄i ).
Proof. Our first step is to enforce Properties 1 and 2. For each edge ẽ = {xinew , x} of
Rτi , let ẽ0 = {x, x0 } be the unique edge of Rτi that is not an edge of Wµ(J̃i ) . Consider the
path Pẽ that is formed by the concatenation of ψ1i (ẽ0 ) and ψ1i (ẽ) and let x̂ be the neighbor
i
of ψ0i (xinew ) = x∗i
new in the path ψ1 (Pẽ ). For each such ẽ and its incident vertex x, we
simultaneously update ψ0i such that ψ0i (x) = x̂. Accordingly, for every ẽ = {xinew , x}
we simultaneously update ψ1i so that ψ1i ({xinew , x}) is the path consisting of the edge
i
0
i 0
{x∗i
new , x̂} (enforcing Property 1) and ψ1 (x, x ) is the subpath of Pẽ between x̂ and ψ0 (x ).
We also update ψ1i such that for each ẽ1 = {xinew , x1 } and ẽ2 = {xinew , x2 } where x1 and
∗
x2 are adjacent, we set ψ1i ({x1 , x2 }) to be the (x̂1 , x̂2 )-path of Wµ(
that does not meet
F̄i )
i
any other vertex of ψ0 (V (Wµ(J̃i ) )), enforcing Property 2.

18

So far, we have enforced that for each i ∈ {1, . . . , λ}, the wheel Wµ(F̄i ) is mapped
via ψ0i and ψ1i to the wheel Wµ(J̃i ) (by slightly abusing the notation, we can say that
ψ1 (Wµ(J̃i ) ) = Wµ(F̄i ) ). Notice that Properties 1 and 2 imply that all vertices and edges
of C̃ i are mapped via ψ0 and ψ1 to vertices and paths of clos(F̄i ).
Our second step is to enforce Properties 3 and 4. The transformation that we describe
next, essentially “stretches” the image of J̃i until it hits from within the boundary of
F̄i . Let ẽ = {x, x0 } be an edge of Rτi where x ∈ V (J̃i ) and x0 ∈ V (Wµ(J̃i ) ) \ {xinew }.
We also set Pẽ = ψ1i (ẽ). By definition, Pẽ is a path in G∗i which starts from ψ0i (x) and
ends at ψ0i (x0 ). As ψ0i (x) is a point of clos(F̄i ) and ψ0i (x0 ) is not, we can define x̂ as the
first vertex of Pẽ that is a vertex of V (F̄i ). For each such ẽ and its incident vertex x,
we simultaneously update ψ0i such that ψ0i (x) = x̂. Accordingly, for every ẽ = {x, x0 } we
simultaneously update ψ1i so that ψ1i ({x, x0 }) is the path consisting of the single edge
{x̂, ψ0i (x0 )} – thus enforcing Property 3 – and for each edge {x1 , x2 } of ΓJ̃i we update ψ1i
so that ψ1i ({x1 , x2 }) is a (x̂1 , x̂2 )-path avoiding any other vertex of ψ0i (V (J̃i )). As now
all images of the vertices and the edges of ΓJ̃i lie on ΓF̄i , Property 4 holds.

4.3

Reducing PDPC to topological minor testing

Lemma 6. PDPC(G, t1 , s1 , . . . , tk , sk , `, F) has a solution if and only if there exists a
τ = (J̃, H̃, T̃ ) ∈ H and a legal bijection ρ : T̃ → T such that Rτ is ρ-realizable in G.
Proof. Suppose that (P, J) is a solution for PDPC(G, t1 , s1 , . . . , tk , sk , `, F) giving rise
to a collection P = {P1 , . . . , Pk } of disjoint paths in G ∪ P where Pi connects si with ti .
From Theorem 2, we can assume that |V (J)| is bounded by a suitable function of k
and therefore, (P, J) is isomorphic to a member (P̃ , J̃) of J , in the sense that P̃ ∪ ΓJ̃
and P ∪ ΓJ are topologically isomorphic. Let (H, T ) be the rooted subgraph of G formed
by the edges of the paths in P that are also edges of G. We now define the rooted
graph (H 0 , T ) by dissolving all non-terminal vertices in the interior of J and observe
that (H 0 , T ) is isomorphic, with respect to some bijection ω, to some (H̃, T̃ ) that is
compatible with (P̃ , J̃). Therefore τ = (J̃, H̃, T̃ ) ∈ H and let ρ be the correspondence
between T̃ and T , induced by ω. By partitioning ω with respect to the weakly connected
components of the set J̃, we generate a bijection φ between the parts {C̃ 1 , . . . , C̃ λ } of τ
and the parts {C 1 , . . . , C λ } of G such that a subdivision of C̃ i is topologically isomorphic
to a subgraph of C φ(i) , i ∈ {1, . . . , λ}. This topological isomorphism can be extended in
the obvious manner to the graphs obtained after the enhancement operation applied to
the parts of τ and the parts of G. This translates to the fact that each of the resulting Rτi
is a ρi -rooted topological minor of G∗φ(i) where each ρi is obtained by the restriction of

19

ρ to the vertices of V (Rτi ) plus the pair (xinew , x∗i
new ). We conclude that Rτ is ρ-realizable
in G.
For the opposite direction, let τ ∈ H. By renumbering if necessary the parts of G, let
be a ρ̂i -rooted topological minor of G∗i were ρ̂i = ρi ∪ {(xinew , x∗i
new )}, for i = 1, . . . , λ.
i
i
Let also ψ0 and ψ1 be the functions satisfying the four properties of Lemma 5.
Rτi

+
when H̃ + is the leftmost graph of Figure 4.
Figure 5: The graph H̃K

For the given τ = (J̃, H̃, T̃ ) ∈ H we assume w.l.o.g. that |V (J̃)| is minimal. Recall
that there exists a P̃ such that (H̃, T̃ ) is compatible with (P̃ , J̃). Let H̃ + = H̃ ∪ ΓJ̃ ∪ P̃ .
From Lemma 1, there exists a curve K where K ⊆ Σ0 \ clos(J̃) and such that K
intersects each edge of P̃ twice. Let ∆in and ∆out be the two connected components
of the set Σ0 \ K and w.l.o.g. we may assume that clos(J̃) ⊆ ∆out . If we consider all
connected components of the set K \ H̃ + as edges and take their union with the graph
obtained by H̃ + after subdividing the edges of P̃ at the points of K ∩ H̃ + , we create
+
+
+
∩ ∆in
= H̃K
a new graph H̃K
(see Figure 5 for an example). We also define H̃K,in
+(i)

+
+
and H̃K,out
= H̃K
∩ clos(∆out ). For i ∈ {1, . . . , λ}, we define H̃K,out as follows: first
+
take the graph obtained by H̃K,out
if we remove all edges except those that have at
least one endpoint in C̃ i and those that belong in K and, second, dissolve in this graph
all vertices that have degree 2. If we now add a new vertex xinew ∈ ∆in and make it
adjacent to all remaining vertices in K, it follows, by the minimality of the choice of τ ,
that the resulting graph is isomorphic to Rτi . In the above construction, we considered
+
the vertex set Q = K ∩ H̃ + ⊆ V (HK
) and we slightly abuse notation by denoting by Q
i
also its counterpart in Rτ . We also denote by πQ the cyclic ordering of Q defined by the

20

order of appearance of the vertices in Q along K. Similarly, for i ∈ {1, . . . , λ}, we set
+(i)
Qi = Q ∩ V (H̃K,out ) and we denote by πQi the induced sub-ordering of πQ . We denote by
Ẽ i = {ẽi1 , . . . , ẽiµ(J̃i ) , ẽi1 } the edges of Rτi , not in Wµ(J̃i ) , that are incident to the vertices
of Qi , cyclically ordered according to πQi .
We now take the graph G∗i and remove from it all edges outside clos(F̄i ) except from
the images of the edges of Ẽ i (observe that clos(F̄i ) is always a connected set while this
is not necessarily the case for F̄i ). From Property 3 in Lemma 5, these images are just
∗i−
edges between V (F̄i ) and V (Wµ(F̄i ) ) \ {x∗i
new }. We denote the resulting graph by G
and observe that it can be drawn in Σ0 in a way that the vertices in ψ0 (Qi ) lie on a
virtual closed curve in accordance with the cyclic ordering πQi of their ψ0i -preimages.
We consider the disjoint union G∗out of all G∗i− and we observe that it is possible to
S
embed it in Σ0 such that all vertices in Q∗ = i∈{1,...,λ} ψ0i (Qi ) lie on the same closed
curve K ∗ . By the way each πQi is defined from πQ and the bijection between Q and
Q∗ we directly obtain that the following properties are satisfied: (i) the new embedding
is planar, (ii) G∗out is a subset of one of the connected components of the set Σ0 ∩ K ∗ ,
(iii) for all i ∈ {1, . . . , λ}, the cyclic ordering of ψ0i (Qi ) is an induced sub-ordering of
the cyclic ordering defined by the way the vertices of Q∗ are being arranged along K ∗ .
S
Note that ψ0 = i∈{1,...,λ} ψ0i defines a bijection from the vertices of Q to the vertices of
+
and renaming each vertex
Q∗ . Our next step is to obtain the graph G∗in by taking H̃K,in
+
∗
∗
x ∈ Q to ψ0 (x). Now the graph G = Gin ∪ Gout consists of the original graph G and a
collection Z of paths of length 3.
We are now ready to define the desired F-patch (P, J) of G. The edges of P are
created by dissolving all internal vertices of each path in Z. Also, J can be any cactus
set for which the embedding of ΓJ results from the embedding of ΓF after dissolving all
vertices of V (F) that are not in ψ0 (V (J̃)).
In [13], Grohe, Kawarabayashi, Marx, and Wollan gave an h1 (k) · n3 algorithm for
checking rooted topological minor testing, where h1 is some computable function. Combining their algorithm with Lemma 6, we obtain an h2 (k)·n3 algorithm for PDPC (here,
again, h2 is some computable function). Therefore, PDPC ∈ FPT.
In the next section, we show how to obtain the improved running time claimed in
Theorem 1.

5

Applying the irrelevant vertex technique

Lemma 6 established that for every candidate patch P̃ , certifying its feasibility for PDPC
on G reduces to finding a rooted topological minor. By the results of [10], PDPC is in
FPT by an h2 (k) · n3 algorithm. In this section we show that this running time can be
21

improved. We first explain the intuition behind this improvement.

5.1

Proof strategy

At a high level, we have reduced the validity of P̃ to the problem of determining whether
a q-vertex rooted graph H is a rooted topological minor of an n-vertex graph G, where
q is bounded by some function of k. By Lemma 5, we can assume that the images of
the vertices of H are either terminals of G or lie on the boundary of the same face of G.
This observation makes it possible to directly employ, in Lemma 9, the irrelevant vertex
technique [19].
In particular, if the treewidth of G is big enough, one can detect a sufficiently large
set of concentric cycles that are away from the images of the vertices of H in G; this
is possible due to Lemma 5. Using the “vital linkage” theorem of Robertson and Seymour [18, 17] (see also [13]), we obtain that the topological minor mapping can be
updated so that the realization of H avoids the inner cycle of this collection. Therefore,
the removal of any of the vertices of this cycle creates an equivalent instance of the
problem with a smaller number of vertices. By repeating this vertex-removal operation,
we end up with a graph whose treewidth is bounded by some function of q. In this
case, since the rooted variant of the topological minor checking problem is definable in
Monadic Second Order Logic (msol) (see Lemma 10 in the Appendix), the problem can
be solved in a linear number of steps according to Courcelle’s Theorem.
For the running time of our algorithm, we use the fact that the detection of an
irrelevant vertex in planar graphs requires to find a vertex that is “far enough” from all
the terminals. As this can be done by standard BFS in O(n) steps and at most n such
vertices are deleted, the overall complexity of the algorithm is f (k) · n2 .

5.2

Treewidth and linkages

Let G be a graph. A linkage in G is a set of pairwise disjoint paths of it. The endpoints
of a linkage L are the endpoints of the paths in L. The pattern of L is defined as
π(L) = {{s, t} | L contains a path from s to t}
Consider now the rooted graph G = (G0 , T ) where G0 is a Σ0 -embedded graph. We
call a cycle of G0 T -respectful if all the vertices of T are inside one of the two connected
components of the set Σ0 \ C. Given a T -respectful cycle C of G0 we denote by ∆ext (C)
the connected component of the set Σ0 \ C that contains T and by ∆int (C) the other.
A sequence C1 , . . . , Ck of T -respectful cycles in G is T -concentric if ∆ext (C1 ) ⊆ · · · ⊆
∆ext (Ck ).
22

Figure 6: The leftmost graph is Γ6 . The insulation of x in the rightmost graph is equal
to 2 (the terminals are the blue vertices).
Let Γk (k ≥ 2) be the graph obtained from the (k × k)-grid by triangulating internal
faces of the (k × k)-grid such that all internal vertices become of degree 6, all non-corner
external vertices are of degree 4, and then one corner of degree two is joined by edges –
we call them external – with all vertices of the external face (the corners are the vertices
that in the underlying grid have degree two). Graph Γ6 is shown in Fig. 6.(i). We also
define the graph Γ∗k as the graph obtained from Γk if we remove all its external edges.
In Γ∗k we call all vertices incident to its unique non-triangle face perimetric.
Let G = (G0 , T ) be a rooted Σ0 -embedded graph. Given x ∈ V (G0 ) we define the
insulation between x and T , denoted insT (x) as the maximum length of a sequence of
S
T -concentric cycles C1 , . . . , Cl in G such that (i) {x} ∩ i∈{1,...,l} Ci = ∅ and (ii) every
line of Σ0 connecting x and some vertex of T meets every Ci , i ∈ {1, . . . , l} For an
example, see Figure 6.(ii). We define the planar thickness of a rooted graph G = (G0 , T )
as follows:
pthT (G) = max{insT (x) | x ∈ V (G0 )}.
It is easy to verify that pth is closed under contractions. In other words, the following
holds.
Lemma 7. Let G1 = (G01 , T1 ) and G2 = (G02 , T2 ) be two rooted graphs where G01 is a
σ-contraction of G02 and T1 = σ(T2 ). Then pthT1 (G1 ) ≤ pthT2 (G2 ).
According to the following lemma, if the treewidth of G is big enough then every
constant radius ball around T is sufficiently insulated from some vertex of G.

23

Lemma 8. Let G = (G0 , T ) be a rooted plane graph where tw(G0 ) ≥ 24 · (2l + 2r +
p
S
2)(d |T | + 1e) + 49. Let also T 0 = t∈T NGr 0 (t). Then pthT 0 (G) ≥ l.
Proof. By using [7, Lemma 6], the graph G0 contains as a σ-contraction the graph
H 0 = Γ(2l+2r+2)(d√|T |+1e) . Define the rooted graph H = (H 0 , TH ) where TH = σ(T ). We
consider a vertex packing of H 0 in |T | + 1 copies of Γ∗2l+2r+2 . By the pigeonhole principle
and the fact that |TH | ≤ |T |, one, say Z, of these copies does not contain any vertex in
r (T ).
TH . By Observation 1, contractions do not increase distances, hence σ(T 0 ) ⊆ NH
0
H
0
∗
Let Z be the subgraph of Z that is isomorphic to Γ2l+2 whose vertices have distance
at least r from the perimetric vertices of Z and therefore are also at distance strictly
greater than r from TH . We conclude that V (Z 0 ) ∩ σ(T 0 ) = ∅. Notice that Z 0 contains
l + 1 σ(T 0 )-concentric cycles C1 , . . . , Cl , Cl+1 that are also σ(T 0 )-concentric cycles of H.
Let x ∈ Cl+1 . Then the cycles C1 , . . . , Cl certify that insσ(T 0 ) (x) ≥ l. Therefore
pthσ(T 0 ) (H 0 ) ≥ l. By Lemma 7, we conclude that pthT 0 (G) ≥ l.
We need the following theorem from [17]. We present it using the terminology of [5].
Proposition 1. There is a computable function
Γ be a Σ0 -embedded plane graph, L be a linkage
in the pairs of π(L). Let also C1 , . . . , Cg(|π(L)|) be
is a linkage L0 with the same pattern as L such
∆ext (Cg(|π(L)|) ).

5.3

g such that the following holds: Let
of Γ and let T be the set of vertices
T -concentric cycles of Γ. Then there
that all paths in L are contained in

The algorithm

Using Lemmata 5, 7, 8, and Proposition 1, we can prove the following result.
Lemma 9. There is an FPTalgorithm, running in f2 (k) · n2 , for some function f2 ,
that given a τ = (J̃, H̃, T̃ ) ∈ H and a legal bijection ρ : T̃ → T, checks whether Rτ is
ρ-realizable in G.
Proof. As the number of bijections φ : {1, . . . , λ} → {1, . . . , λ} is bounded by a function
of k it is enough to show how to check in FPT time whether, for i = 1, . . . , λ, Rτi is a ρˆi rooted topological minor of G∗φ(i) were ρ̂i = ρi ∪ {(xinew , x∗i
new )}. To simplify notation, we
∗φ(i)
i
0i
i
i
drop indices and we denote Rτ = (Rτ , T̃ ∪ {xnew }) and G∗φ(i) = (G0φ(i) , T φ(i) ∪ {xnew })
by R = (R0 , T̃ ∪ {xnew }) and G∗ = (G0 , T ∪ {x∗new }) respectively. We also use ρ̂ instead
of ρ̂i and xnew instead of xinew .
We now apply the irrelevant vertex technique, introduced in [19] as follows. Using
the algorithm from [2] (or, alternatively, the one from [15]) one can either compute a
p
tree-decomposition of G0 of width at most q = 4 · (24 · (2 · g(|E(R0 )|) + 8)( |T | + 2) + 49)
or prove that no tree decomposition exists with width less than q/4. In the case where
24

tw(G0 ) ≤ q, we recall that |E(R0 )| is a function of k and |T | ≤ 2k. Consequently, there
exists a function f3 such that tw(G0 ) ≤ f3 (k) and the result follows from Lemma 10 in
the Appendix.
p
Suppose now that tw(G0 ) ≥ q/4 = 24 · (2 · g(|E(R0 )|) + 8)( |T | + 2) + 49. Applying
Lemma 8 for r = 3 we have that pthT 0 (G∗ ) ≥ g(|E(R0 )|) where T 0 = NG3 0 (T ∪ {x∗new }).
We now prove that there is a vertex x ∈ V (G∗ ) such that if R is a ρ̂-rooted topological
minor of G∗ then R is a ρ̂-rooted topological minor of G∗ \ {x}. Let ψ0 and ψ1 be the
functions certifying that R is a ρ̂-rooted topological minor of G∗ . We apply on ψ0 and
ψ1 the modifications of the Lemma 5 so that they satisfy Properties 1–4. An important
consequence is that the images of all vertices of R under ψ0 are close to terminals
in T. Indeed, from Properties 1 and 2, all neighbors of xnew are mapped via ψ0 to
vertices that belong in NG1 0 (x∗new ). Moreover, from Properties 3 and 4 it follows that
ψ0 (V (J̃)) ⊆ V (F) ⊆ NG2 0 (x∗new ). So far we have proved that all vertices of R, except
those inside J̃, are mapped via ψ0 to vertices in NG2 0 (x∗new ). As all vertices of R that are
inside J̃ belong to T̃ , it follows that ψ0 (V (R)) ⊆ T 0 .
The set L = {ψ1 (e) | e ∈ E(R)} is a set of paths in G∗ . Let L1 ⊆ L be the set of those
paths that have length at most 2 and define L2 = L \ L1 . For each path Q ∈ L2 define its
interior, denoted int(Q), as the subpath of Q consisting of all vertices of I(Q). Clearly,
L = {int(Q) | Q ∈ L2 } is a linkage in G∗ and π(L) ⊆ T 0 . Consider the collection C of
T 0 -concentric cycles C1 , . . . , Cg(|E(R0 )|) certifying the fact that pthT 0 (G∗ ) ≥ g(|E(R0 )|).
S

Define the graph Γ = (clos(∆in (C1 )) ∩ G∗ ) ∪
Q∈L2 int(Q) . We have that (i) L is a
linkage of Γ, and (ii) |E(R0 )| ≥ |π(L)|. Let x be a vertex of Cg(|π(L)|) . By Proposition 1
there is another linkage L0 with the same pattern as L such that all paths in L0 avoid x.
The vertices of all paths in L1 belong to T 0 since they are at distance at most 3 from
T ∪ x∗ new . The endpoints of all paths in L2 also belong T 0 since they are at distance
at most 2 from T ∪ x∗ new . Therefore all paths in L1 and the endpoints of all paths in
L2 avoid Γ altogether. We now show that all paths in L can be rerouted so that they
avoid x, while they remain internally vertex-disjoint. The paths in L1 stay the same.
For the paths in L2 , we only have to reroute their interiors within Γ. This is achieved by
connecting the pairs in π(L) via the linkage L0 . After this substitution all paths in the
updated set L avoid x. By updating ψ1 to reflect the new interiors of the paths in L2 ,
we obtain that R is a ρ̂-rooted topological minor of G∗ \ {x}.
Notice that x can be found in linear time applying BFS starting from T 0 . After deleting x, we create an equivalent instance of the problem with smaller size. By recursively
applying the same reduction to the new instance at most |V (G0 )| times, at some point
the treewidth will drop below q and then we solve the problem by applying Lemma 10
in the Appendix as above.

25

From Lemmata 6 and 9 we obtain Theorem 1.

6

Further extensions and open problems

We chose to tackle the disjoint-paths completion problem with the topological restriction
of having non-crossing patch edges. A natural extension of this problem is to allow a
fixed number ξ > 0 of crossings in the patch. We believe that, using the same techniques,
one may devise an f (k) · n2 algorithm for this problem as well. The only substantial
difference is a generalization of our combinatorial result (Theorem 2) under the presence
of crossings.
An interesting topic for future work is to define and solve the disjoint-paths completion problem for graphs embedded in surfaces of higher genus. A necessary step in
this direction is to extend Theorem 2 for the case where the face to be patched contains
handles.
Another issue is to extend the whole approach for the case where the faces to be
patched are more than one. This aim can be achieved without significant deviation from
our methodology, in case the number of these faces is bounded. However, when this
restriction does not apply, the problem seems challenging and, in our opinion, it is not
even clear whether it belongs to FPT.
Acknowledgement. We wish to thank the anonymous reviewers of an earlier version
of this paper for valuable comments and suggestions.

References
[1] I. Adler, S. G. Kolliopoulos, P. K. Krause, D. Lokshtanov, S. Saurabh,
and D. M. Thilikos, Tight bounds for linkages in planar graphs, in Proceedings
of the 38th International Colloquium on Automata, Languages and Programming
(ICALP 2011), 2011.
[2] E. Amir, Efficient approximation for triangulation of minimum treewidth, in Uncertainty in Artificial Intelligence: Proc. of the Seventeenth Conference (UAI-2001),
San Francisco, CA, Morgan Kaufmann Publishers, 2001, pp. 7–15.
[3] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of
finite graphs, Information and Computation, 85 (1990), pp. 12–75.
[4] B. Courcelle and M. Mosbah, Monadic second-order evaluations on treedecomposable graphs, Theoretical Computer Science, 109 (1993), pp. 49–82.
26

[5] A. Dawar, M. Grohe, and S. Kreutzer, Locally excluding a minor, in Proc.
of the 21st IEEE Symposium on Logic in Computer Science (LICS’07), New York,
2007, IEEE, pp. 270–279.
[6] R. Diestel, Graph theory, vol. 173 of Graduate Texts in Mathematics, SpringerVerlag, Berlin, third ed., 2005.
[7] F. V. Fomin, P. Golovach, and D. M. Thilikos, Contraction bidimensionality:
the accurate picture, in 17th Annual European Symposium on Algorithms (ESA
’09), Lecture Notes in Computer Science, Springer Verlag, 2009, pp. 706–717.
[8] M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the
Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
[9] M. C. Golumbic, H. Kaplan, and R. Shamir, On the complexity of DNA
physical mapping, Adv. in Appl. Math., 15 (1994), pp. 251–261.
[10] M. Grohe, K. Kawarabayashi, D. Marx, and P. Wollan, Finding topological subgraphs is fixed-parameter tractable, in 43rd ACM Symposium on Theory of
Computing (STOC 2011), San Jose, California, June 6-8 2011.
[11] P. Heggernes, C. Paul, J. A. Telle, and Y. Villanger, Interval completion
with few edges, in Proceedings of the 39th Annual ACM Symposium on the Theory
of Computing (STOC 2007), San Diego, California, American Mathematical Society,
2007, pp. 374–381.
[12] H. Kaplan, R. Shamir, and R. E. Tarjan, Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs, SIAM
Journal on Computing, 28 (1999), pp. 1906–1922.
[13] K. Kawarabayashi and P. Wollan, A shorter proof of the graph minor algorithm - the unique linkage theorem, in Proc. of the 42nd annual ACM Symposium
on Theory of Computing (STOC 2010), 2010.
[14] M. R. Kramer and J. van Leeuven, The complexity of wire-routing and finding
minimum area layouts for arbitrary VLSI circuits, Advances in Comp. Research, 2
(1984), pp. 129–146.
[15] B. A. Reed, Finding approximate separators and computing tree width quickly,
in Proc. of the Twenty-fourth annual ACM Symposium on Theory of Computing,
ACM Press, 1992, pp. 221–228.

27

[16] B. A. Reed, N. Robertson, A. Schrijver, and P. D. Seymour, Finding
disjoint trees in planar graphs in linear time, in Graph structure theory (Seattle,
WA, 1991), vol. 147 of Contemp. Math., Amer. Math. Soc., Providence, RI, 1993,
pp. 295–301.
[17] N. Robertson and P. Seymour, Graph minors. XXII. Irrelevant vertices in
linkage problems, preprint, 1992.
[18] N. Robertson and P. Seymour, Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory Ser. B, 99 (2009), pp. 583–616.
[19] N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths
problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65–110.
[20] M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2 (1981), pp. 77–79.

28

Appendix
A.1 MSOL and rooted topological minors
In this section we define a parameterized version of Rooted Topological Minor Testing
that uses treewidth as a parameter and we show, using Monadic Second Order Logic
(msol), that it is in FPT. The corresponding algorithm will be used as a subroutine in
the proof of Theorem 1.
p-Bounded Treewidth Rooted Topological Minor Testing
Input: a rooted graph (H, SH ), a rooted graph (H, SG ), and a
bijection ρ : SH → SG .
Parameter: k = tw(G) + |V (H)|
Question: is (H, SH ) is a ρ-rooted topological minor of the rooted
graph (G, SG )?
Lemma 10. p-Bounded Treewidth Rooted Topological Minor Testing can
be solved in f (k) · |V (G)| steps.
Proof. Let SH = {a1 , . . . , as }, let V (H)\SH = {u1 , . . . , ut }, and let E(H) = {e1 , . . . , e }.
Let τs = {VERT, EDGE, I, c1 , . . . cs } be the vocabulary of graphs (as incidence structures) with s constants. We give an msol[τs ] formula φH,SH such that for every graph
G with SG = {b1 , . . . , bn } and ρ(ai ) = bi we have that (G, b1 , . . . , bs ) |= φH,SH ⇐⇒
(H, SH ) is a ρ-rooted topological minor of (G, SG ).
Let path(x, y, Z) be the msol[τs ] formula stating that Z is a path from x to y. (This
can be easily done by saying that Z is a set of edges with the property that for every
vertex v incident to an edge in Z, the vertex v is either incident to precisely two edges
in Z, or v is incident to one edge in Z and v = x or v = y. Finally, we can express that
the path Z is connected.)

29

Let
φH,SH :=∃Z1 . . . Z ∃x1 . . . xt
^
xi 6= xj ∧

^

path(xk , c` , Zi ) ∧

ei ={uk ,a` }
xk ∈V (H)\SH
a` ∈SH

^

path(xk , x` , Zi ) ∧

ei ={uk ,u` }⊆V (H)\SH

i6=j;i,j≤t

^

^

path(ck , c` , Zi ) ∧

ei ={ak ,a` }⊆SH

∃y (VERTy ∧ ‘y is incident to an edge in Zi

i6=j; i,j≤

and to an edge in Zj ’)
→(

s
_

i=1

y = ci ∨

t
_


y = xi ) .

i=1

The constants ci are interpreted by the bi , hence they make sure that ai is mapped to
bi , and Condition 1 of rooted topological minors is satisfied. In addition we make sure
that every edge of H is mapped to a path in G. Finally we make sure that Condition 3
is satisfied. (The statement ‘x is incident to an edge in Zi and to an edge in Zj ’ can be
easily expressed in msol.)
Observe that the length of the formula φH,SH only depends on H. Hence by Courcelle’s Theorem [3, 4] there is a computable function f1 such that p-Bounded Treewidth
Rooted Topological Minor Testing can be solved in time f1 (tw(G) + |V (H)|) ·
|V (G)|.

30

