FPT algorithms for embedding into low complexity graphic
metrics
Arijit Ghosh

∗

Sudeshna Kolay

†

Gopinath Mishra

∗

arXiv:1801.03253v2 [cs.CG] 17 Jan 2018

January 18, 2018

Abstract
Given metric spaces (X, DX ) and (Y, DY ), an embedding F : X → Y is an injective
mapping from X to Y . Expansion eF and contraction cF of an embedding F : X → Y are
defined as
eF =

max

x1 ,x2 (6=x1 )∈X

DX (x1 , x2 )
DY (F (x1 ), F (x2 ))
and cF =
max
,
DX (x1 , x2 )
x1 ,x2 (6=x1 )∈X DY (F (x1 ), F (x2 ))

respectively and distortion dF is defined as dF = eF ·cF . Observe that dF ≥ 1. An embedding
F : X → Y is non-contracting if cF ≤ 1. When d = 1, then F is isometry.
The Metric Embedding problem takes as input two metric spaces (X, DX ) and (Y, DY ),
and a positive integer d. The objective is to determine whether there is an embedding
F : X → Y such that dF ≤ d. Such an embedding is called a distortion d embedding. The
bijective Metric Embedding problem is a special case of the Metric Embedding problem
where |X| = |Y |. In parameterized complexity, the Metric Embedding problem, in full
generality, is known to be W-hard and therefore, not expected to have an FPT algorithm.
In this paper, we consider the Gen-Graph Metric Embedding problem, where the two
metric spaces are graph metrics. We explore the extent of tractability of the problem in
the parameterized complexity setting. We determine whether an unweighted graph metric
(G, DG ) can be embedded, or bijectively embedded, into another unweighted graph metric
(H, DH ), where the graph H has low structural complexity. For example, H is a cycle, or H
has bounded treewidth or bounded connected treewidth. The parameters for the algorithms
are chosen from the upper bound d on distortion, bound ∆ on the maximum degree of H,
treewidth α of H, and the connected treewidth αc of H.
Our general approach to these problems can be summarized as trying to understand
the behavior of the shortest paths in G under a low distortion embedding into H, and the
structural relation the mapping of these paths has to shortest paths in H.

Keywords. Metric spaces, metric embedding, FPT, low distortion embeddings, and dynamic programming

1

Introduction

Let (X, DX ) and (Y, DY ) be two metric spaces. A small distortion embedding F : X → Y of
a metric space (X, DX ) into a metric space (Y, DY ) essentially means that distances in the metric
space (F (X), DY ) have similar lengths as the corresponding distances in (X, DX ). Therefore,
an algorithmic problem in (X, DX ) could, in principle, be solved (or approximated) by solving a similar problem in (F (X), DY ). Therefore, there is an interest in finding an efficient
way to compute a low distortion embedding of (X, DX ) into (Y, DY ). This simple insight has
been used extensively to design fast algorithms for many classical problems in computer science.
∗
†

Indian Statistical Institute, Kolkata, India.
Eindhoven University of Technology, Netherlands.

1

The central idea is, given an input metric space (X, DX ), we find an efficient small distortion
embedding of (X, DX ) into a simpler metric space whose structure is well understood. For
example, the metric space into which we intend to embed (X, DX ) could be a simple graphic
metric like a path or a tree, or well-studied metric spaces like a Euclidean space etc. Examples of problems where this strategy has been successfully implemented include problems like
Sparsest Cut, Approximate Nearest Neighbor Search, Clustering, Multicommodity Flow, Multicut, Low Diameter Decomposition, Small Balanced Separators
etc. (See [LLR95, Ind01, GNRS04, ABN11, Mat13]).
The problem of finding a low distortion embedding of a metric space into a simple metric
space has been extensively studied both in Mathematics and Computer Science. For example,
any metric space with n points can be isometrically embedded into ℓn∞ [LLR95]. In [LLR95],
Linial et al. showed that any unweighted n vertex tree with l leaves can be isometrically embedO(log l)
ded into ℓ∞
. Bourgain [Bou85] showed that any metric space on n points can be embedded
into ℓp with distortion O(log n). Johnson and Lindenstrauss [JL84] showed that any n points can
O (log2 n/ǫ2 )
be embedded into ℓ2
with distortion at most (1+ǫ). Bartal [Bar96] and Fakcharoenphol
et al. [FRT03] showed that any metric space on n points can be embedded into a distribution
of trees with expected distortion O(log n).

1.1

Embedding into low complexity graphs

The need for getting small distortion embeddings into simpler spaces naturally led to the
question of finding minimum distortion embedding of (X, DX ) into (Y, DY ) when both the
metric spaces come from shortest path metrics on graphs with positive weights, and (Y, DY ) has
a simple topology like paths, cycles, trees etc. Kenyon et al. [KRS10] showed that this problem
is APX-hard even when both the graphs are unweighted, have the same number of vertices,
and one of the graphs is a simple wheel graph. Kenyon et al.’s [KRS10] result implies that the
problem is APX-hard even when we are looking for a bijective embedding and both the graphs
are unweighted. Badoiu et al. [BDG+ 05] also proved APX-hardness when both the graphs are
unweighted and (Y, DY ) is the metric space of a path. Badoiu et al. [BCIS05] showed that
computing the minimum distortion is hard to approximate up to a factor polynomial in |X|,
even when (X, DX ) is a weighted tree with polynomial spread and (Y, DY ) is a path. Fellows et
al. [FFL+ 13] showed that the problem of embedding a weighted graph metric into a path with
distortion at most d > 2 is NP-complete.
Badoiu et al. [BDG+ 05] gave the first algorithm for deciding if an unweighted graph metric
has a non-contracting embedding into a path with distortion d. The running time of their
algorithm was n4d+2 · dO(1) , where n denotes the number of vertices in the graph. The study
of small distortion embeddings through the lens of Parameterized Complexity [CFK+ ] started
with the work of Fellows et al. [FFL+ 13]. They
 gave the first fixed parameter tractable(FPT)
algorithm with running time O n d4 (2d + 1)2d for finding a non-contracting embedding of an
n vertex unweighted graph metric into a path with distortion at most d (d is the parameter of
the algorithm). Fellows et al. [FFL+ 13] also showed that their FPT algorithm can be extended
to get an FPT algorithm for the case of non-contracting embeddings for weighted graphs into
paths, where the parameters to the algorithm are both the distortion and the maximum weight
of an edge in the graph. Nayyeri et al. [NR15] gave improved exact algorithms for embedding
weighted path metrics into weighted paths.
Results for embedding into paths have been extended to the case of trees. Kenyon et al.
[KRS10] gave the first FPT algorithm for finding a bijective embedding f of an unweighted

graph metric on n vertices into a tree with maximum degree bounded by ∆ in O n2 · 2∆

µ3

time,

[FFL+ 13]

where µ = max {ef , cf }. Fellows et al.
extended this result to give an algorithm for
the problem of finding a non-contracting embedding of unweighted graphs into bounded degree
∆d+1 ·d)

trees with distortion at most d in O(n2 · |V (T )|) · 2O((5d)
2

time, where V (T ) denotes the

vertex set of the tree and where the maximum degree in T is bounded by ∆. In a follow-up paper,
Nayyeri et al. [NR17] gave the first (1 + ǫ)-approximation algorithm to embed weighted graphs
with spread Σ into graphs on m vertices with bounded treewidth α and doubling dimension λ
2λ
α·(1/ǫ)λ+2 ·λ·(O(dopt ))

in mO(1) · nO(α)·(dopt Σ)

1.2

time, where dopt denotes the minimum distortion.

Our contributions

In this paper, we further investigate the problem of embedding a general graph metric (G, DG )
into a low complexity graph metric (H, DH ) with distortion at most d. We will denote by n and
N the number of vertices in graphs G and H, respectively. Also, we denote distortion by d, the
maximum degree of H by ∆, and the length of a longest geodesic (or induced) cycle of H by ℓg .
We approach the metric embedding problem by trying to understand the behavior of the shortest
paths in G under a low distortion embedding into H, and what relation the mapping of these
paths has to shortest paths in H. Careful analysis of this connection helps us solve a number of
problems in this area, in the parameterized setting. All the algorithmic results mentioned
below are regarding non-contracting bounded distortion embeddings. However, all
these results can be extended to find bounded distortion embeddings, without the
assumption on non-contraction. For all the results, if the running time of the stated
algorithm is T , then the running time of finding a bounded distortion embedding
will be (nN )O(1) · T . For more details, refer to Proposition 2.2 in Section 2.
(a) In Section 3, we find a non-contracting embedding of distortion d of G into
H, when H is a cycle. We present an FPT algorithm, parameterized by d
and with time complexity 2O(d log d) · nO(1) . The techniques used for obtaining this
algorithm involve a few different ideas from the ones used in the previous papers where H
is either a path or a bounded degree tree. This is due to the existence of the large geodesic
cycle that is the graph H. The technique of pushing embeddings, introduced in [FFL+ 13]
for embedding into paths, does not work and some new ideas are required to solve this
problem. This resolves a question left open in [FFL+ 13]. Moreover, our FPT algorithm
can be extended to the weighted setting, where the input graph G has edge weights and
we parameterize by the distortion d as well as the maximum edge weight in G. On the
other hand, we show that when we do not take the maximum edge weight as a parameter,
then the problem becomes NP-Complete for any distortion d > 2.
(b) Observe that the treewidth of a cycle is 2, but the connected treewidth of a cycle is Ω(n) (see
the definitions of treewidth and connected treewidth in Section 2). These two parameters
(treewidth and connected treewidth of graphs) play important roles in this paper.
– First, in Section 4, we find a non-contracting bijection of distortion d of G
into H, which has constant treewidth α. Parameterized by d and ∆, the
O(αd2 )
. This is
FPT algorithm has time complexity O(α2 nα+3 ) · ∆d+1 · (α∆d+1 )∆
an extension of the result of Kenyon et al. [KRS10] for bijection into bounded degree
trees. Even though our FPT algorithm is different from the algorithm in [KRS10],
the fact that we are looking for bijective embeddings plays an important role in the
analysis and the algorithm in [KRS10] also uses this fact crucially.
– Next, in Section 5, we find a non-contracting embedding of distortion d of
G into H, which has treewidth α and length of longest geodesic cycle ℓg .
Parameterized by d, α, ℓg and ∆, the FPT algorithm has time complexity

µ2 ·∆d+1
O(µ·d+d2 )
+ nO(1) , where µ = 4(α + α2 (ℓg (α −
· 2O((4(µ+d))
O(n2 · N ) · (µ · ∆d+1 )∆
2) − 1)). This result crucially uses the result in [DM17] that a graph has bounded
connected treewidth if and only if the graph has bounded treewidth and no long
geodesic cycle. It is to be noted that a wheel graph has constant connected treewidth,
3

and by a result in [KRS10], embedding into wheel graphs is NP-hard even when the
distortion d = 2. However, when the wheel graph has bounded degree, then the
number of vertices in the wheel graph becomes bounded, and we obtain a trivial
FPT algorithm parameterized by the degree and the distortion d. This motivated
us to consider the above variant of metric embedding. Our FPT algorithm extends
the result of Fellows et al. [FFL+ 13] for embedding into trees with bounded degree.
Controlling the behavior of shortest paths in the graph G under a low distortion
embedding into the class of graphs with bounded degree and bounded connected
treewidth is algorithmically considerably harder than the case of bounded degree trees.
The algorithm given in [FFL+ 13] remembers the information of one shortest path
between two vertices in G but in our case we have to efficiently maintain information
of a set of useful paths between two vertices.
(c) In Section 6, we consider generalized theta graphs: defined by the union
of k paths all of which have common endpoints s and t. We find a noncontracting embedding of distortion d of G into H, which is a generalized
theta graph. Parameterized by d and k, our FPT algorithm has running time
2
O(kd)
·dO(d ) . As mentioned earlier, it was shown in [DM17] that
O(N )+n5 ·k2k+1 ·(kd+1)(2d)
a graph has bounded connected treewidth if and only if the graph has bounded treewidth
and no long geodesic cycle. In general, embedding into graphs with large geodesic cycles is
not amenable to known algorithmic techniques in the parameterized settings. Intuitively,
all known techniques for designing FPT algorithms in this area used the fact that if a low
distortion embedding F exists, then the embedding of a shortest path between two vertices
u, v ∈ V (G) and the shortest path in H between F (u) and F (v) are somewhat structurally
related. With the presence of large geodesic cycles this structural relation may completely
break down: although the two paths have similar lengths, structurally they could be completely different. This poses a problem for designing dynamic programming algorithms, a
staple for FPT algorithms in this area. The class of generalized theta graphs has treewidth
2, but may have large geodesic cycles. Hence, these graphs are more general than cycles
and have constant treewidth, but they do not have bounded connected treewidth. Even
for this very structured graph class, by virtue of the graphs having long geodesic cycles,
we needed to develop completely new ideas in order to find low distortion embeddings into
generalized theta graphs via FPT algorithms. The problem arises from the fact that any
two geodesic cycles of a generalized theta graph intersect at at least two vertices, and there
are many pairs of geodesic cycles with large intersections. Our algorithm is still a dynamic
programming algorithm, but a more involved one. The way to work around the apparent
barriers is to investigate more closely the structural properties of an input graph G that
can be embedded with small distortion into a generalized theta graph. Independently a
generalization of this result was obtained in [CFL+ 17].

2
2.1

Preliminaries
General Notations

We denote {1, . . . , t} as [t]. For a set S, |S| denotes the number of elements present in S.
Given a function f : U ′ → D ′ and a function F : U → D, where U ′ ⊆ U and D ′ ⊆ D, we say
that F extends f if for all x ∈ U ′ , F (x) = f (x). A graph is denoted by G while its vertex set
and edge set are denoted by V (G) and E(G), respectively. We denote the set of neighbours of
a vertex v ∈ V (G) as NG (v). The degree of a vertex v ∈ V (G) is denoted as degG (v). We also
define ∆(G) = max degG (v). We also define the set B(v, r) = {u ∈ V (H) | DH (u, v) ≤ r},
v∈V (G)

and refer to is as an r-ball around v. For a subgraph G′ of G, v ∈ V (G) \ V (S) is said to be a
neighbour of G′ if there is a vertex u ∈ V (G′ ) such that (u, v) ∈ E(G). A subgraph G′ of G is
4

said to be an induced subgraph if E(G′ ) = {(u, v) ∈ E(G)|u, v ∈ V (G′ )}. An induced cycle in a
graph is also called a geodesic cycle.
A generalized theta graph is the union of k paths P = {P1 , P2 , . . . Pk } such that the endpoints
of all the paths are two vertices s and t, while every pair of paths are internally vertex and edge
disjoint. Such a graph will also be referred to as a generalized theta graph defined at s,t, and
the family P is said to define the generalized theta graph.

2.2

Tree decompositions and treewidth

We define treewidth and tree decompositions.
Definition 2.1 (Tree Decomposition [CFK+ ]). A tree decomposition of a (undirected or directed) graph G is a tuple T = (T, {Xu }u∈V (T ) ), where T is a tree in which each vertex u ∈ V (T )
has an assigned set of vertices Xu ⊆ V (G) (called a bag) such that the following properties hold:
S
• u∈V (T ) Xu = V (G)
• For any (x, y) ∈ E(G), there exists a u ∈ V (T ) such that x, y ∈ Xu .

• If x ∈ Xu and x ∈ Xv , then x ∈ Xw for all w on the path from u to v in T .
In short, we denote T = (T, {Xu }u∈V (T ) ) as T .
The treewidth twT of a tree decomposition T is the size of the largest bag of T minus one.
A graph may have several distinct tree decompositions. The treewidth tw(G) of a graph G is
defined as the minimum of treewidths over all possible tree decompositions of G. Note that for
the tree T of a tree decomposition, we denote a vertex of V (T ) in bold font.
A tree decomposition T = (T, {Xu }u∈V (T ) )) is called a nice tree decomposition if T is a tree
rooted at some node r where Xr = ∅, each node of T has at most two children, and each node
is of one of the following kinds:
• Introduce node: a node u that has only one child u′ where Xu ⊃ Xu′ and |Xu | =
|Xu′ | + 1.
• Forget vertex node: a node u that has only one child u′ where Xu ⊂ Xu′ and |Xu | =
|Xu′ | − 1.
• Join node: a node u with two children u1 and u2 such that Xu = Xu1 = Xu2 .
• Leaf node: a node u that is a leaf of T , and Xu = ∅.
One can show that a tree decomposition of width w can be transformed into a nice tree decomposition of the same width w and with O(w|V (G)|) nodes, see e.g. [CFK+ ].
A connected tree decomposition is a tree decomposition where the vertices in every bag induce
a connected subgraph of G [DM17]. The connected treewidth ctw(G) of a graph G is defined as
the minimum of treewidths over all possible connected tree decompositions of G.

2.3

Parameterized Complexity

The instance of a parameterized problem/language is a pair containing the problem instance
of size n and a positive integer k, which is called a parameter. The problem is said to be
in FPT if there exists an algorithm that solves the problem in f (k)nO(1) time, where f is a
computable function. Such an algorithm is called an FPT algorithm and the running time
of such an algorithm is called FPT running time. There is also an accompanying theory of
parameterized intractability using which one determines that a parameterized problem is unlikely
to admit FPT algorithms. A parameterized problem is said to be in the class para-NP if it has
a nondeterministic algorithm with FPT running time. To show that a problem is para-NP-hard
we need to show that the problem is NP-hard for some constant value of the parameter. Readers
are requested to refer [CFK+ ] for more details on Parameterized Complexity.
5

2.4

Metric Embedding

Given a graph G, the function DG : V (G) × V (G) → R is the shortest distance function
defined on G; for any pair u, v ∈ V (G), DG (u, v) is the length of the shortest path between u
and v in the graph G. When the graph is unweighted, then note that the range of DG is Z≥0 .
When we talk of a graph metric, then we denote it as the tuple (G, DG ). In this paper, unless
otherwise mentioned, a graph metric is that of an unweighted undirected graph.
A metric embedding of a graph metric (G, DG ) into a graph metric (H, DH ) is a function
F : V (G) → V (H). When the graph metrics are clear, we also use the terminology that the
metric embedding is that of G into H, or that G is embedded into H. We also denote (G, DG )
as the input metric space and (H, DH ) as the output metric space. The expansion of F is defined
as
DH (F (u), F (v))
.
eF = max
DG (u, v)
u,v∈V (G)
Similarly, the contraction of F is defined as
cF =

DG (u, v)
.
u,v∈V (G) DH (F (u), F (v))
max

The metric embedding F is said to be of distortion d if d = eF ·cF . When F has the property that
cF < 1, then the metric embedding is called a non-contracting embedding. In this case, a noncontracting distortion d metric embedding implies that the expansion is at most d. Therefore,
for any pair u, v ∈ V (G),
DG (u, v) ≤ DH (F (u), F (v)) ≤ d · DG (u, v).
When d = 1, then the metric embedding is called an isometry.
The Gen-Graph Metric Embedding problem is defined below:
Gen-Graph Metric Embedding
Input: Two graph metrics (G, DG ) and (H, DH ), where G is a connected graph, and a
positive integer d
Question: Is there a distortion d metric embedding of (G, DG ) into (H, DH )?
A related problem is the Graph Metric Embedding problem, where we are only interested
in finding a non-contracting distortion d metric embedding.
Graph Metric Embedding
Input: Two graph metrics (G, DG ) and (H, DH ), where G is a connected graph, and a
positive integer d
Question: Is there a non-contracting distortion d metric embedding of (G, DG ) into
(H, DH )?
We also define the following restricted version of the problem.
Red-Blue Graph Metric Embedding
Input: Two graph metrics (G, DG ) and (H, DH ), where G is a connected graph and V (H) =
R ⊎ B, and a positive integer d
Question: Is there a metric embedding F : V (G) → R such that it is a non-contracting
distortion d metric embedding of (G, DG ) into (H, DH )?
In Red-Blue Graph Metric Embedding, the objective is to find a non-contracting distortion d metric embedding that maps the vertices of V (G) only to the vertices in R ⊆ V (H).
Now, we will explain the necessity of this restricted problem in the graph metric setting.
When (G, DG ) and (H, DH ) are graph metrics, then the contraction cF is a rational number
p
q . By a result of Nayyeri et al. [NR15], we can assume that F is a non-contracting distortion d
metric embedding. We state a modified version of the result, tailored to our need.
6

Proposition 2.2. Let (G, DG ) and (H, DH ) be graph metrics with n and N vertices, respectively.
Then the Gen-Graph Metric Embedding problem reduces to solving O(N 4 n4 ) instances of
the Red-Blue Graph Metric Embedding problem.
Proof. Let F be any metric embedding with distortion d. Let x, x′ ∈ V (G) and y, y ′ ∈ V (H)
realize the expansion eF and the contraction cF , respectively. Since we consider graph metrics,
the contraction cF is a rational pq . We subdivide all the edges of H p times. This results in a new
graph H ′ , where we mark all the original vertices of H with red and all the newly introduced
subdivision vertices with blue. We define a bipartition of V (H ′ ) into the set R of red vertices
and the set B of blue vertices. Now, the mapping F still is a distortion d embedding of G
into H ′ . The extra property is that F is a non-contracting distortion d embedding of G into
H ′ . Since the original vertices of H are remembered in the set R, we can derive a distortion d
metric embedding of G into H from a non-contracting distortion d metric embedding of G into
H ′ , where V (G) is mapped to R. Since we do not know the metric embedding F , we guess the
vertices x, x′ , F (x), F (x′ ), y, y ′ , F −1 (y) and F −1 (y ′ ). There are O(N 4 n4 ) choices for these values.
Thus, if we solve O(N 4 n4 ) instances of Red-Blue Graph Metric Embedding, we can solve
Gen-Graph Metric Embedding.
The Gen-Graph Metric Embedding problem or the Graph Metric Embedding problem for a graph class G is a variant where the output metric space (H, DH ) is such that H ∈ G.
In this paper, the graph classes we consider are the class of cycles, the class of generalized theta
graphs and the class of graphs with treewidth α, for any constant α. All these classes are closed
under the subdivision operation. Therefore, by Proposition 2.2 solving the Gen-Graph Metric Embedding for such a graph class is same as solving polynomially many instances of the
Red-Blue Graph Metric Embedding problem for the graph class. In this paper, we present
detailed FPT algorithms for the Graph Metric Embedding problem. All these algorithms
are easily modified to solve the Red Blue Graph Metric Embedding problem, and therefore
by Proposition 2.2, FPT algorithms for the Gen-Graph Metric Embedding problem can be
designed.
The bijective Gen-Graph Metric Embedding problem takes the same input but aims
to determine whether the distortion d embedding is a bijective function. The following result
in [GKL03] is useful for us to reduce the problem to that of finding a non-contracting distortion
d metric embedding.
Proposition 2.3. Let (G, DG ) and (H, DH ) be two graph metrics. Let F : V (G) → V (H) be
a bijection. Then the expansion of F is achieved by an adjacent pair (x, x′ ) ∈ E(G) and the
contraction of F is achieved by an adjacent pair (y, y ′ ) ∈ E(H).
From the above proposition, we obtain the following result.
Lemma 2.4. Let (G, DG ) and (H, DH ) be graph metrics with n and m vertices, respectively.
Then the bijective Gen-Graph Metric Embedding problem reduces to solving (mn)O(1) instances of the Red-Blue Graph Metric Embedding problem with the following property:
consider a reduced instance of the Red-Blue Graph Metric Embedding problem where the
input metric is (G, DG ) and the output metric is (H ′ , DH ′ ) with V (H ′ ) = R′ ⊎ B ′ . (i) Any path
in H ′ of length at least d + 1 has at least one internal vertex in R′ ; (ii) The solution metric
embedding should be a bijection between V (G) and R′
Proof. By Proposition 2.3, for a bijective distortion d metric embedding F , an edge in H realizes
the contraction cF . Therefore, cF ∈ N and cF ≤ d. From Proposition 2.2, it is enough to solve
the Red-Blue Graph Metric Embedding problem where the output graph metric of each
instance has had each of its edges subdivided at most d times. Therefore, in the new output
graph metric any path of length d + 1 contains at least one internal red vertex. Also, a bijective
mapping of the Gen-Graph Metric Embedding problem implies that in a reduced instance
7

of Red-Blue Graph Metric Embedding we look for a bijection between the vertices of the
input graph metric (G, DG ) and the red vertices R′ of the output graph metric (H ′ , DH ′ ).
In Section 4, we describe an FPT algorithm for bijective Graph Metric Embedding for
constant treewidth graphs. Using Lemma 2.4, it is possible to easily modify this algorithm to
design an FPT algorithm for bijective Gen-Graph Metric Embedding.
The following Observation relates ∆(H) to ∆(G) when G can be embedded into H by a
non-contracting distortion d embedding.
Observation 2.5. Given graph metrics (G, DG ) and (H, DH ), if ∆(G) > Σ0≤i≤d−1 ∆(H)(∆(H)−
1)i then there is no non-contracting distortion d metric embedding of G into H.
Proof. Consider any vertex v ∈ V (H). Consider the set B(v, d) = {u ∈ V (H) | DH (u, v) ≤ d}.
Then |B(v, d)| ≤ Σ0≤i≤d−1 ∆(H)(∆(H) − 1)i . Let x ∈ V (G) be such that degG (x) = ∆(G) >
Σ0≤i≤d−1 ∆(H)(∆(H) − 1)i . If there is a non-contracting distortion d embedding F of G into
H, then without loss of generality we assume that F (x) = v. However, by non-contracting, F
is an injective function. Since F has distortion d, every neighbour of x in G must be mapped
to a vertex of B(v, d). However, since ∆(G) > Σ0≤i≤d−1 ∆(H)(∆(H) − 1)i , this is not possible.
Therefore, there cannot exist a non-contracting distortion d embedding of G into H.
The following observation is about non-contracting distortion d embeddings into lines or
cycles.
Observation 2.6. Let F be a non-contracting distortion d embedding of a graph G, into H such
that H is either a line or a cycle. Let P ′ be the maximal subpath of H such that F (x) ∈ V (P ′ )
for all x ∈ V (G). Then |P ′ | ≤ 2dn, where |V (G)| = n.
Proof. For any two vertices x, y ∈ V (G), DG (x, y) ≤ n − 1. This implies DH (F (x), F (y)) ≤
d(n − 1). Let u ∈ V (H) be such that some vertex of G is mapped to it. Observe that any other
vertex of H that has a vertex of G as its pre-image, must be within a distance of d(n − 1) from
u in H. As the degree of u is at most 2, the result follows.

3

Graph Metric Embedding for cycles

In this Section, we are going to look at the parameterized complexity of the Graph Metric
Embedding problem for cycles. Recall that this means that the output metric (C, DC ) is such
that C is a cycle. First, we consider the problem of embedding unweighted graphs into cycles,
parameterized by the distortion d. We show that the problem is in FPT. Next, we consider the
input graph to have edge weights, while the parameters are the distortion d and the largest edge
weight W . This problem also has an FPT algorithm, very similar to the one for unweighted
graphs. However, in general the weights on the edges need not be reasonably bounded, and
therefore, we consider the weighted problem with only distortion d as parameter. In this case,
the problem becomes NP-hard for any distortion d > 2, where d is a rational number.

3.1

Embedding an unweighted graph into a cycle

In this part, we will present an FPT algorithm for embedding an input unweighted graph into
a given cycle. Our algorithm is similar to the FPT algorithm for Graph Metric Embedding
for lines, given in [FFL+ 13]. We too try to build the metric embedding function by stitching
together partial embeddings that we find locally. Similar to the definition in [FFL+ 13], a partial
embedding describes what a metric embedding could possibly look like when restricted to a
small subpath of the given cycle. The main idea is to employ a dynamic programming strategy
to build a solution metric embedding using a set of computed partial embeddings. We compute
the set of partial embeddings by an FPT algorithm and the dynamic programming algorithm
8

is also FPT. Thereby we find a metric embedding into the given cycle in FPT time. Now we
formalize the ideas. In [FFL+ 13], the algorithm searched for a special kind of embedding, called
a pushing embedding, that always exists for embedding into lines. Such an embedding need not
exist for embedding into cycles. Our algorithm does not require the assumption of a pushing
embedding.
Let (G, DG ) be the input connected graph metric and (C, DC ) be the output graph metric
such that C is a cycle. We denote the vertices of the cycle C as 0, . . . , N − 1 in the clockwise
direction. Whenever we use u to denote a vertex of C in this section, consider the vertex to be
numbered u mod N .
First, we make an observation about a property of a non-contracting distortion d embedding
into a cycle.
Observation 3.1. Let F be a non-contracting distortion d embedding of G into C. Then there
exists at most one maximal connected subgraph S of C such that the pre-image of V (S) is ∅
and |V (S)| ≥ 2d + 3.
Proof. We prove the observation by contradiction. The input graph G is connected. Let S1 and
S2 be two maximal connected subgraph of C such that the pre-images of both V (S1 ) and V (S2 )
are ∅ and |V (S1 )| , |V (S2 )| ≥ 2d + 3. Without loss of generality, assume that the vertex set of S1
is {1, . . . , i} and that of S2 is {j, . . . , k}, where 2d + 3 ≤ i < j − 1 and j + 2d + 2 < k + 1 ≤ N .
By definition of maximality, 0, i + 1, j − 1 and k + 1 have pre-images. Consider the sets Sˆ1 =
{v ∈ V (G)|F (v) ∈ {i + 1, . . . , j − 1}} and Sˆ2 = {v ∈ V (G)|F (v) ∈ {k + 1, . . . , N = 0 mod N }}.
These subsets are nonempty and form a partition of V (G).
Now, DC (x, y) > d, for all x ∈ {i + 1, . . . , j − 1} and y ∈ {k + 1, . . . , N }. Consider any pair
of vertices u, v ∈ V (G) such that u ∈ Sˆ1 and v ∈ Sˆ2 . Since DC (F (u), F (v)) > d and F is a
non-contracting distortion d embedding of G, it is true that (u, v) ∈
/ E(G). This implies the
graph G is not connected, which is a contradiction.
From now on, we assume that if there is a non-contracting distortion d embedding of G into C,
the pre-image of the vertex 0 ∈ V (C) is nonempty. Also, let us assume that if there is a subgraph
S of C such that |V (S)| ≥ 2d + 3 and the pre-image of V (S) is ∅, then V (S) = {k, . . . , N − 1}
for some k ≤ N − (2d + 3). This can be ensured by making a guess for the vertex of G that will
be mapped to 0 ∈ V (C); there are polynomially many such guesses. For any ℓ ∈ {0, . . . , N − 1},
we define Sℓ = {ℓ − (d + 1), . . . , ℓ + (d + 1)}. We fix a function Ψ : W → S0 , where Ψ is a
non-contracting distortion d embedding of a vertex set W ∈ V (G). Since we are under the
assumption that the preimage of the vertex 0 ∈ V (C) is nonempty, we also make sure that
W 6= ∅. All of the following definitions are with respect to Ψ. First, we define the notion of a
partial embedding at a vertex a ∈ V (C).
Definition 3.2. (i) For an a ∈ V (C), a partial embedding of U ⊆ V (G), with respect to Ψ,
is a function fa : U → Sa . Here, U is referred to as Domfa and a is referred to as mid(fa ).
[p,q]

(ii) Domfa is the set of vertices of U that are mapped into {a + p, . . . a + q}, where −(d + 1) ≤
p ≤ q ≤ (d + 1). Domxfa is the set of vertices of U that are mapped into {a + x}.
[−(d+1),−1]

[1,(d+1)]

(iii) DomL
and DomR
. L(fa ) (R(fa )) is the union of the
fa = Domfa
fa = Domfa
vertex sets of connected components of V (G) \ (W ∪ U ) that have neighbours in DomL
fa
).
(DomR
fa
It is important to define the feasibility of a partial embedding. Since we ultimately want
to use the partial embeddings to build a metric embedding of G into C, it is necessary that a
feasible partial embedding behaves like a metric embedding locally.
Definition 3.3. Let fa : U → Sa be a partial embedding with respect to Ψ, where U ⊆ V (G).
Then f is said to be feasible with respect to Ψ, if it satisfies the following conditions.
9

(i) U 6= ∅, U ∩ W = ∅ and Sa ∩ S0 = ∅.
(ii) fa is a non-contracting distortion d embedding of U .
(iii) For every pair u ∈ U and w ∈ W , DC (fa (u), Ψ(w)) is non-contracting and has expansion
at most d,
(iv) If u is a neighbour of a vertex in Dom0fa , then fa (u) ∈ Sa .
(v) L(fa ) ∩ R(fa ) = ∅.
Next, we define the notion of succession from one partial embedding to another. This
definition will help us put together many partial embeddings to get one metric embedding of G
into C.
Definition 3.4. Let fa : U → Sa be a feasible partial embedding of U with respect to Ψ. Let
fb : U ′ → Sb be a feasible partial embedding of U ′ with respect to Ψ. Then fb succeeds fa with
respect to Ψ if the following conditions are satisfied.
[−d,d+1]

(i) Domfa

[−(d+1),d]

= Domfb

.

(ii) ∀u ∈ Domfa ∩ Domfb , fa (u) = fb (u).
−(d+1)

(iii) Domfa

(d+1)

(iv) Domfb

⊆ L(fb ).

⊆ R(fa ).

While we are considering a partial embedding f , the sets L(f ) and R(f ) help us to have a
view of the mapping of the rest of the graph G in terms of this partial embedding f . The next
Lemma proves that our definition of succession implies that we have a consistent view of the
mapping of the rest of G when we move from one partial embedding to another.
Lemma 3.5. Let fa : U → Sa be a feasible partial embedding of U with respect to Ψ, and
fb : U ′ → Sb be a feasible partial embedding of U ′ with respect to Ψ. If fb succeeds fa with
respect to Ψ, then the following properties hold.
(i) R(fa ) = R(fb ) ∪ Domd+1
fb .
−(d+1)

(ii) L(fb ) = L(fa ) ∪ Domfa

.

Proof. We prove property (i), and property (ii) can be proved similarly. Note that fb succeeds
fa . In the forward direction, we prove that R(fa ) ⊆ R(fb )∪Domd+1
fb . Let us consider a connected
component Y such that V (Y ) ⊆ R(fa ). Recall the definition of R(fa ). Since the two embeddings
−(d+1)
.
are feasible, L(fa )∩R(fa ) = ∅. This implies that Y does not contain any neighbour of Domfa




[−(d+1),d]
[−d,d+1]
∪W .
∪ W = G \ Domfb
Hence, Y is a connected component of G \ Domfa
If Y does not contain any vertex from Domd+1
fb , then Y is a connected component of G \
[1,d+1]

(Domfb ∪ W ). As V (Y ) ⊆ R(fa ), by definition Y contains a neighbour of DomR
fa = Domfa
[0,d]
Domfb .

By definition of feasibility, if Y had a neighbour in

[1,d+1]
. Since Y
to contain a vertex in Domfb
d+1
with no vertex in Domfb , Y cannot have a
[1,d]
Domfb ⊆ DomR
fb . Hence, V (Y ) ⊆ R(fb ).

[1,d]
Domfb ,

=

then Y would have

is a connected component of G \ (Domfb ∪ W )
neighbour in Dom0fb . So, Y has neighbours in

′
On the other hand, if Y contains a vertex from Domd+1
fb , then each connected component Y


′
of G[Y \ Domd+1
fb ∪ W ], is also a connected component of G\(Domfb ∪ W ). So, V (Y ) ⊆ R(fb ).

This implies that V (Y ) ⊆ R(fb ) ∪ Domd+1
fb .

10

To complete the proof, in the backward direction, we prove that R(fb )∪Domd+1
fb ⊆ R(fa ). By
d+1
condition (iv) of Definition 3.4, Domfb ⊆ R(fa ). Now consider a connected component Y such
that V (Y ) ⊆ R(fb ). By the definition of R(fb ), Y is a connected component of G \ (Domfb ∪ W ).
−(d+1)
⊆ L(fb ). Also, L(fb ) ∩ R(fb ) = ∅ as fb is a
By condition (iii) of Definition 3.7, Domfa
−(d+1)

. This implies Y is
feasible partial embedding. So, Y does not contain any vertex of Domfa
a connected component of G \ (Domfa ∪ Domfb ∪ W ).
[1,d]
If Y does not have a neighbour in Domd+1
=
fb , then Y has neighbours only in Domfb
[2,d+1]

d+1
⊆ DomR
Domfa
fa . Thus, V (Y ) ⊆ R(fa ). If Y has a neighbour in Domfb , then in the graph
G \ (Domfa ∪ W ), Y and at least one vertex from Domd+1
fb are in the same connected component.
d+1
Since Domfb ⊆ R(fa ) and since L(fa ) ∩ R(fa ) = ∅, V (Y ) ⊆ R(fa ).
Putting everything together, R(fb ) ∪ Domd+1
⊆ R(fa ). Hence, we have proved property
fb
(i).

Finally, the following definitions help to establish the meaning of building a metric embedding
using a sequence of partial embeddings.
Definition 3.6. Let Π = {fi : Ai → Bi , i ∈ [t]} be a set of functions such that for any i, j ∈ [t],
t
t
S
S
x ∈ Ai ∩ Aj implies fi (x) = fj (x). Then we define ΦΠ :
Ai →
Bi such that ΦΠ (x) = fi (x)
i=1

for i ∈ [t], x ∈ Ai .

i=1

Definition 3.7. A sequence of feasible partial embedding Φ1 , . . . , Φt with respect to Ψ is embeddable with respect to Ψ if it satisfies the following conditions.
(i) Φi succeeds Φi−1 with respect to Ψ for every 2 ≤ i ≤ t.
(ii) Let F = ΦΠ , where Π = {Φi : i ∈ [t]} ∪ Ψ. Suppose Φ1 : A → Sa and Φt : B → Sb . Let
us call the vertices {1, 2, . . . d} ∈ V (C) as Cb and the vertices {−(d + 1), . . . , −1} ∈ V (C)
as Ce . If u ∈ V (G) is a neighbour of some vertex in DomL
Φ1 , then F (u) ∈ Sa ∪ Cb and if
R
u ∈ V (G) is a neighbour of some vertex in DomΦt , then F (u) ∈ Sb ∪ Ce .
(iii) L(Φ1 ) = ∅, R(Φ1 ) = V (G) \ (DomΦ1 ∪ W ) and L(Φt ) = V (G) \ (DomΦt ∪ W ), R(Φt ) = ∅.
We prove the relation between a non-contracting distortion d embedding of G into C and a
sequence of feasible partial embeddings.
Lemma 3.8. A graph G has a non-contracting distortion d embedding into a cycle C if and
only if there exist a W ⊆ V (G), a non-contracting distortion d partial embedding Ψ : W → S0
and an embeddable sequence of feasible partial embeddings Φ1 , . . . , Φt with respect to Ψ.
Proof. First, we show that if F is a non-contracting distortion d embedding of G into C then
there is an embeddable sequence of feasible partial embeddings Φ1 , . . . , Φt with respect to some
Ψ. By Observation 3.1, there exists at most one connected subgraph S of C such that the
pre-image of S under F is ∅ and |S| ≥ 2d + 3. If such a subgraph S exists, then without loss
of generality assume that the vertices of S are {k, . . . , N − 1} for some k ≤ N − (2d + 3). Now,
take W as the set of vertices that are mapped by F into S0 . Take a function Ψ : W → S0 to be
the restriction of F to S0 . Let t = max F (v) − (2d + 2). For i ∈ [t], let Φi be F restricted to
v∈V (G)

the vertices that are mapped into S2d+2+i . Observe that F = ΦΠ , where Π = {Φi , i ∈ [t]} ∪ {Ψ}.
Now, it is easy to verify that Φ1 , . . . , Φt are all embeddable with respect to Ψ.
Conversely, let {Φ1 , . . . , Φt } be a sequence of embeddable feasible partial embeddings with
respect to Ψ : W → S0 . We make the following claims about the sequence of embeddable feasible
partial embeddings, which we prove later.
11

Claim 3.9. For each v ∈ V (G), either v ∈ W or there exists some Φi such that v ∈ Dom(Φi ).
Claim 3.10. The following properties hold:
(a) For any v ∈ V (G) \ W , let Av = {mid(Φi ) ∈ V (C) \ S0 : v ∈ DomΦi , 1 ≤ i ≤ t}. Then the
subgraph of C induced by Av , is connected.
(b) v ∈ DomΦi ∩ DomΦj implies Φi (v) = Φj (v).
Consider F = ΦΠ where Π = {Φi , i ∈ [t]} ∪ {Ψ}. We are done with the proof of the converse
part by the following claims, which we will prove later.
Claim 3.11. The function F = ΦΠ is a distortion d embedding of G into C.
Claim 3.12. The function F = ΦΠ is a non-contracting embedding of G into C.

Proof of Claim 3.9. If v ∈ W or v ∈ DomΦ1 , then we are done. Assume that v ∈
/ W ∪ Φ1 .
This implies v ∈ R(Φ1 ) as the graph G is connected and L(Φ1 ) = ∅. Then by Lemma 3.5,
d+1
v ∈ R(Φ2 ) ∪ Domd+1
Φ2 . If v ∈ DomΦ2 , then v ∈ DomΦ2 and we are done. Otherwise, v ∈ R(Φ2 ).
Let m − 1 be the maximum index such that v ∈ R(Φm−1 ). Observe that m ≤ t as R(Φt ) = ∅
and v ∈
/ W . By Lemma 3.5, we can conclude that v ∈ Domd+1
Φm , i.e., v ∈ DomΦm .
Proof of Claim 3.10. (a) We give a proof by contradiction. Let v ∈ DomΦi , v ∈ DomΦj such
that mid(Φi ) and mid(Φj ) are not adjacent in the graph C \ W . W.l.o.g assume that
mid(Φi ) < mid(Φj ). Consider the path P = {x1 , . . . , xk }, k ≥ 3, from mid(Φi ) to mid(Φj )
in the graph C \ W , where x1 = mid(Φi ) and xk = mid(Φj ).
Recall the definition of succession from Definition 3.4. The partial embedding Φj cannot
succeed Φi as mid(Φi ) and mid(Φj ) are not adjacent. So, there must exist some Φi′ such
that mid(Φi′ ) is a vertex in P such that mid(Φi ) < mid(Φi′ ) < mid(Φj ). This implies
v ∈ L(Φi′ ) and v ∈ R(Φi′ ), i.e., L(Φi′ ) ∩ R(Φi′ ) 6= ∅. This is not possible as Φi′ is a feasible
partial embedding.
(b) The statement follows from part (a) and by using the definition of succession.
Proof of Claim 3.11. By Claim 3.9, DomF = V (G). Consider any pair of vertices u, v ∈ V (G).
We need to show the following statement. DC (F (u), F (v)) ≤ d.DG (u, v). We use the method
of induction on DG (u, v). For now, assume that the statement is true for DG (u, v) = 1. We
will prove it after the inductive step. Let the statement be true for all DG (u, v) < l. Consider
a pair of vertices u, v such that DG (u, v) = l > 1. Let x be some vertex, other than u and
v, in the shortest path from u to v, i.e, DG (u, v) = DG (u, x) + DG (x, v). By triangle inequality, DC (F (u), F (v)) ≤ DC (F (u), F (x)) + DC (F (x), F (v)) holds. By the induction hypothesis,
DC (F (u), F (x)) ≤ d.DG (u, x) and DC (F (x), F (v)) ≤ d.DG (x, v) hold. Putting everything together, DC (F (u), F (v)) ≤ d.DG (u, v). Thus, we need to prove the base case of this induction
hypothesis. Consider an edge (u, v) in G. We break the analysis into the following cases.
• Case 1(v ∈ W ): If u ∈ W , then DC (F (u), F (v)) ≤ d as Ψ is a distortion d embedding
of W . If u ∈
/ W , then u is in the domain of some Φi . The path between Ψ(v) = F (v)
and Φi (u) = F (u) does not expand by a factor of more than d, due to condition (iii) of
Definition 3.3. This implies DC (F (u), F (v)) ≤ d.

12

• Case 2 (v ∈ DomL
Φ1 ): In this case, again we denote the vertex set {1, . . . , d + 1} ∈ V (C)
as Cb . F (u) ∈ Sa ∪ Cb by condition (ii) of Definition 3.7.
If F (u) ∈ Sa , both u, v ∈ DomΦ1 , DC (F (u), F (v)) ≤ d. This is because Φ1 is a feasible
partial embedding of DomΦ1 .
If F (u) ∈ Cb , then u ∈ W . The path between Φ1 (v) = F (v) and Ψ(u) = F (u) is not expanding by a factor of more than d by condition (iii) of Definition 3.3. So, DC (F (u), F (v)) ≤
d.
• Case 3 (v ∈ DomR
Φt ): In this case, we denote the vertex set {−(d + 1), . . . , 1} ∈ V (C) as
Ce . F (u) ∈ Sb ∪ Ce by condition (ii) of Definition 3.7.
If F (u) ∈ Sb , both u, v ∈ DomΦt , DC (F (u), F (v)) ≤ d. This is because Φt is a feasible
partial embedding of DomΦt .
If F (u) ∈ Ce , then u ∈ W . The path between Φt (v) = F (v) and Ψ(u) = F (u) is not expanding by a factor of more than d by condition (iii) of Definition 3.3. So, DC (F (u), F (v)) ≤ d.
R
• Case 4 (v ∈
/ W ∪ DomL
Φ1 ∪ DomΦt ): It is easy to observe that there exists a Φi such that
0
v ∈ DomΦi . By condition (iv) of Definition 3.3, we can say that u ∈ DomΦi . Note that
both u and v are in DomΦi and Φi is a feasible partial embedding. So, DC (F (u), F (v)) ≤ d.

Proof of Claim 3.12. By Claim 3.9, DomF = V (G). Let us consider u, v ∈ V (G). Let PC (u, v) =
{x ∈ V (G), F (x) is in the shortest path from F (u) to F (v) in C}. Note that u, v ∈ PC (u, v).
We have to show that DG (u, v) ≤ DC (F (u), F (v)) for any u, v ∈ V (G).
We divide the proof into the following cases.
• Case 1(PC (u, v) ∩ W 6= φ):
For some x ∈ W , dC (F (u), F (v)) = dC (F (u), F (x)) + dC (F (x), F (v)). Using the fact that
u(v) is in the domain of some feasible partial embedding and recalling condition (iii) of
Definition 3.3, observe that DG (u, x) ≤ DC (F (u), F (x)) and DG (x, v) ≤ DC (F (x), F (v)).
This implies DG (u, v) ≤ DC (F (u), F (v)).
• Case 2(PC (u, v) ∩ W = φ): Fact 1: If DC (F (u), F (v)) ≤ 2d + 2, then there exists some
Φi such that u, v ∈ Dom(Φi ).
This implies the path between F (u) and F (v) is non-contracting and has expansion of at
most d due to condition (ii) of Definition 3.3.
Now assume that DC (F (u), F (v)) ≥ 2d + 3. Let PC (u, v) = {x1 , . . . , xl } such that
l−1
P
DC (F (u), F (v)) =
DC (F (xi ), F (xi+1 )) and PC (xi , xi+1 ) = {xi , xi+1 }. Note that u =
i=1

x1 , v = xl , and DC (F (xi ), F (xi+1 )) ≤ 2d + 2 . Observe that

DG (xi , xi+1 ) ≤ DC (F (xi ), F (xi+1 )) by Fact 1
Hence, DG (u, v) ≤ DC (F (u), F (v)).
Hence, we are done.
Thus, we have seen that finding a sequence of feasible partial embeddings is enough to find
a non-contracting distortion d embedding of G into C. What remains to be proven is that the
number of such sequences is bounded by an FPT function.
In the following observation, we describe the structure of a partial embedding.

13

Observation 3.13. Let f : U → Sa be any feasible partial embedding with respect to Ψ. Then
we can describe it by the following properties.
(i) An integer a such that 2d + 3 ≤ a ≤ N − (2d + 3).
(ii) A sequence of vertices u1 , . . . , up .
(iii) A sequence of non-negative integers x0 , . . . , xp−1 such that
x0 +

p−1
P

(DG (ui , ui+1 ) + xi ) ≤ 2d + 2.

i=1

Proof. Consider the vertex set {u1 , . . . , up } as Domf = U , such that f (u1 ) < f (u2 ) . . . < f (up ).
Let x0 = d + 1 − (a − f (u1 )). For i ∈ {1, . . . , p − 1} !
let xi = DC (f (ui ), f (ui+1 )) − DG (ui , ui+1 ).
j−1
P
Then, f (uj ) = a − (d + 1) + x0 +
(DG (ui , ui+1 + xi ). This implies the statement of the
i=1

Observation.

Now, we are ready to bound the number of feasible partial embeddings possible.
Definition 3.14. Let x be a non-negative integer and Nu1 (x) be the number of sequences
p−1
P
u1 , . . . , up such that
DC (f (ui ), f (ui+1 )) = x. We define N (x) = max Nu1 (x).
u1 ∈V (G)

i=1

Lemma 3.15. For any non-negative integer x, N (x) ≤ (4d(2d + 2))x .

Proof. We prove the statement using induction on x. For x = 0, the statement is trivially true.
Assume that the statement is true for every y < x. Let Si be the set of sequences such that
DC (f (u1 ), f (u2 )) = i, where i ∈ [x]. As f is a non-contracting embedding, DG (u1 , u2 ) ≤ i.
x
P
Let Au1 (i) be the set of vertices u such that DG (u1 , u) ≤ i. Observe that, Nu1 (x) ≤
|Si | ≤
x
P

i=1

i=1

|Au1 (i)| · N (x − i).

By the induction hypothesis,
N (x − i) ≤ (4d(2d + 2))x−i .

Note that by Observation 2.5, if there is a non-contracting distortion d embedding of G into C,
it must be true that ∆(G) ≤ 2d. This implies that |Au1 (i)| ≤ 2 · (2d)i . So,
N u1 (x) ≤

x
X

2 · (2d)i · (4d(2d + 2))x−i

i=1

≤ (4d(2d + 2))x

x
X
i=1

≤ (4d(2d + 2))x

1
(2d + 2)i

Note that the above discussion is true for any u1 ∈ V (G). Hence,
N (x) ≤ (4d(2d + 2))x .

Lemma 3.16. Let |V (G)| = n, |V (H)| = N . The total number of feasible
partial embeddings

2d+2 and the total number of
with respect to a particular Ψ, is at most O N
·
n
·
(4d(2d
+
2))

possible Ψ : W → S0 is O n · (4d(2d + 2))2d+2 .
14

Proof. By Observation 3.13 and Definition 3.14, we can have at most N (2d + 2 − x1 ) feasible
partial embeddings with respect to Ψ for a fixed integer a and fixed vertices u1 ∈ V (G), where
u1 is mapped to a − (d + 1) + x1 . Hence, the total number of feasible partial embeddings is at
most
N ·n·

2d+2
X

N (2d + 2 − x1 ) ≤ N · n ·

2d+2
X

(4d(2d + 2))2d+2−x1

x1 =0

x1 =0



= O N · n · (4d(2d + 2))2d+2 .

Observe that a particular Ψ can be described by a vertex sequence u1 . . . up along with a
p−1
P
sequence of non-negative integers x0 , . . . , xp−1 such that x0 +
(DG (ui , ui+1 ) + xi ) ≤ 2d + 2.
i=1

Hence, the stated bound on the total number of possible Ψ follows from Lemma 3.15.

Putting everything together, our algorithm tries to find a sequence of feasible partial embeddings in order to find a non-contracting distortion d embedding of G into C. The bound on
feasible partial embeddings makes the algorithm run in FPT time.
Theorem 3.17. Given an undirected unweighted graph G on n vertices, a cycle C and a distortion parameter d, there exists an algorithm that either finds a non-contracting distortion d embed
ding of G into C or decides that there does not exist such an embedding in O n3 · d2d+3 · (4d(2d + 2))4d+4
time.
Proof. Suppose there exists a desired embedding F from G to C. By Observation 2.6, there
exists a maximal subpath P of length 2dn of C such that F (x) ∈ V (P ) for all x ∈ V (G). If
|V (C)| = N > 4dn, then consider an induced connected subgraph C ′ of C having 2dn vertices.
Observe that C ′ is a line and G can be embedded into C if and only if G can be embedded into
C ′ . We run the algorithm of embedding an unweighted graph into a line [FFL+ 13], to find a
possible embedding of G into C ′ . Note that the time complexity of the mentioned algorithm in
[FFL+ 13], is O(nd4 (2d + 1)2d ).
If N ≤ 4dn, then we do the following. Let F be a distortion d embedding of G into
C, if one exists. We find ∆(G) in O(n) time. By Observation 2.5, if ∆(G) > 2d then we
report no F exists. Otherwise, we try to find an embeddable sequence of partial embeddings,
according to Lemma 3.8. We first fix Ψ : W → S0 . Let FΨ be the set of all possible partial
embeddings with respect to
 Ψ from G to C. By Observation 3.13 and Definition 3.14, |FΨ | ≤
O N · n · (4d(2d + 2))2d+2 . Then we make the following construction:
(i) Construct a directed graph G, where V (G) = FΨ ∪ {S, D} and E(G) = E1 ∪ E2 ∪ E3 , where
E1 = {(Φa , Φb ) : Φb succeeds Φa w.r.t. Ψ}
E2 = {(S, Φ1 ) : L(Φ1 ) = ∅, R(Φ1 ) = V (G) \ (DomΦ1 ∪ W )}
E3 = {(Φt , D) : L(Φt ) = V (G) \ (DomΦt ∪ W ), R(Φt ) = ∅}.
(ii) Then we check for the existence of a directed path from S to D. This implies that there
is a directed path from some Φ1 ∈ FΨ to some Φt ∈ FΨ in G such that conditions (ii) and
(iii) of Definition 3.7 are satisfied. If such a path exists, then there exists an embeddable
sequence, say Φ1 , . . . , Φt , of feasible partial embeddings with respect to Ψ. Report ΦΠ as
F , where Π = {Φi : i ∈ [t]}.
Otherwise, there does not exist an embeddable sequence of feasible partal embeddings with
respect to Ψ.

15

If there does not exist an embeddable sequence of feasible partal embeddings with respect to
Ψ, then we conclude that we cannot have a non-contracting and distortion d embedding of G
into C. Observe that we execute the above procedure for all possible
Ψ in the worst case. But,

the total number of possible Ψ is at most O n · (4d(2d + 2))2d+2 by Lemma 3.16. The number
of vertices in graph G is at most O N · n · (4d(2d + 2))2d+2 . Every vertex of G has outdegree
at most O(d2d ). This is because, if fb succeeds fa , then fb is determined by fa along with the
condition (i) of Definition 3.4. Similar to [FFL+ 13], we can test whether a partial embedding
2
succeeds another using a prefix tree like data structure
 in O(d ) time. So, the total running
2
2d
2d+2
time of Step-(i) is O d · d · N · n · (4d(2d + 2))
. We can test the existence of a path of
the mentioned type in Step-(ii), by running the DFS algorithm in O N
· n · (4d(2d + 2))2d+2

time. Hence, our algorithm takes O d2 · d2d · N · n · (4d(2d + 2))2d+2 time for each Ψ and
O N · n2 · d2d+2 · (4d(2d + 2))4d+4 in total. As N ≤ 2dn, the stated bound of the time complexity follows.
A Note on Embedding into lines Note that we can design a similar algorithm for embedding into lines. An FPT algorithm for embedding a graph metric (G, DG ) into a graph
metric (H, DH ), where H is a line, already exists in [FFL+ 13]. A key observation made for
embedding into lines was that it is enough to search for a pushing embedding of G into H.
For a non-contracting distortion d embedding F , let v1 , v2 , . . . , vn be an ordering of the vertices such that F (v1 ) < F (v2 ) < . . . < F (vn ). Then F is called a pushing embedding if
DH (f (vi ), f (vi+1 ) = DG (f (vi ), f (vi+1 )) for all 1 ≤ i ≤ n − 1. Our algorithm does not assume
pushing embeddings and therefore will work even for embedding into lines, where the maps of
certain vertices are already fixed. Specifically in this part, we mention two results which will be
useful for us in Section 6.
A line with N vertices can be thought to have vertices named {1, 2, . . . , N }.
Lemma 3.18. Let (G, DG ) and (H, DH ) be two graph metrics on n and N vertices,respectively.
Let a1 , a2 be two positive integers such that a1 + a2 ≤ N . Let Z1 = {1, 2, . . . , a1 } and Z2 =
{N − a2 + 1, N − a2 + 2 . . . , N }. Let Ψ1 : U1 → Z1 and Ψ2 : U2 → Z2 be two fixed noncontracting distortion d embeddings of two disjoint sets U1 , U2 ⊆ V (G). Then there is an FPT
algorithm to determine whether there exists a non-contracting distortion d embedding of G into H

that extends Ψ1 and Ψ2 . The running time of the algorithm is O n2 · d2d+3 · (4d(2d + 2))2d+2 .

Proof. Without loss of generality, assume that there exists a vertex of G mapped to 1 and N .
If N > 2dn, then there exists an induced maximal subpath P of H such that all vertices of G
are mapped into it and |V (P )| > 2dn. This is impossible by Observation 2.6. Hence, there does
not exist a desired embedding if N > 2dn.
Now assume that N ≤ 2dn. The algorithm is very similar to the algorithm for embedding
into a cycle. As before, for any ℓ ∈ {1, 2, . . . , N }, Sℓ = {ℓ − (d + 1), . . . , ℓ + (d + 1)}. We explicitly
define a feasible partial function.
Definition 3.19. (i) For an a ∈ V (H), a partial embedding of U ⊆ V (G), with respect to Ψ1
and Ψ2 , is a function fa : U → Sa . As before, U is referred to as Domfa and a is referred
to as mid(fa ).
[p,q]

(ii) Domfa is the set of vertices of U that are mapped into {a + p, . . . a + q}, where −(d + 1) ≤
p ≤ q ≤ (d + 1). Domxfa is the set of vertices of U that are mapped into {a + x}.
[−(d+1),−1]

[1,(d+1)]

(iii) DomL
and DomR
. L(fa ) (R(fa )) is the union of the
fa = Domfa
fa = Domfa
vertex sets of connected components of V (G) \ (U1 ∪ U2 ∪ U ) that have neighbours in
R
DomL
fa (Domfa ).

16

Definition 3.20. Let fa : U → Sa be a partial embedding with respect to Ψ1 and Ψ2 , where
U ⊆ V (G). Then f is said to be feasible with respect to Ψ1 and Ψ2 , if it satisfies the following
conditions.
(i) U 6= ∅, U ∩ U1 = U ∩ U2 = ∅ and Sa ∩ Z1 = Sa ∩ Z2 = ∅.
(ii) fa is a non-contracting distortion d embedding of U .
(iii) For every pair u ∈ U and w ∈ U1 , DH (fa (u), Ψ1 (w)) is neither contracting nor expanding
by a factor of more than d. A similar condition holds for every pair u ∈ U and w ∈ U1 ,
(iv) If u is a neighbour of a vertex in Dom0fa , then fa (u) ∈ Sa .
(v) L(fa ) ∩ R(fa ) = ∅.
The definition of succession of feasible partial embeddings and embeddability of a sequence of
partial embeddings are analogous to Definitions 3.4 and 3.7. We can also state results analogous
to Lemma 3.5 and 3.8.
What remains is to bound the number of partial embeddings. By Observation 2.5, ∆(G) ≤ 2d
if G is embeddable into H. The structure of a partial embedding for embedding into lines
is same as that described in Observation 3.13. Therefore, Lemma 3.15 is true in this case
as well. Given Ψ1 and Ψ2 , analogous to Lemma 3.16, the total number of feasible partial
embeddings with respect to Ψ1 and Ψ2 is O(N ·n(4d(2d+ 2))2d+2 ). Now, we design an algorithm
similar to that given in Theorem 3.17. The correctness of the algorithm can be argued in
a similar way as that in Theorem
 3.17. The running time of the algorithm turns out to be
2d+2
2d+2
O N ·n·d
· (4d(2d + 2))
. As N ≤ 2dn, the claimed bound of the time complexity
holds. follows.
We also obtain the following corollary using similar analysis.
Corollary 3.21. Let (G, DG ) and (H, DH ) be two graph metrics on n and N vertices,respectively.
Let a1 be a positive integer such that a1 ≤ N . Let Z1 = {1, 2, . . . , a1 }. Let Ψ1 : U1 → Z1 be
a fixed non-contracting distortion d embedding of U1 ⊆ V (G). Also consider a fixed vertex
v ∈ V (G). Then there is an FPT algorithm to determine whether there exists a non-contracting
distortion d embedding F of G into H that extends Ψ1 and where for all u ∈ V (G), F (u) ≤ F (v).
The running time of the algorithm is O n2 · d2d+3 · (4d(2d + 2))2d+2 .

Proof. Without loss of generality, assume that there exists a vertex of G that is mapped to 1.
Then, by Observation 2.6, there does not exist any vertex of G that is mapped to some j > 2dn.
So, we delete all vertices of H that are at a distance more than 2dn from 1. Call the new graph
H ′ . Observe that finding a required embedding of G into H is equivalent to finding a required
embedding of G into H ′ . Let N ′ denote the number of vertices in H ′ . Note that N ′ ≤ 2dn.
The definition of feasible partial embeddings, succession of feasible partial embeddings, embeddability of a sequence of partial embeddings are similar to the definitions in Lemma 3.18.
Similarly, we can also argue the correctness of finding an embeddable sequence of partial embeddings and a bound on the number of feasible partial embeddings. The FPT algorithm will be
very similar to that of Lemma 3.18. The only change is that now there is an added condition
that v is the last vertex that gets mapped in the line H. However, this can be ensured very
easily, by making modifications in the directed graph G associated with partial embeddings, that
was built for the algorithms of Theorem 3.17 and of Lemma 3.18. The running time of the
algorithm is O N ′ · n · d2d+2 · (4d(2d + 2))2d+2 . As N ′ ≤ 2dn, the claimed bound of the time
complexity follows.
As mentioned earlier, these algorithms on embedding into the line will be useful to us in
Section 6.
17

3.2

Embedding a weighted graph into a cycle

In this part, we consider embedding weighted graph metrics into cycles. Let G be a weighted
graph and w : E(G) → R be the weight function. The objective is to either find a non-contracting
distortion d embedding of G into C or decide that no such embedding exists. We will call this
problem Weighted Graph Metric Embedding. In general this problem is NP-complete,
which we show shortly. However, we first give an FPT algorithm by taking M = max w(e) as
e∈E(G)

a parameter along with d. The terminologies and the algorithm discussed in Section 3.1, can
be extended to the an FPT algorithm for embedding of a weighted graph metric G into a cycle,
parameterized by M and d.
FPT algorithm taking d and M as parameter
We have an observation analogous to Observation 3.1, with the change that |V (S)| ≥ (2d +
4)M . Sℓ = {ℓ − (dM + 1), . . . , ℓ + (dM + 1)}. We first fix a function Ψ : W → S0 . We define a
partial embedding as fa : U → Sa , where U ⊆ V (G) and other terminologies in Definition 3.2
can be defined in a similar manner. We can define the notion of feasible partial embedding,
how a feasible partial embedding succeeds another and what an embeddable sequence of feasible
partial embeddings is similarly. We can also state results analogous to Lemma 3.5 and 3.8.
Analogous to Observation 2.5, we check whether ∆(G) ≤ 2dM . If this is false, we conclude
that we cannot embed the given graph into the cycle C with distortion d. If the condition is true,
we execute an algorithm similar to that explained in the proof of Theorem 3.17. By following similar analysis done in Lemma 3.15 and Lemma 3.16, the total number of feasiblepartial embeddings
2dM +2 and the total numwith respect to some Ψ can be bounded by O n · N · (4dM (2dM + 2))

2dM
+2
ber of possible Ψ can be bounded by O n · (4dM (2dM + 2))
. One can easily go through
the analogous steps explained in Theorem 3.17 and verify that the time complexity of our algo
rithm to embed a weighted graph into a cycle C is O n2 · N · (dM )2dM +2 (4dM (2dM + 2))4dM +4 .
Using Observation 2.6 and an arguement similar to that given in the first paragraph of the proof
of Theorem 3.17, we can assume that N ≤ 4dM n. Hence, the time complexity of our algorithm
to embed a weighted graph into a cycle C is O n3 (dM )2dM +3 (4dM (2dM + 2))4dM +4 .

Theorem 3.22. Let G be the given weighted graph on n vertices such that M = max w(e),
e∈E(G)

and C be a cycle. Then there exists an algorithm that either finds a non-contracting distortion d
embedding of G into C or concludes that there does not exist such
 an embedding. The running
time of the algorithm is O n3 (dM )2dM +3 (4dM (2dM + 2))4dM +4 .
Hardness proof

Consider the Weighted Graph Metric Embedding problem where the input metric
(G, DG ) has an associated weight function w : E(G) → R≥0 and the distortion is d > 2. We use
the notation W (G) to denote maximum weight over all edges of the graph G. In this section,
we prove the following Theorem.
Theorem 3.23. Weighted Graph Metric Embedding is NP-complete for any rational
d > 2. The problem remains NP-Complete even if W (G) ≤ |V (G)|.
To prove the theorem, we need the following observation, which is the weighted analogue of
Observation 2.6, and a known result of Fellows et al. [FFL+ 13].
Observation 3.24. Let F be a non-contracting distortion d embedding of a weighted graph G,
into H such that H is either a line or a cycle. Let P ′ be the maximal subpath of H such that
F (x) ∈ V (P ′ ) for all x ∈ V (G). Then |V (P ′ )| ≤ 2dM n, where |V (G)| = n and W (G) = M .

18

Proof. For any two vertices x, y ∈ V (G), DG (x, y) ≤ M (n − 1). This implies DH (F (x), F (y)) ≤
dM (n − 1). Let u ∈ V (H) be such that some vertex of G is mapped to it. Observe that any
other vertex of H that has a vertex of G as its pre-image, must be within a distance of dM (n − 1)
from u in H. As the degree of u is at most 2, the result follows.
Proposition 3.25 ([FFL+ 13]). Let G be the given graph with weight function w, and L be a
given line having sufficiently large number of vertices. Weighted Graph Metric Embedding
on the instance (G, w, L, d) is NP-complete for any d > 2. The problem remains NP-Complete
even if w(G) ≤ |V (G)|.
Proof of Theorem 3.23. Clearly the problem is in NP. To show NP-hardness, we reduce the
Weighted Graph Metric Embedding problem for cycles from the Weighted Graph Metric Embedding problem for lines. We give the reduction for a special case where w(G) ≤
|V (G)| = n and |V (C)| = 4dn2 + 1. We need to prove that there exists an embedding of G into
L if and only if there exists an embedding of G into C.
Let F be a required embedding from G to L. By Observation 3.24, there exists a maximal
subpath P ′ of 2dn2 vertices of L such that F (x) ∈ V (P ′ ) for all x ∈ V (G). Let Q′ be a
maximal subpath of 2dn2 vertices of C and Φ be a bijection from P ′ to Q′ such that DL (u, v) =
DC (Φ(u), Φ(v)) for any u, v ∈ V (P ′ ). Such a bijection exists as |V (C)| = 4dn2 +1. Now consider
the function F ′ from V (G) to V (C) defined as follows. For any x ∈ V (G), F ′ (x) = Φ(F (x)).
Since |V (C)| > 2 |V (P ′ )| = 2 |V (Q′ )|, F ′ is a non-contracting and distortion d embedding of G
into C.
For the converse part, let F be a non-contracting distortion d embedding from G to C. By
Observation 3.24, there exists a maximal subpath Q′ of 2dn2 vertices of C such that F (x) ∈ V (Q′ )
for all x ∈ V (G). Let P ′ be a subpath of 2dn2 vertices of L and Ψ be a bijection from Q′ to
P ′ such that DC (u, v) = DL (Ψ(u), Ψ(v)) for any u, v ∈ V (Q′ ). Such a bijection exists as
|V (C)| = 4dn2 + 1. Now consider the function F ′ from V (G) to V (C) defined as follows. For
any x ∈ V (G), F ′ (x) = Ψ(F (x)). Since |V (C)| > 2 |V (Q′ )| = 2 |V (P ′ )|, it follows that F ′ is a
non-contracting and distortion d embedding of G into L.

4

Bijective Graph Metric Embedding for bounded treewidth
graphs

In this section, we consider the bijective Graph Metric Embedding problem for the graph
class G, which consists of graphs with treewidth at most α for a given constant α. Let (G, DG ) be
the input connected graph metric to be embedded into the output graph metric (H, DH ), where
H ∈ G. Also, |V (G)| = |V (H)|. We design an FPT algorithm for the problem parameterized
by the distortion d and the maximum degree ∆(H). We will also refer to ∆(H) as ∆. Again,
the strategy is to define feasible partial embeddings locally, and a notion of succession amongst
partial embeddings such that we can build towards a bijective non-contracting distortion d
metric embedding of G into H. We use a tree decomposition of H to define the notions of
partial embeddings and successions. We also use the tree decomposition to design a dynamic
programming algorithm to derive a non-contracting distortion d embedding of G into H from
a set of partial embeddings that is computed in FPT time. The ideas used to design this
algorithm is essentially similar to those used for designing an FPT algorithm for embedding
into trees with bounded degree [FFL+ 13]. However, we need to modify the definitions and the
algorithm according to the need of our problem.
Let T = (T, {Xu }u∈V (T ) ) be a nice tree decomposition [CFK+ ] of H. Recall that Xr = ∅ and
Xℓ = ∅, where r is the root of the tree T and ℓ is any leaf of T . We use NT (u), CT (u) to denote
the set of neighbours and children of u in T , respectively. Let T
Su denote the subtree rooted at
Xv , i.e, the vertices present
the node u ∈ V (T ) and Hu denote the subgraph induced by
v∈V (Tu )

19

in the bags corresponding to the nodes present in Tu . Note that Hr = H. For a v ∈ NT (u), we
denote Tu (v) as the subtree
containing v in the graph T \ {u} and Huv as the subgraph induced
S
on all vertices in
Xw . For x ∈ V (H), B(x, d + 1) is the set of vertices of H that are
w∈V (Tu (v))
S
B(x, d + 1).
at distance of at most d + 1 from x. For u ∈ V (T ), B(u, d + 1) =
x∈Xu

Next, we define partial embeddings with respect to the sets B(u, d + 1), u ∈ V (T ). For ease
of notations, we abuse the usual set theoretic terminology by using A \ a to denote A \ {a}.

Definition 4.1. (i) A u-partial embedding of U ⊆ V (G) is a function fu : U → B(u, d + 1),
where u ∈ V (T ) and U ⊆ V (G). We refer to U as Domfu .
[p,q]

(ii) Let v ∈ NT (u). Then Domfu (v) = {x ∈ U : fu (x) ∈ V (Huv )}, Domfu
[p,q]
p ≤ DH (y, fu (x)) ≤ q for some y ∈ Xu }, Domfu (v)
[k,k]
[0,0]
Domfu (v) for k ≥ 1 and Dom0fu = Domfu = Xu .

=

[p,q]
Domfu

= {x ∈ U :

∩ Domfu (v), Domkfu (v) =

(iii) M [fu , v] is the union of vertex sets of all connected components of G \ Domfu that have
neighbours in Domfu (v).
The feasibility of partial embeddings in order for them to build up to a metric embedding is
defined as below.
Definition 4.2. A u-partial embedding fu : U → B(u, d+1) is feasible if it satisfies the following
conditions.
(i) fu is a non-contracting and distortion d embedding of U into B(u, d + 1).
(ii) M [fu , v] ∩ M [fu , w] = ∅ for any v, w ∈ NT (u) and v 6= w.
(iii) All neighbours of Dom0fu are in U .
Similarly, we define succession of partial embeddings, keeping in mind that we want to find
a set of partial embeddings and put them together to form a non-contracting distortion d metric
embedding.
Definition 4.3. Let fu and fv be two feasible partial embeddings and v ∈ CT (u). Then fv
succeeds fu if the following conditions are satisfied.
(i) Domfu ∩ Domfv = Domfv if u is an introduce node and Domfu = Domfv , otherwise.
(ii) ∀x ∈ Domfu ∩ Domfv , fu (x) = fv (x).
S
(iii) M [fu , v] =
(M [fv , w] ∪ Domd+1
fv (w)).
w∈NT (v)\u

(iv) M [fv , u] =

S

w∈NT (u)\v

(M [fu , w] ∪ Domd+1
fu (w)).

Next, we describe how we put together feasible partial embeddings. In the case of cycles, we
used the structure of the cycle. Here, we use the structure of the tree T .
Definition 4.4. Let Π = {fu : u ∈ V (T )}. Π is said to be an embeddable set of partial
embeddings if the following are satisfied.
(i) Each fu is feasible, u ∈ V (T ).
(ii) Let us take any u ∈ V (T ). Then for every v ∈ CT (u), fv succeeds fu .
The next Lemma shows that it is enough to design an algorithm to find an embeddable set
of partial embeddings.
20

Lemma 4.5. Let G be the given graph to be embedded into H such that |V (G)| = |V (H)|. G
has a bijective, non-contracting and distortion d embedding into H if and only if there exists an
embeddable set of partial embeddings.
Proof. Let F be a non-contracting distortion d embedding of G into H. For u ∈ V (T ), consider
fu to be F restricted to the preimage of B(u, d + 1). Let Π = {fu : u ∈ V (T )}. It is easy to
verify that Π is an embeddable set of partial embeddings.
For the converse part, Let Π = {fu : u ∈ V (T )} be an embeddable set of partial embeddings.
Let us construct F = ΦΠ , as in Definition 3.6. First consider the following claims, which we
prove later.
Claim 4.6. For every x ∈ V (G), there exists some fu such that x ∈ Domfu .
Claim 4.7.

(a) The subgraph of T induced by Ax = {u ∈ V (T ) : x ∈ Domfu } is connected.

(b) If x ∈ Domfu ∩ Domfv , then fu (x) = fv (x).
By Claim 4.6 and Claim 4.7, F is a bijective function from V (G) to V (H) as |V (G)| = |V (H)|.
We are done with the proof of the converse part by the following claims, which we prove later.
Claim 4.8. F , as an embedding of G into H, has expansion at most d.
Claim 4.9. F is a non-contracting embedding of G into H.

Assume that
Proof of Claim 4.6. If x ∈ DomfS
r , r is the root of the tree T , we are done.
M [fr , v]. By condition (ii) of Definition 4.2, we can say
x∈
/ Domfr . This implies x ∈
v∈CT (r)

that there exists exactly one v1 ∈ CT (r) such that x ∈ M [fr , v1S
]. The choice of v1 implies that
(M [fv1 , w] ∪ Domd+1
x∈
/ M [fv1 , r]. Now, by condition (iii) of Definition 4.3, x ∈
fv (w)).
1

w∈NT (v1 )\r

If x ∈ Domfv1 , then we are done. Otherwise, x ∈ M [fv1 , v2 ] for exactly one v2 ∈ NT (v1 ) \ r,
due to condition (ii) of Definition 4.2. The choice of v2 implies that x ∈
/ M [fv2 , v1 ]. Again
by condition (iii) of Definition 4.3 and condition (ii) of Definition 4.2, we can say that either
x ∈ Domfv2 , or x ∈ M [fv2 , v3 ] for exactly one v3 ∈ NT (v2 ) \ v1 .
In both cases, we proceed as before. Either we
S get a non-leaf node u ∈SV (T ) such that
M [fvi , ℓ] = ∅
M [fvi , ℓ]. However,
x ∈ Domfu , or a leaf vi such that x ∈ Domfvi ∪
ℓ∈CT (vi )

ℓ∈CT (vi )

as vi is a leaf. So, x ∈ Domfvi .

Proof of Claim 4.7. (a) We give a proof by contradiction. Let us consider u, v ∈ V (T ) such
/ E(T ). Let P = u1 . . . uk , k ≥ 3, be the path from
that x ∈ Domfu ∩ Domfv and (u, v) ∈
u = u1 to v = uk in T such that for some i, 1 < i < k, x ∈
/ Domfui . By Definition 4.1,
x ∈ M [fui , ui+1 ] and x ∈ M [fui , ui−1 ]. In other words, both ui−1 , ui+1 ∈ NT (ui ) and
x ∈ M [fui , ui+1 ] ∩ M [fui , ui−1 ]. This contradicts the fact that fui is a feasible partial
embedding.
(b) The statement follows from Part (a) and by using the definition of succession, i.e., Definition 4.3.
Proof of Claim 4.8. Consider an edge (x, y). Let F (x) ∈ Xu for some u ∈ V (T ). Observe that
in this case x ∈ Dom0fu . By condition (iii) of Definition 4.2, y ∈ Domfu . Also, note that fu is a
feasible partial embedding. This implies DH (F (x), F (y)) ≤ d.
Therefore, for any edge (x, y) ∈ E(G), DH (F (x), F (y)) ≤ d. Now, we apply induction similar
to that in the proof of Claim 3.11, and get the required result.

21

Proof of Claim 4.9. We need to show that DG (x, y) ≤ DH (F (x), F (y)) for any x, y ∈ V (G).
We prove it by the method of induction on DH (F (x), F (y)). For the base case consider
DG (F (x), F (y)) = 1, or (F (x), F (y)) ∈ E(H). By the definition of tree decomposition, there
exists u ∈ V (T ) such that F (x), F (y) ∈ Xu . Now using the fact that both x, y ∈ Domfu and
fu is a feasible partial embedding of Domfu , DG (x, y) ≤ DH (F (x), F (y)). Hence, the base case
holds.
For the inductive step assume that DG (x, y) ≤ DH (F (x), F (y)) holds for any x, y such that
DH (F (x), F (y)) < ℓ. Now, we have to show for the case DH (F (x), F (y)) = ℓ > 1. There
exists u ∈ V (T ) such that F (x) ∈ Xu . Let fu : U → B(u, d + 1). The shortest F (x) to
F (y) path must contain a vertex a ∈ V (H) such that a ∈ B(u, d + 1) and DH (F (x), F (y)) =
DH (F (x), a) + DH (a, F (y)). Let a = F (w) for some w ∈ V (G). Such a w exists as the
embedding F is a bijection. By the induction hypothesis, DG (x, w) ≤ DH (F (x), F (w)) and
DG (w, y) ≤ DH (F (w), F (y)). Hence, DG (x, y) ≤ DH (F (x), F (y)).
Putting everything together, we have an FPT algorithm for the problem.
Theorem 4.10. Let G, H be two given graphs such that |V (G)| = |V (H)| = n, the maximum
degree of H is ∆ and tw(H) ≤ α. Then there exists an algorithm that either finds a bijective
non-contracting distortion d embedding of G into H or decides no such embedding exists in
O(αd2 )
time.
O(α2 nα+3 ) · ∆d+1 · (α∆d+1 )∆
Proof. Due to Observation 2.5, if ∆(G) > ∆d , then there does not exist an embedding from G
to H. So, assume that ∆(G) ≤ ∆d .
Let T = (T, {Xu }u∈V (T ) ) be a nice tree decomposition. Note that |Xu | ≤ α, Xr = ∅ and
Xℓ = ∅, where r is the root of T and ℓ is any leaf of T . We do a dynamic programming. For
each u ∈ V (T ), we create a binary list of all possible feasible u-partial embeddings from some
subset of V (G) to B(u, d + 1). For any leaf ℓ ∈ V (T ), make all entries to be true. For the root
r, just create one entry in the list, whose value is to be assigned. Let u be a non-leaf node. Let
fu be a feasible partial embedding. Suppose for every v ∈ CT (u), there exists a feasible partial
embedding fv and fv succeeds fu . Then assign the corresponding entry of fu to be true. Assign
true to the corresponding entry of r if there exists a feasible partial embeddings for each child
of r. By Lemma 4.5, one can observe that the algorithm is correct.
For the running time, we have to bound the total number of feasible partial embeddings.
Observation 4.11. The total number of u-partial embedding is at most nα · (α · ∆d+1 )∆

O(α·d2 )

.

Proof. Let us consider a u-partial embedding fu from some subset of V (G) to B(u, d + 1).
Observe that |B(u, d + 1)| ≤ α.∆d+1 . As we are considering non-contracting embeddings, the
domain of fu must be contained in the union of at most α balls of radius 2d + 2, where each ball
2
is centered at some vertex of G. As ∆(G) ≤ ∆d , the domain of fu can contain at most ∆O(α.d ) .
So, the total number of feasible u-partial embeddings is at most nα · (α · ∆d+1 )∆

O(α·d2 )

.

Let fu and fv be given such that
 v ∈ CT (u). From Definition 4.3, one can decide whether
d+1
fv succeeds fu in time O n.α.∆
.
Recall that T is a nice tree decomposition, which implies |V (T )| = O(α.n) and ∆(T ) = O(1).
O(α·d2 )

partial embeddings. Note that the
So, observe that there are at most α.n.nα · (α · ∆d+1 )∆
bags corresponding to two adjacent vertices of T , differ by at most one vertex of H. So, each
∆O(α.d2 )
number of successions.
feasible partial embedding can take part in at most n · α · ∆d+1
Hence, the total running time is O(α2 nα+3 ) · ∆d+1 · (α∆d+1 )∆

22

O(αd2 )

.

A note on bijective Gen-Graph Metric Embedding for bounded treewidth graphs
Assume that the input of the Red Blue Graph Metric Embedding problem is such that the
output metric (H, DH ) has the following property: given V (H) = R⊎ B, any path of length d+ 1
in H has at least one internal vertex in R. Also, we want to find a non-contracting distortion d
embedding that is a bijection between V (G) and R. For this variant of the Red Blue Graph
Metric Embedding, the above algorithm can be easily modified to give a solution. Most details
of the above algorithm remain the same. Note that for a u ∈ V (T ), a u-partial embeddings of
U ∈ V (G) is a function fu : U → B(u, d+ 1)∩ R. We explicitly prove the equivalent of Claim 4.9,
since that is the only major place of difference.
We restate the claim for a map F obtained from an embeddable set of partial embeddings,
as in Lemma 4.5.
Claim 4.12. F is a non-contracting embedding of G into H.
Proof. We need to show that DG (x, y) ≤ DH (F (x), F (y)) for any x, y ∈ V (G). We prove it by
the method of induction on DH (F (x), F (y)). For the base case consider DG (F (x), F (y)) ≤ d.
By the definition of tree decomposition, there exists u ∈ V (T ) such that F (x), F (y) ∈ B(u, d+1).
Now using the fact that both x, y ∈ Domfu and fu is a feasible partial embedding of Domfu ,
DG (x, y) ≤ DH (F (x), F (y)). Hence, the base case holds.
For the inductive step assume that DG (x, y) ≤ DH (F (x), F (y)) holds for any x, y such that
DH (F (x), F (y)) < ℓ. Now, we have to show for the case DH (F (x), F (y)) = ℓ > 1. There exists
u ∈ V (T ) such that F (x) ∈ Xu . Let fu : U → B(u, d + 1). Since ℓ ≥ d + 1, the shortest F (x)
to F (y) path must contain a vertex a ∈ R such that a ∈ B(u, d + 1) and DH (F (x), F (y)) =
DH (F (x), a)+DH (a, F (y)). Let a = F (w) for some w ∈ V (G). Such a w exists as the embedding
F is a bijection between V (G) and R. By the induction hypothesis, DG (x, w) ≤ DH (F (x), F (w))
and DG (w, y) ≤ DH (F (w), F (y)). Hence, DG (x, y) ≤ DH (F (x), F (y)).
Thus, we obtain an FPT algorithm for this variant of Red-Blue Graph Metric Embedding. Due to Lemma 2.4 and Proposition 2.2, we obtain the following result.
Corollary 4.13. Assume that the bijective Gen-Graph Metric Embedding problem takes
as input two graph metrics (G, DG ) and (H, DH ) such that |V (G)| = |V (H)| = n. Let the
maximum degree of H be ∆ and tw(H) ≤ α. Then there exists an algorithm that either finds a
bijective distortion d embedding for this instance of bijective Gen-Graph Metric Embedding
O(αd2 )
time.
or decides that no such embedding exists in O(α2 nα+11 ) · ∆d+1 · (α∆d+1 )∆

5

Graph Metric Embedding and connected treewidth

In this Section, we will look at the Graph Metric Embedding problem with respect to
the added parameters of treewidth and longest geodesic cycle of the output graph metric. Let
(G, DG ) be the input connected graph metric to be embedded into (H, DH ). We show that this
problem is FPT, when parameterized by the distortion d, the treewidth tw(H) = α, the length ℓg
of the longest geodesic cycle of H, and the maximum degree ∆(H) = ∆. From [DM17] it can be
shown that for a graph with longest geodesic cycle ℓg , a tree decomposition of treewidth α′ can
′
be converted into a connected tree decomposition of width α′ + α2 (ℓg (α′ − 2) − 1) in polynomial
time. Since trees have constant connected treewidth, our algorithm is a generalization of the
FPT algorithm for Graph Metric Embedding for trees, parameterized by distortion d and
maximum degree ∆ [FFL+ 13]. As before, we employ a dynamic programming to build a noncontracting distortion d metric embedding using a set of partial embeddings that are computed
in FPT time.
Let (G, DG ) be a graph metric to be embedded into (H, DH ). Here the parameters are
the treewidth α of H, the length of the longest geodesic cycle ℓg in H, the distortion d and
23

the maximum degree ∆ of H. Let T be a nice tree decomposition of H with width µ. Since
from [DM17] H has a connected tree decomposition of width µ, we may assume that the nice
tree decomposition is derived from the connected tree decomposition [CFK+ ] and therefore the
maximum distance between any two vertices inside a bag in T is Γ ≤ µ.
We borrow the definition of feasible partial embeddings and succession of feasible partial
embeddings from Definitions 4.1, 4.2, and 4.3.
Unlike the arguments of Section 4, now ensuring non-contraction for a non-contracting distortion d metric embedding F is more elaborate. Local non-contraction no longer implies global
non-contraction. This problem was dealt with in [FFL+ 13] by introducing the notion of types.
For our algorithm too, for a vertex u ∈ V (T ) we need to define a type for every vertex of V (G)
that is mapped into the subgraph Hu , to indicate how it behaves with the rest of the graph.
More specifically, let x ∈ V (G) be a vertex that is mapped to F (x) ∈ V (Hu ). Consider any
other vertex y ∈ V (G) such that F (y) is a vertex from V (H) \ V (Hu ). Then, a type relates
DH (F (x), F (y)) with DG (x, y). The crucial observation here is that (i) the shortest path between F (x) and F (y) must pass through a vertex in Xu , and (ii) the shortest path between x
and y in G is such that there is at least one internal vertex x′ such that F (x′ ) ∈ B(u, d + 1), as
otherwise F does not have distortion d. Thus, the types store information of the interaction of
vertices of the graph seen so far with the boundary vertices, and this is enough to ensure global
non-contraction.
Definition 5.1. Let u ∈ V (T ), fu be a feasible partial embedding and Xu = {u1 , . . . , uk },
1 ≤ k ≤ αc . Then
(i) For v ∈ NT (u) and ui ∈ Xu , [fu , v, ui ] type is a function tui : Domfu (v) → {∞, 2Γ + 3d +
3, Γ + d + 1, . . . , −(Γ + d + 1)}.
(ii) A [fu , v] type t is a tuple (tui , . . . , tuk ), where tui is a [fu , v, ui ] type.
(iii) A [fu , v] type-list is a set of [fu , v] types.
Intuitively, we want to define a type corresponding to each vertex mapped into Hu . However,
this blows up the number of types. In order to handle this, it can be shown that we do not
need to remember the type of each vertex, and that it is enough to only remember the type of
vertices ”close to” the vertices in Xu . Now we present the formal arguments. To bound the
total number of possible types, we define a function β as follows: β(k) = k if k < 2Γ + 3d + 3,
and β(k) = ∞ otherwise. In the following definitions, treat β(k) = k and the definition of β will
be clear while we prove our claims.
Definition 5.2. Let us consider u ∈ V (T ), v ∈ NT (u). Let fu be a feasible partial embedding
and L be a [fu , v] type-list. Then L is said to be compatible with Domfu (v) if the following
condition is satisfied.
• For each x ∈ Domfu (v) there exists a type t ∈ L, such that for each y ∈ Domfu (v), for all
ui ∈ Xu DH (fu (x), ui ) − DG (x, y) = tui (y) .
Definition 5.3. Let u ∈ V (T ) and fu be a feasible partial embedding. Also consider v, w ∈
NT (u) along with a [fu , v] type-list L1 and a [fu , w] type-list L2 such that v 6= w. Then L1
and L2 agree if the following condition is satisfied for all ui ∈ Xu .
• For every t1 ∈ L1 and t2 ∈ L2 , there exists x ∈ Domfu (v) and y ∈ Domfu (w) such that
tu1 i (x) + tu2 i (y) ≥ DG (x, y) for all ui ∈ Xu .
Next, we define a state with respect to a vertex in T .
Definition 5.4. Let u ∈ V (T ). A u-state constitutes of a feasible partial embedding fu , a
[fu , v] type-list L[fu , v] for each v ∈ NT (u).
24

Notice that it is no longer enough to consider feasibility and succession of partial embeddings.
We also need to take care of the types of vertices. Therefore, we define feasibility and succession
of states.
Definition 5.5. A u-state is said to be feasible if the following conditions are satisfied.
(i) L[fu , v] is compatible with Domfu (v), for each v ∈ NT (u).
(ii) L[fu , v] agrees with L[fu , w], for any v, w ∈ NT (u) and v 6= w.
Definition 5.6. Let u ∈ V (T ) and v ∈ CT (u). Let Su , Sv be feasible u-state and v-state,
respectively. Sv is said to succeed Su if the following properties hold.
(i) fv succeeds fu .
(ii) For every w ∈ NT (v) \ u and a type t1 ∈ L[fv , w] there exists a type t2 ∈ L[fu , v]
satisfying the following conditions.
(a) For all x ∈ Domfu (v) ∩ Domfv (w) and a ∈ Xu ∩ Xv , ta2 (x) = ta1 (x).
(b) For all x ∈ Domfu (v) ∩ Domfv (w) and a ∈ Xu \ Xv ,


b
a
t2 (x) = β min (DH (a, b) + t1 (x)) .
b∈Xv

(c) For all x ∈ Domfu (v) \ Domfv (w) and a ∈ Xu ∩ Xv ,


a
a
(t1 (y)) − DG (x, y)) .
t2 (x) = β
max
y∈Domfv (w)

(d) For all x ∈ Domfu (v) \ Domfv (w) and a ∈ Xu \ Xv ,



b
a
.
min (DH (a, b) + t1 (y)) − DG (x, y)
t2 (x) = β
max
y∈Domfv (w)

b∈Xv

(iii) For every w ∈ NT (u) \ v and a type t1 ∈ L[fu , w] there exists a type t2 ∈ L[fv , u]
satisfying the following conditions.
(a) For all x ∈ Domfv (u) ∩ Domfu (w) and a ∈ Xu ∩ Xv , ta2 (x) = ta1 (x).
(b) For all x ∈ Domfv (u) ∩ Domfu (w) and a ∈ Xv \ Xu ,


b
a
t2 (x) = β min (DH (a, b) + t1 (x)) .
b∈Xu

(c) For all x ∈ Domfv (u) \ Domfu (w) and a ∈ Xu ∩ Xv , ta2 (x) = ta1 (x).
(d) For all x ∈ Domfv (u) \ Domfu (w) and a ∈ Xv \ Xu ,



.
min (DH (a, b) + tb1 (y)) − DG (x, y)
ta2 (x) = β
max
y∈Domfu (w)

b∈Xu

Now, we define the embeddability of a set of feasible states.
Definition 5.7. For u ∈ V (T ), let Su denote a u-state. The set {Su : u ∈ V (T )} is said to be
an embeddable set of feasible states if the following conditions are satisfied.
(i) For each u ∈ V (T ), Su is a feasible state.
(ii) For u ∈ V (T ) and v ∈ CT (u), Sv succeeds Su .
25

The above definitions are enough to show the relation between the existence of a noncontracting distortion d embedding of G into H and the existence of an embeddable set of
feasible states. This is proved over the following two Lemmas.
Lemma 5.8. Let F be a non-contracting and distortion d embedding of G into H. Then there
exists an embeddable set of feasible states.
Proof. For u ∈ V (T ), consider fu to be the function F restricted to B(u, d + 1). Observe that
each fu is feasible. It is also easy to verify that for u ∈ V (T ) and v ∈ CT (u), fv succeeds fu .
To show the existence of feasible u-states, we have to define types. Let u = {u1 , . . . , uk } ∈
V (T ) and v ∈ C(u). We create a [fu , v] type-list L[fu , v]. For each x ∈ Domfu (v) ∪ M [fu , v]
and ui ∈ Xu , we define tuxi (y) = β (DH (F (x), ui ) − DG (x, y)) for all y ∈ Domfu (v). We add
tx [fu , v] = (tux1 , . . . , tuxk ) to L[fu , v]. tx is a [fu , v] type by the following observation, which we
prove later.
Observation 5.9. For any ui ∈ Xu and y ∈ Domfu (v), tuxi (y) ≥ −(Γ + d + 1).
For any x, y ∈ Domfu (v), we have the type tx [fu , v] such that tuxi [fu , v](y) = DH (F (x), ui ) −
DG (x, y) for all ui ∈ Xu . From Definition 5.2, we can say that say each L[fu , v] is compatible
with Domfu (v).
Let Su constitute the feasible u-partial embedding fu along with L(fu , v) for each v ∈ NT (u).
From Definition 5.5, Su is a feasible u-state by the the following claim, which we prove later.
Claim 5.10. For two different v, w ∈ NT (u) such that v 6= w, L[fu , v] agrees with L[fu , w].
To complete the proof of existence of a set of embeddable feasible states, we have to prove
that conditions (ii) and (iii) of Definition 5.6 hold for the above description of types. Condition
(ii) holds by the following claim, and Condition (iii) can be proved similarly. The following claim
will be proved later.
Claim 5.11. Let u ∈ V (T ) and v ∈ NT (u). Then for every w ∈ NT (v) \ u and a type
t1 ∈ L[fv , w] there exists a type t2 ∈ L[fu , v] satisfying the following conditions.
(a) For all x ∈ Domfu (v) ∩ Domfv (w) and a ∈ Xu ∩ Xv , ta2 (x) = ta1 (x)


b
a
(b) For all x ∈ Domfu (v) ∩ Domfv (w) and a ∈ Xu \ Xv , t2 (x) = β min (DH (a, b) + t1 (x)) .
b∈Xv

(c) For all x ∈ Domfu (v) \ Domfv (w) and a ∈ Xu ∩ Xv ,


a
a
(t1 (y)) − DG (x, y)) .
t2 (x) = β
max
y∈Domfv (w)

(d) For all x ∈ Domfu (v) \ Domfv (w) and a ∈ Xu \ Xv ,
ta2 (x)

=β



max

y∈Domfv (w)



min (DH (a, b) +

b∈Xv

tb1 (y))


− DG (x, y) .

Lemma 5.12. Let Π = {fu : u ∈ V (T )} be an embeddable set of feasible states. Then there
exists a non-contracting and distortion d embedding of G into H.
Proof. This Lemma will be proved by a series of claims. The Claims 5.13, 5.14 and 5.15 can
be proved in the similar way that we proved Claims 4.6, 4.7 and 4.8, respectively. We prove
Claim 5.16 and 5.17 later.
Claim 5.13. For every x ∈ V (G), there exists a feasible u-state such that x ∈ Domfu .
26

Claim 5.14. The subgraph of T induced by Ax = {u ∈ V (T ) : x ∈ Domfu } is connected.
Moreover, x ∈ Domfu ∩ Domfv implies fu (x) = fv (x).
Now by Definition 3.6, we construct F = ΦΠ , where Π = {fu : u ∈ V (T )}.
Claim 5.15. F is a metric embedding with expansion at most d.
Claim 5.16. Consider a path P = u1 u2 . . . uk from u = u1 to v = vk in T . Then for every
x ∈ Domfv , at least one of the following properties hold.
Prop-1: There exists a uj ∈ P and y ∈ Domfuj such that DH (F (x), u′ )−DG (x, y) ≥ 2Γ+3d+3
for all u′ ∈ Xuj .
′

Prop-2: There exists a type tx ∈ L[fu , u2 ] such that tux (y) = DH (F (x), u′ ) − DG (x, y) for all
y ∈ Domfu (u2 ) and u′ ∈ Xu .
Claim 5.17. ConsiderS a path P = u1 u2 . . . uk from u to v in T , where u = u1 and v = uk .
Domfui is non-contracting.
Then F restricted to
ui ∈P

Now we will be done if we prove that F is a non-contracting embedding. Let us consider two
vertices x, y ∈ V (G). Note that each of F (x) and F (y) is in some bag. Fix u, v ∈ V (T ) such
that F (x) ∈ Xu and F (y) ∈ Xv . Consider the path P = u1 u2 . . . uk from u to v in T , where
u = u1 andSv = uk . By Claim 5.17, the shortest path between F (x) to F (y) is non-contracting
Domfui .
as x, y ∈
ui ∈P

Proof of Observation 5.9. Observe that

DG (x, y) ≤ DH (F (x), F (y)) ≤ DH (F (x), ui ) + DH (ui , F (y))
≤ DH (F (x), ui ) + Γ + (d + 1).
The first inequality follows from the fact that F is a non-contracting embedding, while the
second inequality follows from triangle inequality. The third inequality follows from the fact
that y ∈ B(u, d + 1) along with the fact that H has bounded connected treewidth.
So, DH (F (x), ui ) − DG (x, y) ≥ −(Γ + d + 1). This implies
tuxi (y) = β (DH (F (x), ui ) − DG (x, y)) ≥ −(Γ + d + 1).

Proof of Claim 5.10. For contradiction, let there exist tp ∈ L[fu , v] and tq ∈ L[fu , w] such that
for all x ∈ Domfu (v) and y ∈ Domfu (w) there is some ui ∈ Xu , tup i (x) + tuq i (y) < DG (x, y). Let
x′ ∈ Domfu (v) and y ′ ∈ Domfu (w) be two vertices such that there is a ui with tup i (x′ ) + tuq i (y ′ ) <
u
u
DG (x′ , y ′ ) and for all x ∈ Domfu (v), y ∈ Domfu (w) and uj with tp j (x) + tq j (y) < DG (x, y),
u
u
j
j
tup i (x′ ) + tuq i (y ′ ) − DG (x′ , y ′ ) ≤ tp (x) + tq (y) − DG (x, y). This implies


tup i (x′ ) + tuq i (y ′ ) = β DH (F (p), ui ) − DG (p, x′ ) + β DH (F (q), ui ) − DG (q, y ′ )
< DG (x′ , y ′ )

= DH (F (p), ui ) − DG (p, x′ ) + DH (F (q), ui ) − DG (q, y ′ )

< DG (x′ , y ′ )
Now, we can say
DH (F (p), F (q)) ≤ DH (F (p), ui ) + DH (F (q), ui ) < DG (p, x′ ) + DG (q, y ′ ) + DG (x′ , y ′ ).
By the choice of x′ and y ′ , DG (p, x′ ) + DG (q, y ′ ) + DG (x′ , y ′ ) = DG (p, q) as any p to q path in
G must pass through some vertex in Domfu (v) and Domfu (w). Putting everything together,
DH (F (p), F (q)) < DG (p, q). It contradicts the fact that F is non-contracting.
27

Proof of Claim 5.11. Let tp = (tvp1 , . . . , tvpl ) ∈ L[fv , w], where vj ∈ Xv for all j ∈ [l] and p is
v
some vertex in Domfv (w) ∪ M [fv , w]. Note that tpj (x) = β(DH (F (p), vj ) − DG (p, x)) for all
x ∈ Domfv (w). As u is not a forget node, Domfv (w) ∪ M [fv , w] ⊆ Domfu (v) ∩ M [fu , v]. As we
are assuming that we are working with a nice tree decomposition and that the graph has bounded
connected treewidth, p ∈ Domfu (v) ∪ M [fu , v]. Consider the type zp = (zpu1 , . . . , zpuk ) ∈ L[fu , v],
where ui ∈ Xu for all i ∈ [k]. zp (x) = β (DH (F (p), ui ) − DG (p, x)) for all x ∈ Domfu (v).
• For all x ∈ Domfu (v) ∩ Domfv (w) and a ∈ Xu ∩ Xv , it is easy to see that zpa (x) = tap (x) .
• For all x ∈ Domfu (v)∩Domfv (w) and a ∈ Xu \Xv , we can say the following. DH (F (p), a) =
min (DH (F (p), b) + DH (b, a)). It is because we are assuming each bag is connected and
b∈Xv

any path from F (p) to a in H, must pass through some vertex in Xv . Hence,
zpa (x) = β (DH (F (p), a) − DG (p, x))


= β min (DH (F (p), b) + DH (b, a)) − DG (p, x)
b∈Xv


= β min (DH (b, a) + β(DH (F (p), b) − DG (p, x)))
b∈Xv

= β



∵ By the definition of β


b
min DH (a, b) + tp (x)
.

b∈Xv



• For all x ∈ Domfu (v) \ Domfv (w) for any a ∈ Xu ∩ Xv , we can say the following.
Any path from p to x in G must pass through a vertex in Domfv (w), i.e., DG (p, x) =
(DG (p, y) + DG (y, x)). Recall that zpa (x) = β (DH (F (p), a) − DG (p, x)). This
min
y∈Domfv (w)

implies

zpa (x)





(DG (p, y) + DG (y, x))
= β DH (F (p), a) −
min
y∈Domfv (w)


(DH (F (p), a) − DG (p, y) − DG (y, x))
= β
max
y∈Domfv (w)


(β (DH (F (p), a) − DG (p, y)) − DG (y, x))
= β
max
y∈Domfv (w)

∵ DG (x, y) ≤ Γ + 2d + 2

= β



max

y∈Domfv (w)


tap (y) − DG (x, y)



• For all x ∈ Domfu (v) \ Domfv (w) for any a ∈ Xu \ Xv , we can say the following.
Any path from p to x in G must pass through a vertex in Domfv (w), i.e., DG (p, x) =
(DG (p, y) + DG (y, x)). Recall that zpa (x) = DH (F (p), a) − DG (p, x). This immin
y∈Domfv (w)

plies

28





zpa (x)

(DG (p, y) + DG (y, x))
= β DH (F (p), a) −
min
y∈Domfv (w)


(DH (F (p), a) − DG (p, y) − DG (x, y))
= β
max
y∈Domfv (w)


(β(DH (F (p), a) − DG (p, y)) − DG (x, y))
= β
max
y∈Domfv (w)

∵ DG (x, y) ≤ Γ + 2d + 2

Observe that DH (F (p), a) = min (DH (F (p), b) + DH (b, a)). Hence,
b∈Xv

zpa (x)



 
β min (DH (F (p), b) + DH (b, a)) − DG (p, y) − DG (x, y)
= β
max
b∈Xv
y∈Domfv (w)



min (DH (a, b) + β (DH (F (p), b) − DG (p, y))) − DG (x, y)
= β
max
y∈Domfv (w) b∈Xv





b
min DH (a, b) + tp (y) − DG (x, y)
= β
max


y∈Domfv (w)

b∈Xv

Proof of Claim 5.16. We prove the claim by induction on k. First consider k = 1. Note that
Su is a feasible state. Observe that Prop-2 holds by Definition 5.5 and 5.2. Therefore, the base
case holds.
Let the statement be true for all k′ < k. Now we show for k.
If Prop-1 holds for some x ∈ Domfv , we are done for that x. So, consider some x ∈ Domfv
such that for every uj ∈ P and y ∈ Domfuj there exists u′ ∈ Xuj such that DH (F (x), u′ ) −
DG (x, y) ≤ Γ + d + 1.
Consider the sub-path P ′ = u2 . . . uk . Recall that Prop-1 does not hold for the x ∈ Domfv
with respect to P ′ . By the induction hypothesis, there exists a type tx ∈ L[fu2 , u3 ] such that
′
tux (y) = DH (F (x), u′ ) − DG (x, y) for all y ∈ Domfu2 (u3 ) and u′ ∈ Xu2 . Note that either Su2
succeeds Su1 or Su1 succeeds Su2 depending on u2 ∈ C(u1 ) or u1 ∈ C(u2 ). Now by Definition 5.6,
we will have a type zx ∈ L[fu , u2 ] such that the following properties hold.
• For all y ∈ Domfu (u2 ) ∩ Domfu2 (u3 ) and a ∈ Xu ∩ Xu2 ,
zxa (y) = tax (y) = DH (F (x), a) − DG (x, y)
• For all y ∈ Domfu (u2 ) ∩ Domfu2 (u3 ) and a ∈ Xu \ Xu2 ,
zxa (y)

= β
= β







b
min DH (a, b) + tx (y)

b∈Xu2

min (DH (a, b) + DH (F (x), b) − DG (x, y))

b∈Xu2



∵ By Induction Hypothesis(I.H)

= β (DH (F (x), a) − DG (x, y))
= DH (F (x), a) − DG (x, y)

∵ Prop-1 does not hold

29

• For all y ∈ Domfu (u2 ) \ Domfu2 (u3 ) and a ∈ Xu ∩ Xu2 ,
!

a ′
′
a
tx (y ) − DG (y, y )
zx (y) = β
max
y ′ ∈Domfu (u3 )
2

= β

′

max

y ′ ∈Domfu (u3 )
2

= β

′


DH (F (x), a) − DG (x, y ) − DG (y, y )

DH (F (x), a) −

min

′

y ′ ∈Domfu (u3 )
2

= β (DH (F (x), a) − DG (x, y))

′


DG (x, y ) + DG (y , y)

!

(∵ By I.H)

!

= DH (F (x), a) − DG (x, y) (∵ Prop-1 does not hold)
• For all y ∈ Domfu (u2 ) \ Domfu2 (u3 ) and a ∈ Xu \ Xu2 ,
zxa (y) = β

max

y ′ ∈Domfu (u3 )
2

= β

max

y ′ ∈Domfu (u3 )
2

= β

max

= β



!
min (DH (a, b) + tbx (y ′ )) − DG (y, y ′ )

b∈Xu1

!
(∵ By I.H)
min (DH (a, b) + DH (F (x), b) − DG (x, y )) − DG (y, y )
′

′

b∈Xu1

′

y ′ ∈Domfu (u3 )
2



′


DH (F (x), a) − DG (x, y ) − DG (y, y )

DH (F (x), a) −

′

min

y ′ ∈Domfu (u3 )
2

= β (DH (F (x), a) − DG (x, y))

′


DG (x, y ) + DG (y , y)

!
!

= DH (F (x), a) − DG (x, y) (∵ Prop-1 does not hold)

Proof of Claim 5.17. We prove by the method of induction on k. If k = 1, the statement is valid
as Su is a feasible u-partial embedding. Now assume that the statement is true for all k′ < k.
Now, we show for k.
Observe that it is enough to show the following. For any two vertices x ∈ Domfu1 \ Domfu2
and y ∈ Domfuk \ Domfuk−1 , DH (F (x), F (y)) ≥ DG (F (x), F (y)). All other cases are taken care
of by the Induction Hypothesis on shorter length paths. Note that x satisfies either Prop-1 or
Prop-2 in Claim 5.16.
• Case 1(Prop-1 holds) In this case there exists a uj and z ∈ Domfuj , in the path P such
that DH (F (y), u′ ) − DG (y, z) ≥ 2Γ + 3d + 3 for all u′ ∈ Xuj .
Observe that any path from F (x) and F (y) must pass through some vertex u′′ ∈ Xuj . So,
DH (F (x), F (y)) = DH (F (x), u′′ ) + DH (u′′ , F (y))
≥ DH (F (x), F (z)) − DH (u′′ , F (z)) + DH (u′′ , F (y)) (By triangle inequality)
By the induction hypothesis, DH (F (x), F (z)) ≥ DG (x, z) and by Prop-1 DH (u′′ , F (y) ≥
DG (z, y) + 2Γ + 3d + 3. Hence,
DH (F (x), F (y)) ≥ DG (x, z) − DH (F (z), u′ ) + DG (z, y) + 2Γ + 3d + 3
≥ DG (x, z) − DH (u′′ , F (z)) + DG (y, z) + 2Γ + 3d + 3
≥ DG (x, y) + 2Γ + 3d + 3 − DH (u′′ , F (z))
≥ DG (x, y) + Γ + 2d + 2
30

The last inequality holds due to the following. z ∈ Domfuj and u′′ ∈ Xuj . Recalling the
fact that we are considering bounded connected treewidth, we can say that DH (u′′ , F (z)) ≤
Γ + d + 1.
′

• Case 2(Prop-2 holds) In this case there exists a type ty ∈ L[fu , u2 ] such that tuy (y) =
DH (F (y), u′ ) − DG (y, z) for all z ∈ Domfu2 (u) and u′ ∈ Xu . Let x ∈ Domfu (w) for
some w ∈ NT (u) \ u1 . Note that Su is a feasible partial embedding and hence L[fu , w]
′
is compatible with Domfu (w). So, there exists a type tx ∈ L[fu , w] such that tux (z) =
DH (F (x), u′ ) − DG (x, z) for all z ∈ Domfu (w) and u′ ∈ Xu .
Again considering the fact that Su is a feasible partial embedding, L[fu , u2 ] and L[fu , w]
must agree. Now by Definition 5.3, there exists y ′ ∈ Domfu (u2 ) and x′ ∈ Domfu (w) such
′
′
that tux (x′ ) + tuy (y ′ ) ≥ DG (x′ , y ′ ).
As the shortest path from F (x) to F (y) passes through some vertex u′′ ∈ Xu , we can
deduce the following.

DH (F (x), F (y)) = DH (F (x), u′′ ) + DH (u′′ + F (y))
′′

′′

≥ tux (x′ ) + DG (x, x′ ) + tuy (y ′ ) + DG (y, y ′ )
≥ DG (x′ , y ′ ) + DG (x, x′ ) + DG (y, y ′ ) ≥ DG (x, y)

Now, we are ready to design the FPT algorithm.
Theorem 5.18. Let G, H be two given graphs with n and N vertices, respectively, such that
the maximum degree of H is ∆, tw(H) ≤ αc and the length of the longest geodesic cycle in H is
ℓg . Then there exists an algorithm that either finds a non-contracting distortion d embedding of
G into H or decides no such embedding exists in running time O(n2 · N ) · (µ · ∆d+1 )∆

µ2 ·∆d+1 )
2O((4(µ+d))
+ nO(1) , where µ = 4(α + α2 (ℓg (α − 2) − 1)).

O(µ·d+d2 )

·

Proof. Due to Observation 2.5, if ∆(G) > ∆d , then there does not exist an embedding from G to
H. So, assume that ∆(G) ≤ ∆d . First, by [FG06], we find a tree decomposition of width 4α in
time 2O(α) · n2 . Then using the arguments in [DM17], we can convert this tree decomposition
in

polynomial time to a connected tree decomposition whose width is µ = 4(α + α2 (ℓg (α − 2) − 1)).
Let T = (T, {Xu }u∈V (T ) ) be a nice tree decomposition derived from it is constant time. Note
that |Xu | ≤ µ, Xr = ∅ and Xℓ = ∅, where r is the root of T and ℓ is any leaf of T . We do
a dynamic programming. For each u ∈ V (T ), we create a binary list of all possible feasible
u-state. For any leaf ℓ ∈ V (T ), make all entries to be true. Let u be a non-leaf node. Let Su
be a feasible u-state. Suppose for every v ∈ CT (u), there exists a feasible partial embedding Sv
and Sv succeeds Su . Then assign the corresponding entry of Su to be true. Assign true to the
corresponding entry of r if there exists a feasible u-state for each child of r. By Lemmas 5.8 and
5.12, one can observe that the algorithm is correct.
For the running time, we have to bound the total number of feasible partial embeddings and
total number of feasible states. Before proceeding further, let nu denote the number of feasible
u-states, where u ∈ V (T ), and let ts denote the time required to test whether a feasible state
succeeds another.
∆O(Γ·d+d2)
Observation 5.19. The total number of u-partial embeddings is at most n· µ · ∆d+1
∆O(Γ·d+d2) O((4(Γ+d))µ2 ·∆d+1 )
·2
.
and the total number of feasible u-states is at most n · µ · ∆d+1
31

Proof. Let us consider a u-partial embedding fu from some subset of V (G) to B(u, d + 1).
Observe that |B(u, d + 1)| ≤ µ.∆d+1 . Note that the distance between two vertices in B(u, d + 1),
is at most Γ. As we are considering non-contracting embedding, the domain of fu must be
contained in a ball of radius Γ + 2d + 2 centered at some vertex of G. As ∆(G) ≤ ∆d , the
2
domain of fu can contain at most ∆O(Γ.d+d ) vertices. So, the total number of feasible u-partial
∆O(Γ·d+d2)
.
embeddings is at most n · µ · ∆d+1
Now consider some u ∈ V (T ) and v ∈ NT (u). The total number of [fu , v] types is at most
2

µ2 ·∆d+1

d+1

and hence the total number of [fu , v] typelists is at most 2(4(Γ+d))
. Note
(4(Γ + d))µ ·∆
that the maximum degree of T is O(1). So, the total number of feasible u-states, i.e., nu is at
∆O(Γ·d+d2) O((4(Γ+d))µ2 ·∆d+1 )
·2
.
most n · µ · ∆d+1
Recalling Definition 4.3 and 5.6, we can say the following. Let fu and fv correspond
 to
u ∈ V (T ) and v ∈ CT (u). One can decide whether fv succeeds fu in time O n · µ · ∆d+1 and
hence the time required to test whether a feasible state succeeds another ts = n · µ · ∆d+1 + µ ·
µ2 ·∆d+1

).
∆d+1 · 2O((4(Γ+d))
First, a tree decomposition has to be constructed and converted into a connected tree decomposition in 2O(α) · n2 + nO(1) time. This connected tree decomposition is converted into a
nice tree decomposition in polynomial time, with the guarantee that the distance between two
vertices in a bag of the nice tree decomposition is at most Γ. Recall that T is a nice tree decomposition, which implies |V (T )| = O(µ.N ) and ∆(T ) = O(1). So, there are at most O (µ · N nu )
feasible states. Note that the bags corresponding to two adjacent vertices of T , differ by at most
∆O(µ.d2 )
one vertex of H. So, each feasible partial embedding can take part in at most µ · ∆d+1
number of successions. Thus the total running time of the algorithm is
∆O(µ.d2 )
· ts . Since Γ ≤ µ, the running time is
= 2O(α) · n2 + nO(1) + µ · N · nu · µ · ∆d+1

µ2 ·∆d+1 )
O(µ·d+d2 )
O((4(µ+d))
O(1)
2
d+1
∆
+n
, where µ = 4(α+ α2 (ℓg (α−2)−1)).
·2
O(n ·N )·(µ·∆ )

6

Graph Metric Embedding for Generalized Theta graphs

In this section, we design an FPT algorithm for embedding unweighted graphs into generalized theta graphs. Our FPT algorithm is parameterized by the distortion d and the number k
of paths in the generalized theta graph. The strategy for the algorithm is still the same: that of
putting together partial embeddings to obtain a non-contracting distortion d metric embedding.
For this algorithm, we also observe structural properties of graphs that are embeddable into
generalized theta graphs. We exploit these properties to obtain an FPT algorithm to compute
a set of partial embeddings, and then use a dynamic programming algorithm to put together
partial embeddings from the set to obtain the solution metric embedding. Our notion of partial
embeddings will be more involved in this algorithm.
Let (G, DG ) be the graph metric that we want to embed into the graph metric (H, DH ).
Here H is a generalized theta graph defined at s,t and let P be the family of s − t paths that
define H. To begin with, we try to guess the non-contracting distortion d embedding of (G, DG )
into (H, DH ), when restricted to a d-ball around s and around t.
Definition 6.1. Let F be a non-contracting distortion d embedding of G into H. Define
Bs = {v ∈ V (H) | DH (v, s) ≤ d} and Bt = {v ∈ V (H) | DH (v, t) ≤ d}. For an embedding F :
V (G) → V (H), define DomFs = {u ∈ V (G) | F (u) ∈ Bs } and DomFt = {u ∈ V (G) | F (u) ∈ Bt }.
The following observation talks about the degree bound on the vertices of a graph that is
embeddable into a generalized theta graph.
Observation 6.2. If there exists a non-contracting distortion d embedding F of G into H, then:
32

• Each vertex in DomFs can have degree at most (k + 1)d. Similarly, each vertex in DomFt
can have degree at most (k + 1)d.
• All other vertices of G can have degree at most 2d.
Observation 6.3. The number of possible non-contracting distortion d embeddings of some
O(kd)
.
U ⊆ V (G) into Bs ∪ Bt is at most n2 · (kd + 1)(2d)
Proof. Observe that |Bs | , |Bt | ≤ kd + 1. As we are considering non-contracting embeddings, the
preimage of Bs (Bt ) lies in a ball of radius 2d centered at some vertex of G. By Observation 6.2,
the size of the pre-image of Bs (Bt ) is at most (2d)O(kd) . Hence, the number of required
O(kd)
.
embeddings can be at most n2 · (kd + 1)2.(2d)
We prove several properties of graphs that are embeddable into generalized theta graphs. For
the given input graph G, let F be a non-contracting distortion d embedding and Ψ : DomFs ∪
DomFt → Bs ∪ Bt be the restriction of F to Bs ∪ Bt . Let C1 , C2 , . . . Ca be the components of
G \ (DomFs ∪ DomFt ). We will derive certain properties of G with the help of the embedding F .
For each i ∈ [k], let Pi′ = Pi \ (Bs ∪ Bt ). If Pi′ is a non-empty path, let si be the endpoint of Pi′
that has an edge to Bs while ti be the endpoint of Pi′ that has an edge to Bt . Let Si (Ti ) denote
the set of vertices of DomFs (DomFt ) that are mapped into Pi .
Observation 6.4. Let F be a non-contracting distortion d embedding, Ψ : DomFs ∪ DomFt →
Bs ∪ Bt be the restriction of F to Bs ∪ Bt , and C1 , C2 , . . . Ca be the components of G \ (DomFs ∪
DomFt ). Then each component of G \ (DomFs ∪ DomFt ) can have it’s vertices mapped into exactly
one Pi′ , i ∈ [k].
Proof. Since a non-contracting distortion d embedding requires an edge to have expansion at
most d, all vertices of a component of G \ (DomFs ∪ DomFt ) must be mapped into exactly one Pi′ ,
i ∈ [k].
Also, there cannot be many components of G \ (DomFs ∪ DomFt ) mapped into a Pi′ , i ∈ [k].
Observation 6.5. Given a non-contracting distortion d embedding F , each Pi′ , i ∈ [k], can have
at most 2 connected components of G \ (DomFs ∪ DomFt ) mapped into it, in the non-contracting
distortion d embedding F .
Proof. Let F be a non-contracting distortion d embedding. Assume that there are three connected components Ci1 , Ci2 , Ci3 of G \ (DomFs ∪ DomFt ) mapped into path Pi′ for some i ∈ [k]. As
all components are mapped into a path, at most one of them has some neighbours, in G, mapped
into Bs (Bt ). So, there must be a component that has no neighbour mapped into Bs ∪ Bt . This
implies the graph is disconnected.
Thus, there can be at most 2k components of G \ (DomFs ∪ DomFt ).
Definition 6.6. Let F be a non-contracting distortion d embedding. An empty subpath of F
is a subpath of the generalized theta graph where none of the vertices have any preimage. If a
path Pi′ , i ∈ [k], has an empty subpath with one endpoint at ti , then such a subpath is called a
t-empty subpath. Similarly, if a path Pi′ has an empty subpath with one endpoint at si , then such
a subpath is called a s-empty subpath. If a path Pi′ contains an empty subpath that coincides
with neither si nor ti , then such a subpath is called an internal-empty subpath. Finally, it is
possible that the path Pi′ itself is an empty subpath and then Pi′ is called a fully-empty subpath.
Note that a path Pi′ can have at most one empty subpath with respect to F . Similarly, we
classify the components of G \ (DomFs ∪ DomFt ).

33

Definition 6.7. Let F be a non-contracting distortion d embedding. A component in G \
(DomFs ∪ DomFt ) is called an s-component if it has neighbours to DomFs and not to DomFt .
Similarly, we define a t-component. A full component is a component that has neighbours to
both DomFs and DomFt .
Since F is a non-contracting distortion d embedding, the following observation is true.
Observation 6.8. Let F be a non-contracting distortion d embedding. Any path Pi , Pi′ 6= ∅,
can be one of the following forms.
(i) form-1: It has an s-component mapped into it by F , and a t-empty subpath,
(ii) form-2: It has a t-component mapped into it by F , and an s-empty subpath,
(iii) form-3: It has an s-component and a t-component mapped into it by F , and an internalempty subpath,
(iv) form-4: It has a full component mapped into it by F ,
(iv) form-5: It contains a fully-empty subpath.
If we refer Pi to be of form-st , then Pi is of form-1 or form-2 or form-3.
The objective is to find a non-contracting distortion d embedding F , if it exists. Although
we do not know about F , we want to store a snapshot of F .
Definition 6.9. A configuration X is a tuple (Ψ, P ′ , P̂) where:
• Let U ⊆ V (G) be such that G \ U creates a set of components {C1 , C2 , . . . , Ca }, a ≤ 2k.
Ψ : U → Bs ∪ Bt is a non-contracting distortion d embedding of U .
• P ′ ⊆ P,
• P̂ is a family of |P \ P ′ | tuples such that for each path Pi ∈ P \ P ′ , there is a tuple
(formi , CPi , compi ) with the following information:
(i) formi assigns the name of a form to Pi .
(ii) The set CPi is a set of at most 2 components of G \ U that are assigned to Pi′ and to
no other Pj′ , j 6= i.
(iii) The function compi indicates for each C ∈ CPi whether it is an s-component or a
t-component or full-component, with respect to Ψ.
S
• Pi ∈P\P ′ CPi has all the components of G \ U .
The number of configurations is bounded for a fixed Ψ.

Observation 6.10. For any fixed Ψ, the total number of configurations is O(k2k ).
Proof. When Ψ : U → Bs ∪ Bt is fixed, the components {C1 , C2 , . . . , Ca } of G \ U are fixed. Also,
whether a component is an s-component, a t-component or a full-component gets fixed. The
total number of ways in which the components can be assigned to paths of P is O(k2k ). Once
an assignment of the components to the paths is fixed, in constant time, we can find out P ′ , and
for each i ∈ [k], the tuple (formi , CPi , compi ). Therefore, the total number of configurations for
a fixed Ψ is O(k2k ).
Next, we define feasible configurations that can be associated with metric embeddings.
Definition 6.11. A configuration X = (Ψ, P ′ , P̂) is said to be feasible with respect to a noncontracting distortion d embedding F of G into H if the following hold:
34

• Ψ : DomFs ∪ DomFt → Bs ∪ Bt is the restriction of F to DomFs ∪ DomFt .
• Pi′ = Pi \ (Bs ∪ Bt ) is empty for each Pi ∈ P ′ ⊆ P. ,
• For each Pi that is non-empty with respect to F , P̂ contains a tuple (formi , CPi , compi )
with the following information:
(i) formi is the form of Pi in F .
(ii) The set CPi is the set of at most 2 components of G \ U that are embedded into Pi′
by F .
(iii) The function compi indicates for each C ∈ CPi whether it is an s-component or a
t-component or full-component, with respect to F .
S
• Pi ∈P\P ′ CPi has all the components of G \ (DomFs ∪ DomFt ).

By Observation 6.4, in a feasible configuration |CPi | ≤ 2. Note that if |CPi | = 0, then Pi
can only be of form-5. If |CPi | = 1, then Pi can be of form-1, form-2 or form-4. If |CPi | = 2,
then Pi can only be of form-3 where one component of CPi is a s-component and the other
one is a t-component. Note that each non-contracting distortion d embedding F induces a
feasible configuration. We denote it by X (F ). Also, the total number of feasible configurations
is bounded by the total number of configurations.
Next, we define the notion of a last vertex for a component of G \ (DomFs ∪ DomFt ) with
respect to the embedding F .
Definition 6.12. Let F be a non-contracting distortion d embedding. Let C be a j-component,
j ∈ {s, t}. A vertex ℓ in C is the last vertex of C with respect to embedding F if DH (j, F (ℓ)) ≥
DH (j, F (x)) for all x ∈ C.
The following Lemma gives a bound on the potential last vertices of a component of G \
(DomFs ∪ DomFt ) if G is embeddable into H.
Lemma 6.13. Let F be a family of non-contracting distortion d embedding of G into H such
that X (F1 ) = X (F2 ) for any F1 , F2 ∈ F. Then for any form-st path Pi and any s(t)-component
2
C ∈ CPi , there are dO(d ) vertices that are candidates for being the last vertex of C with respect
to some F ∈ F.
Proof. Without loss of generality, assume that C is an s-component. Let v ∈ C be a candidate
for the last vertex of C with respect to some F ∈ F. Let u ∈ Si be some vertex in DomFs that is
mapped to a vertex in Pi . Since G is a connected graph, such a vertex always exists. We show
that, in G, v must be either a vertex furthest away from u or at most d2 distance away from
a furthest vertex. Let Q̂ be the subpath of Pi between F (u) and F (v). Consider the subpath
Q ⊆ Q̂ that has length d2 and has an endpoint at F (v). Before proceeding further, we need the
following Claim.
Claim 6.14. For any vertex x that is mapped into some vertex of Q̂ \ Q, DG (u, x) < DG (u, v).
Proof. If the shortest path between u and v passes through x in G, then we are done. Therefore,
assume that the shortest path between u and v passes through two vertices of an edge (y, z) such
that DH (F (u), F (y)) < DH (F (u), F (x)) and DH (F (u), F (z)) > DH (F (u), F (x)). For ease of
notation, when DH (F (u), F (y)) < DH (F (u), F (x)) we say that y is mapped before x. Similarly,
when DH (F (u), F (z)) > DH (F (u), F (x)) we say that z is mapped after x. Note that such an
edge (y, z) exists on the shortest path between u and v. Also, since the expansion is at most d,

35

DH (F (y), F (z)) ≤ d. Now, we give an upper bound for DG (u, x)
DG (u, x) ≤ DG (u, y) + DG (y, x)
≤ DG (u, y) + DH (F (y), F (x))
< DG (u, y) + DH (F (y), F (z))
≤ DG (u, y) + d
For a lower bound of DG (u, v),
DG (u, v) = DG (u, y) + 1 + DG (z, v)
DH (F (z), F (v))
≥ DG (u, y) + 1 +
d
2
d +1−d
> DG (u, y) + 1 +
d
> DG (u, y) + d.

Therefore, all vertices that are furthest away from u must be mapped to vertices of Q. As
we are constructing a non-contracting embedding, all vertices that are mapped to vertices of Q
must be within distance d2 of the furthest vertices from u.
There can be at most d2 furthest vertices from u. By Observation 6.2, each vertex is of degree
2
at most 2d. Hence, the total number of candidate vertices for v is bounded by d2 .(2d)d .
Next, we define the notion of a shortest embedding of a component in a path of P.
Definition 6.15. Let Y be a feasible configuration such that Y = X (F ) for a non-contracting
distortion d embedding F . Let Pi be a form-st path, C ∈ CPi be a s-component of G \ (DomFs ∪
DomFt ) and ℓ ∈ C be a candidate to be the last vertex of C with respect F .
Recall that Si is the set of vertices of DomFs that are mapped into Pi . Let A be a family of
non-contracting and distortion d embedding of C ∪ Si into Pi such that the following conditions
hold,
(i) f1 |Si = f2 |Si for any f1 , f2 ∈ A.
(ii) For each f ∈ A, f (x) is a vertex of Pi′ for any x ∈ C.
(iii) For each f ∈ A, F |C∪Si = f and ℓ is the last vertex of C with respect to F .
(iv) For each f ∈ A, for any x ∈ DomFs ∪ DomFt , the path between f (ℓ) and f (x) is noncontracting with expansion at most d.
Then the shortest embedding of C ∪ Si into Pi with respect to Y and ℓ, is an embedding
f ∈ A such that DH (s, f (ℓ)) ≤ DH (s, f ′ (ℓ)) for all f ′ ∈ A. If C is a t-component, Ti is taken to
be the set of vertices of DomFt that are mapped into Pi and we can define the shortest embedding
of C ∪ Ti with respect to Y and ℓ in a similar way.
We can extend the notion of shortest embedding of a component into a path of P to that
of a non-contracting distortion d embedding of G into H that has shortest embeddings for all
s-components and t-components.
Definition 6.16. Let us consider a non-contracting distortion d embedding F of G into H. We
say F is a special embedding with respect to feasible configuration X (F ) if for every path Pi
of form-st and s (t)-component C ∈ CP , the following holds: F |C∪Si (F |C∪Ti ) is the shortest
embedding of C ∪ Si (C ∪ Ti ) into Pi with respect to the feasible configuration X (F ) and the
last vertex of C with respect to F .
36

The next lemma shows that it is enough to look for a special embedding of G into H.
Lemma 6.17. If there exists a non-contracting distortion d embedding of G into H, then there
exists a special embedding of G into H with respect to some configuration.
Proof. Let F be a desired embedding of G into H. Consider Ψ to be F restricted to Bs ∪ Bt
and let the feasible configuration with respect to F be X (F ). Let F ′ be a function from V (G)
to V (H) satisfying the following conditions.
(i) X (F ) = X (F ′ ).
′

′

(ii) For every x ∈ DomFs ∪ DomFt , F ′ (x) = F (x). That is DomFs ∪ DomFt = DomFs ∪ DomFt .
(iii) For every path Pi of form-4, component C ∈ CPi and vertex x ∈ C, F ′ (x) = F (x). In
other words if x is a vertex of any full component C, then F ′ (x) = F (x).
(iv) For every path Pi of form-st and s(t)-component C ∈ CPi , F ′ |C∪Si (F ′ |C∪Ti ) is the shortest
embedding of C ∪ Si (C ∪ Ti ) into Pi with respect to X (F ′ ) and the last vertex of C with
respect to F .
It is easy to see that F ′ is an injection from V (G) to V (H). Note that the last vertices of
components in F ′ remain the same as the last vertices of components in F . Let L denote the set
′
′
of last vertices of the components of G \ (DomFs ∪ DomFt ) = G \ (DomFs ∪ DomFt ). To conclude
that F ′ is a special embedding from G to H, we have to show that F ′ is a non-contracting
distortion d embedding of G into H. We will be done by the following claims.
Claim 6.18. F ′ has expansion at most d.
Proof. We show that DH (F ′ (x), F ′ (y)) ≤ d holds for any edge (x, y) ∈ E(G). Then we can
apply induction similar to that in the proof of Claim 3.11.
′
′
If both x, y ∈ DomFs ∪ DomFt , then DH (F ′ (x), F ′ (y)) = DH (F (x), F (y)) ≤ d. This is
′
′
because Ψ is a distortion d embedding of DomFs ∪ DomFt . If both x and y are mapped into the
same component C, then also DH (F ′ (x), F ′ (y)) ≤ d. Note that both x and y cannot belong to
′
′
different components. So, the only case that remains is when x ∈ DomFs ∪ DomFt and y is in
some component C.
If C is a full component, then DH (F ′ (x), F ′ (y)) = DH (F (x), F (y)) ≤ d. Let Pi be the path
that contains C. If C is an (a) s (t)-component, then x has to be a vertex in Si (Ti ). However,
F ′ |C∪Si (F ′ |C∪Ti ) is a shortest embedding of C ∪ Si (C ∪ Ti ) into Pi . Note that every shortest
embedding is a non-contracting embedding. Hence, DH (F ′ (x), F ′ (y)) ≤ d.
′

′

Claim 6.19. Let C be any component of G \ (DomFs ∪ DomFt ). Then for any x ∈ C and
′
′
y ∈ DomFs ∪ DomFt , the shortest path between F ′ (x) and F ′ (y) is non-contracting.
Proof. Note that F ′ (y) = F (y). If C is a full component, then F ′ (x) = F (x). So, DH (F ′ (x), F ′ (y)) =
DH (F (x), F (y)) ≥ DG (x, y). Now consider the case if C is an (a) s (t)-component. The shortest
′
′
path from F ′ (x) and F ′ (y) must pass through F ′ (z), where z is either a vertex in DomFs ∪DomFt
or the last vertex of C with respect to F ′ .
In either case,
DH (F ′ (x), F ′ (y)) = DH (F ′ (x), F ′ (z)) + DH (F ′ (z), F ′ (y))
≥ DG (x, z) + DG (z, y) (By the construction of F ′ )
≥ DG (x, y).

′

′

Recall that L is the set of last vertices of components in G \ (DomFs ∪ DomFt ) with respect
to F , and by construction F ′ .
37

Claim 6.20. F ′ is a non-contracting embedding.
′

′

Proof. Let x and y be two vertices of G such that either both x and y are in DomFs ∪ DomFt
or both are in the same component C. Then by the construction of F ′ , F ′ (x) = F (x) and
F ′ (y) = F (y). Hence, the shortest path between F ′ (x) and F ′ (y) is non-contracting.
′
′
If one of x and y is in DomFs ∪ DomFt and the other vertex is in some component C, then
also we are done by Claim 6.19.
So, assume that x and y are in different components. We look at the following cases:
• Let x ∈ C1 and y ∈ C2 . Assume that one of C1 and C2 is a full component. Without loss
of generality, let C1 be the full component. Then the shortest path from F ′ (x) to F ′ (y)
′
′
passes through F ′ (u), where u is some vertex in DomFs ∪ DomFt . So,
DH (F ′ (x), F ′ (y)) = DH (F ′ (x), F ′ (u)) + DH (F ′ (u), F ′ (y))
≥ DG (x, u) + DG (u, y) (By Claim 6.19)
≥ DG (x, y)
• Let x ∈ C1 and y ∈ C2 such that neither is a full component. Let ℓ1 ∈ V (G) be the last
vertex of C1 with respect to F , and ℓ2 ∈ V (G) be the last vertex of C2 with respect to F .
By construction they remain the last vertices of the respective components with respect
to F ′ as well. Suppose the shortest path from F ′ (x) to F ′ (y) passes through F ′ (u) where
′
′
u is some vertex in DomFs ∪ DomFt . Then
DH (F ′ (x), F ′ (y)) = DH (F ′ (x), F ′ (u)) + DH (F ′ (u), F ′ (y))
≥ DG (x, u) + DG (u, y) (By Claim 6.19)
≥ DG (x, y)
Otherwise, the shortest path from F ′ (x) to F ′ (y) contains F ′ (ℓ1 ) and F ′ (ℓ2 ). By construction of F ′ , DH (F ′ (ℓ1 ), F ′ (ℓ2 )) ≥ DH (F (ℓ1 ), F (ℓ2 )). Since, F was a non-contracting
distortion d embedding, this implies that DH (F ′ (ℓ1 ), F ′ (ℓ2 )) ≥ DG (ℓ1 , ℓ2 ). Then
DH (F ′ (x), F ′ (y)) = DH (F ′ (x), F ′ (ℓ1 )) + DH (F ′ (ℓ1 ), F ′ (ℓ2 )) + DH (F ′ (ℓ1 ), F ′ (y))
≥ DG (x, ℓ1 ) + DG (ℓ1 , ℓ2 ) + DG (ℓ2 , y) (Due to shortest embeddings)
≥ DG (x, y)

Therefore, we have shown that if G is embeddable into H then it is enough to find a special
embedding. We design an FPT algorithm for finding a special embedding.
Theorem 6.21. Metric Embedding into generalized theta graphs is FPT parameterized by
distortion d and number k of s − t paths. The algorithm runs in time O(N ) + n5 · k2k+1 · (kd +
2
O(kd)
· dO(d ) , where n and N are the number of vertices in the input and output graph
1)(2d)
metrics, respectively.
Proof. By Lemma 6.17, it is sufficient to look for special embedding with respect to some
configuration. We find ∆(G) and if ∆(G) > (k + 1)d, then we report NO. This is correct
by Observation 6.2. Note that ∆(G) can be found in linear time.
We first compute DH (s, u) and DH (t, u) for all u ∈ V (H). We store this distance information
in a matrix Dst , such that the look-up time for the distance from any u ∈ V (H) to s or t is O(1).
Note that we can compute Dst in O(N +k) time as the number of edges in H is O(N +k). Dst will
38

be required for checking whether an obtained function from V (G) to V (H) is a noncontracting
distortion d embedding.
Let us fix a non-contracting distortion d embedding Ψ of U ⊆ V (G) into Bs ∪ Bt and a
configuration Y containing Ψ. If the degree of any vertex in G \ U is more than 2d, then we
decide that there does not exist any desired embedding with respect to Y. Otherwise, we proceed
as follows. Let F be the special embedding of G into H with respect to Y that we want to find,
if one exists. Note that U = DomFs ∪ DomFt .
(i) If a path Pi is of form-5, we don’t have to do anything for that.
(ii) Let a path Pi be of form-4, and suppose C ∈ CPi is the only full component mapping
into Pi . The vertices in Si ∪ Ti ⊂ U are the points that are mapped into Pi \ Pi′ . Then
we find a non-contracting distortion d embedding fC , if possible, of C ∪ Si ∪ Ti into Pi
such that fC |Si = Ψ|Si and fC |Ti = Ψ|Ti . Note that Si (Ti ) is the set of vertices of
DomFs (DomFt ) that are mapped into Pi . Such an embedding fC can be found by running
the algorithm described in Lemma
3.18. This algorithm admits a time complexity of

2
2d+3
2d+2
O n ·d
· (4d(2d + 2))
= O n2 · dO(d) . If we cannot find such an embedding,
then there does not exist any special embedding of G into H with respect to Y.
(iii) Let Pi be a form-st path and C ∈ CPi be an (a) s (t)-component. Without loss of generality,
assume that C is an s-component. Here, our objective is to find the shortest embedding f
of C ∪ Si into Pi with respect to Y and some ℓ, where ℓ is the last vertex of C with respect
to F . We guess a vertex ℓ ∈ C, as the last vertex. This vertex is either a furthest vertex
from a fixed vertex a ∈ Si or lies within distance of d2 from a furthest vertex from a in G.
By Lemma 6.13, the total number of candidates for the last vertex of C with respect to F
2
is dO(d ) .
It is easy to see that |C ∪ Si | ≤ DH (f (ℓ), f (a)) ≤ 2d. |C ∪ Si | by Observation 2.6. Thus,
the length of the shortest embedding of C ∪ Si , where ℓ is the last vertex, is also in
this range. For each possible length |C ∪ Si | ≤ len ≤ 2d. |C ∪ Si |, we try to find a noncontracting distortion d embedding flen of C ∪ Si into a path Plen = {1, 2, . . . , len} such
that flen restricted to the first |Si | vertices is same as the mapping by Ψ, and for each
u ∈ C ∪ Si , DPlen (1, flen (u)) ≤ DPlen (1, flen (ℓ)). Observe that we have to run the algorithm
described in Corollary 3.21. If the algorithm returns no for all lengths, for every candidate
ℓ for the last vertex, then there does not exist any special embedding of G into H with
respect to Y. Otherwise, assume that for the current guess ℓ the shortest length for
which the algorithm returns a required non-contracting distortion d embedding is len′ .
Let this embedding be fC . In the worst case this
incur a time complexity of
 step will

2)
2)
O(d
2
2d+3
2d+2
3
O(d
.
d
· O 2nd · n · d
· (4d(2d + 2))
=O n ·d

Let F = ΦΠ be the function such that Π = {Ψ} ∪ {fC | C is a component of G \ U }. We
verify whether the obtained F is a non-contracting distortion d embedding from G to H. If yes,
we are done. If not, then there does not exist any special embedding with respect to Y. Observe
that the distance between two given points in H, can be computed in O(1) time using Dst . Since
we only need to check for non-contraction and distortion d for every pairs of mapped vertices in
H, the verification of F for a desired embedding can be done by spending O(n2 ) time.
Note that in the worst case, we have to run the above steps for all possible configurations. If
we decide that there does not exist a special embedding with respect to all configurations, then
we report that G does not admit the desired embedding of G into H. The correctness of the
algorithm follows from Lemma 6.17.
Now we analyze the running time of the algorithm. Recall that there can be 2k components
2
of G\U . In the execution of our algorithm for a fixed configuration, we spent 2k·n2 ·dO(d ) +O(n2 )
time. By Observation 6.3 and 6.8, the total number of configuration is at most k2k · n2 · (kd +
39

O(kd)

. Note that we have spent O(N + k) time to compute Dst . Putting everything together,
1)(2d)
the time complexity of our algorithm is bounded by
O(kd)

O (N ) + n5 · k2k+1 · (kd + 1)(2d)

2)

· dO(d

.

7

Conclusion

In this paper, we presented several FPT algorithms for embedding into different graph
classes. Note that for all the considered graph classes, our results can be modified to answer the
Weighted Graph Metric Embedding problem for the graph classes. Similar to the results
in Section 3, for a particular graph class considered in this paper, when we take the maximum
edge weight M to be a parameter along with the set of parameters considered for the graph
class, then the problem is still FPT. On the other hand, without M as a parameter, the problem
is NP-Complete for any distortion d > 2. The question of the parameterized complexity of
embedding into trees of unbounded degree, asked in [FFL+ 13], still remains open. Another important question is to determine the parameterized complexity of Graph Metric Embedding
for bounded treewidth graphs, even when the treewidth is taken to be some constant. Since
trees with unbounded degree have treewidth 1, the latter open problem is a generalization of
the former.

References
[ABN11] I. Abraham, Y. Bartal, and O. Neiman. Advances in metric embedding theory.
Advances in Mathematics, 228(6):3026 – 3126, 2011.
[Bar96] Y. Bartal. Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications. In Proc. of FOCS, pages 184–193, 1996.
[BCIS05] M. Badoiu, J. Chuzhoy, P. Indyk, and A. Sidiropoulos. Low-Distortion Embeddings
of General Metrics into the Line. In Proc. of STOC, pages 225–233, 2005.
[BDG+ 05] M. Badoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. Räcke, R. Ravi, and
A. Sidiropoulos. Approximation Algorithms for Low-Distortion Embeddings into
Low-Dimensional spaces. In Proc. of SODA, pages 119–128, 2005.
[Bou85] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel
Journal of Mathematics, 52(1–2):46–52, 1985.
[CFK+ ] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer.
[CFL+ 17] T. Carpenter, F. V. Fomin, D. Lokshtanov, S. Saurabh, and A. Sidiropoulos. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. CoRR,
2017.
[DM17] Reinhard Diestel and Malte Müller. Connected tree-width. Combinatorica, 2017.
[FFL+ 13] M. R. Fellows, F. V. Fomin, D. Lokshtanov, E. Losievskaja, F. A. Rosamond, and
S. Saurabh. Distortion is Fixed Parameter Tractable. Transactions on Computation
Theory, 5(4):16:1–16:20, 2013.
[FG06] J. Flum and M. Grohe. Parameterized Complexity Theory. Texts in Theoretical
Computer Science. An EATCS Series. Springer, 2006.
40

[FRT03] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary
metrics by tree metrics. In Proc. of STOC, pages 448–455, 2003.
[GKL03] Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded Geometries,
Fractals, and Low-Distortion Embeddings. In Proc. of FOCS, pages 534–543, 2003.
[GNRS04] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, Trees and l1 Embeddings of Graphs. Combinatorica, 24(2):233–269, 2004.
[Ind01] P. Indyk. Algorithmic Applications of Low-Distortion Geometric Embeddings. In
Proc. of FOCS 2001, pages 10–33, 2001.
[JL84] W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert
space. In Conference in modern analysis and probability (New Haven, Conn., 1982),
volume 26 of Contemporary Mathematics, pages 189–206. American Mathematical
Society, 1984.
[KRS10] C. Kenyon, Y. Rabani, and A. Sinclair. Low Distortion Maps Between Point Sets.
SIAM Journal on Computing, 39(4):1617–1636, 2010. Peliminary version in Proc. of
STOC, 2004.
[LLR95] N. Linial, E. London, and Y. Rabinovich. The Geometry of Graphs and Some of its
Algorithmic Applications. Combinatorica, 15(2):215–245, 1995.
[Mat13] J. Matoušek.
Lecture Notes on Metric Embeddings.
http://kam.mff.cuni.cz/ matousek/ba-a4.pdf.

2013.

Link:

[NR15] A. Nayyeri and B. Raichel. Reality Distortion: Exact and Approximate Algorithms
for Embedding into the Line. In Proc. of FOCS, pages 729–747, 2015.
[NR17] A. Nayyeri and B. Raichel. A Treehouse with Custom Windows: Minimum Distortion
Embeddings into Bounded Treewidth Graphs. In Proc. of SODA, pages 724–736,
2017.

41

