Light spanners for bounded treewidth graphs
imply light spanners for H-minor-free graphs∗
Glencora Borradaile and Hung Le
Department of Electrical Engineering and Computer Science
Oregon State University, USA
glencora@eecs.orst.edu, lehu@onid.oregonstate.edu

arXiv:1703.10633v1 [] 30 Mar 2017

Abstract
Grigni and Hung [10] conjectured that H-minor-free graphs have (1 + )-spanners that are light,
that is, of weight g(|H|, ) times the weight of the minimum spanning tree for some function
g. This conjecture implies the efficient polynomial-time approximation scheme (PTAS) of the
traveling salesperson problem in H-minor free graphs; that is, a PTAS whose running time is of
the form 2f () nO(1) for some function f . The state of the art PTAS for TSP in H-minor-freegraphs has running time n1/poly() . We take a further step toward proving this conjecture by
showing that if the bounded treewidth graphs have light greedy spanners, then the conjecture is
true. We also prove that the greedy spanner of a bounded pathwidth graph is light and discuss
the possibility of extending our proof to bounded treewidth graphs.
1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems, G.2.2 Graph
Theory
Keywords and phrases Light spanners, bounded treewidth graphs, H-minor-free graphs, traveling salesperson problem
Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p

1

Introduction

Spanners are used to approximately preserve distances in a compact way. In this work, we
focus on spanners that preserve distances within a (1 + ) factor (for a fixed  < 1) and
measure quality in terms of the spanner’s weight compared to the minimum spanning tree (the
lightness). Formally, given an edge-weighted graph G, we wish to find a spanning subgraph
S of G such that1 dS (x, y) ≤ (1 + ) · dG (x, y) ∀x, y ∈ V (G) and w(S) = L() · w(MST(G))
where the lightness, L(), is a function that depends only on .
We focus on the greedy (1 + )-spanner, the spanner that is constructed by adding edges
by increasing weight while doing so decreases the distance between their endpoints by a 1 + 
factor. Althöfer et al. showed that the greedy spanner has lightness L() = O(1/) for planar
graphs (and also gave lightness bounds that depend on n for general graphs) [1]. The same
lightness bound holds for bounded genus graphs, as showed by Grigni [8]. However, the best
lightness
p bound, which was shown by Grigni and Sissokho [11], for H-minor-free graphs is
(|H| log |H| log n/).

∗
1

This material is based upon work supported by the National Science Foundation under Grant No.
CCF-1252833.
We use standard graph terminology and notation; we revisit notation necessary for some proofs in
Appendix A.

© Glencora Borradaile and Hung Le;
licensed under Creative Commons License CC-BY
Conference title on which this volume is based on.
Editors: Billy Editor and Bill Editors; pp. 1–21
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

2

Light spanners bounded treewidth graphs and H-minor-free graphs

In this work, we investigate the possibility of removing the dependence on n from the
lightness for H-minor-free graphs by focusing on the following conjecture of Grigni and
Hung [10]:
I Conjecture 1. H-minor-free graphs have (1 + )-spanners with lightness that depends on
|H| and  only.
If this conjecture is true, it would, among other things, imply that TSP admits an efficient
PTAS for H-minor free graph, that is, a PTAS whose running time is of the form 2f () nO(1)
for some function f , improving on the existing PTAS with running time n1/poly() via the
framework of Demaine, Hajiaghayi and Kawarabayashi [3] and the spanner of Grigni and
Sissokho [11]. We make progress towards proving Conjecture 1 by reducing the heart of the
problem to the simpler graph class of bounded treewidth2 graphs:
I Theorem 2. If the greedy (1 + )-spanner of a graph of treewidth tw has lightness that
depends on tw and  only, then the greedy (1 + )-spanner of an H-minor-free graph has
lightness that depends on |H| and  only.
Grigni and Hung gave a construction of a (1 + )-spanner for graphs of pathwidth pw with
lightness O(pw3 /) [10]; however, their construction is not greedy. Rather than considering
the edges by increasing order of weight, they constructed a monotone spanning tree and
greedily added edges to the monotone tree. They also argued that such a spanning tree is
unlikely to exist for bounded treewidth graphs, giving little hope on two fronts (the different
spanner construction as well as a construction that is unlikely to generalize to graphs of
bounded treewidth) that Theorem 2 will lead to proving Conjecture 1 via Grigni and Hung’s
work. In this paper we improve Grigni and Hung’s for bounded pathwidth graphs and
do so by arguing lightness for the standard greedy algorithm, removing the limitations of
Theorem 2 as a stepping stone to Conjecture 1. In Section 4, we prove:
I Theorem 3. The greedy (1 + )-spanner for a graph G of pathwidth pw has lightness
O(pw2 /).
While our proof does not immediately extend to graphs of bounded treewidth, the techniques
are not as specific to path decompositions as Grigni and Hung’s monotone-spanning-tree
technique is, and thus gives more hope for proving Conjecture 1.
While it may seem like a limitation in proving Conjecture 1 that we must show that
a particular construction of the (1 + )-spanner (namely the greedy construction) is light
for bounded treewidth graphs, Filtser and Solomon (Theorem 4 [7]) showed that if an
edge-weighted graph has light spanner, its greedy spanner is also light.

2

Analyzing greedy spanners

The greedy construction for a (1 + )-spanner due to Althöfer et al. [1] is an extension of
Kruskal’s minimum spanning tree algorithm. Start by sorting the edges by increasing weight
and an empty spanner subgraph S; for each edge uv in order, if (1 + )w(uv) ≤ dS (u, v), then
uv is added to S. By observing that this is a relaxation of Kruskal’s algorithm, MST(G) ⊆ S.
Althöfer et al. (Lemma 3 [1]) also showed that for any edge e = uv in S and any u-to-v path
PS (uv) between u and v in S \ {e}, we have:
(1 + )w(e) ≤ w(PS (uv))
2

Formal definitions of pathwidth and treewidth are given later in this paper.

(1)

G. Borradaile and H. Le

3

The following property of greedy (1 + )-spanners is crucial in our analysis. The proof follows
by contradiction to Equation (1) and can be found in Appendix B.
I Lemma 4. Let S be the greedy (1 + )-spanner of a graph and let H be a subgraph of S.
Then the greedy (1 + )-spanner of H is itself.

2.1

Charging scheme

To argue that S is light, that is, has weight L()w(MST(G) for some function L(), we
identify a specific charging path PS (uv) from u to v for each non-spanning-tree edge uv
of the spanner. One may think of PS (uv) as being the shortest u-to-v path in S when
uv is added to the spanner, but this is not necessary for the analysis; we only need that
(1 + )w(uv) ≤ w(PS (uv)) (as is guaranteed by Equation (1) for greedy spanners) for every
path in S. We call (uv, PS (uv)) a charging pair. For a spanning tree T (not necessarily a
minimum spanning tree), we call a set of charging pairs (e, PS (e)) for all edges e ∈ S\T a
charging scheme. We say that an edge is charged to if it belongs to the charging path for
another edge. A charging scheme is acyclic if for every edge e 6∈ T , the directed graph where
vertices of the graph are edges not in T and directed edges represent charged to relationship,
i.e. there is a directed edge (e1 → e0 ) if e0 is charged to by ei , is acyclic. A charging scheme
is k-simple if each edge e ∈ S\T is charged to at most once and each edge in T is charged to
at most k times. Based on these definitions , one can prove (see Appendix B for full details):
I Lemma 5. If S is a greedy (1 + )-spanner of a graph that has a k-simple acyclic charging
scheme to a spanning tree T , then w(S) ≤ (1 + k )w(T ).
Indeed, in proving the greedy (1 + )-spanner has weight at most (1 + 2 )MST(G) when G
is planar, Althofer et al. [1] implicitly proved the existence of a 2-simple acyclic charging
scheme to MST(G). Since our paper only deals with acyclic simple charging schemes, we
simply say simple charging schemes to refer to acyclic simple charging schemes. We will use
a stronger result for outer-planar graphs, planar graphs in which all the vertices are on the
boundary of a common face (the outer face), which we take to be simple. The proof of the
following lemma is included in Appendix B.
I Lemma 6. If G is an outer-planar graph and T is a path formed by all the edges in the
boundary less one edge, then G has an acyclic 1-simple charging scheme to T .
For a greedy spanner S, one may instead, when it is convenient, define a weak k-simple
charging scheme for a supergraph of S. A weak k-simple charging scheme is a k-simple
charging scheme in which Equation (1) need not hold for charging pairs. See Appendix B for
the proof of the following.
I Lemma 7. Let S be a greedy spanner with spanning tree T and let Ŝ be a supergraph of S
that S spans. If Ŝ has a weak k-simple charging scheme to T then S has a k-simple charging
scheme to T .

3

The greedy spanner of an H-minor free graph is possibly light

Our result relies on the Graph Minor Structure Theorem due to Robertson and Seymour [14]
which guarantees a structural decomposition of an H-minor-free graph into simpler graphs.
Informally, the seminal Graph Minor Structure Theorem of Robertson and Seymour states
that every H-minor-free graph is the (small) clique-sum of graphs that are almost embeddable

Arxiv

4

Light spanners bounded treewidth graphs and H-minor-free graphs

on graphs of small genus. We give a formal statement of the Graph Minor Structure Theorem
below after some requisite definitions.
We first argue that almost-embeddable graphs have light (1 + )-spanners assuming
bounded treewidth graphs have light (1 + )-spanners. We partition the spanner edges of
almost-embeddable graphs into two parts: those in the surface-embeddable part and those in
the non-embeddable part. We bound the weight of the surface-embeddable part by “cutting
along” a subset of edges to create an outer-planar graph and then using the lightness bound
for outer-planar graphs. Since the large-grid minor of the graph must be contained in the
surface-embeddable part, we can show that the non-embeddable part has bounded treewidth.
Therefore, the lightness of (1 + )-spanners of the non-embeddable part follows from the
assumption that bounded treewidth graphs have light (1 + )-spanners.

3.1

Definitions: Treewidth, pathwidth and the structure of H-minor
free graphs

Note that if G excludes K|H| as a minor, then it also excludes H.
Tree decomposition A tree decomposition of G(V, E) is a pair (X , T ) where X = {Xi |i ∈ I},
each Xi is a subset of V (called bags), I is the set of indices, and T is a tree whose set of
nodes is X satisfying the following conditions:
1. The union of all sets Xi is V .
2. For each edge uv ∈ E, there is a bag Xi containing both u, v.
3. For a vertex v ∈ V , all the bags containing v make up a subtree of T .
The width of a tree decomposition T is maxi∈I |Xi | − 1 and the treewidth of G, denoted by
tw, is the minimum width among all possible tree decompositions of G. A path decomposition
of a graph G(V, E) is a tree decomposition where the underlying tree is a path and is denoted
by (X , P). The pathwidth of a G(V, E), denoted by pw, is defined similarly.
β-almost-embeddable A graph G is β-almost-embeddable if there is a set of vertices A ⊆
V (G) and β + 1 graphs G0 , G1 , . . . , Gβ such that:
1. |A| ≤ β.
2. G0 ∪ G1 ∪ . . . ∪ Gβ = G[V \A].
3. G0 is embeddable in a surface Σ of genus at most β.
4. Each Gj has a path decomposition (Xj , Pj ) of width at most β and length |Ij |, which is
the number of bags, for j ≥ 1.
5. There are β faces F1 , F2 , . . . , Fβ of G0 such that |Fj | ≥ |Ij |, G0 ∩ Gj ⊆ V (Fj ), and the
vertices of Fj appear in the bags of Xj in order along Pj for each j.
The vertices A are called apices and the graphs {G1 , G2 , . . . , Gβ } are called vortices. The
vortex Gj is said to be attached to the face Fj , 1 ≤ j ≤ β.
β-clique-sum Given two graphs H1 , H2 , a graph H is called a β-clique-sum of H1 and H2
if it can be obtained by identifying a clique of size at most β in each of two graphs H1 , H2
and deleting some of the clique edges.
We can now state Robertson and Seymour’s result:
Graph Minor Structure Theorem (Theorem 1.3 [14]). An H-minor-free graph can be
decomposed into a set of β(|H|)-almost-embeddable graphs that are glued together in a treelike structure by taking β(|H|)-clique-sums where β(|H|) is a function of |H|.

G. Borradaile and H. Le

5

It will be convenient to consider a simplified decomposition that assumes there are no edges
between the apices and vortices. This simplification introduces zero-weight edges that do not
change the distance metric of the graph. We include the proof of this claim in Appendix B.
I Claim 8. There is a representation of a β-almost-embeddable graph as a 2β-almostembeddable graph that has no edge between apices and vertices of vortices (that are not in the
surface-embedded part of the graph) and that maintains the distance metric of the graph.
In the remainder of this section, we prove Theorem 2 by assuming that, if S is the greedy
(1 + )-spanner of a graph of treewidth tw:
w(S) ≤ g(tw, ) · w(MST)

(2)

The bulk of the technical detail in dealing with H-minor free graphs is in handling the
vortices, which we do first.

3.2

Handling vortices

In this subsection, we consider a greedy (1 + )-spanner G of some apex-free β-almostembeddable graph. We will show that:
w(G) ≤ q(β, ) · w(MST(G))

(3)

where q(β, ) is the lightness that only depends on β and . Note that the MST of the
graph is the MST of the spanner. We assume that G is connected since we can bound the
weight of each component separately. Let G = G0 ∪ G1 ∪ . . . ∪ Gβ be the decomposition of G
into a graph G0 embedded on a surface Σ of genus at most β and a set G1 , . . . , Gβ vortices
according to the definition of β-almost-embeddability. Let Ci be the cycle bounding the face
of G0 to which vortex Gi is attached.
Bounding the weight of the vortices First we bound the weight of the vortices and
Sβ
Sβ
their bounding cycles ( i=1 Ci ) ∪ Gi by showing that MST(G) ∪ ( i=1 Ci ∪ Gi ) has bounded
treewidth.
Sβ
Let K = (MST(G) ∩ G0 ) ∪ i=1 Ci and let K ∗ be the dual of K; the vertices of K ∗
correspond to the faces of K. Consider a vertex v of K ∗ that does not correspond to a face
bounded by a cycle in {C1 , C2 , . . . , Cβ }. Then v must be adjacent to a face that is bounded
Sβ
by a cycle Cj for some j because K \ ( i=1 Ci ) is a forest. Therefore, the diameter of K ∗ is
O(β). Since a graph of genus β has treewidth O(β · diameter) (Eppstein, Theorem 2 [5]), K ∗
has treewidth O(β 2 ). Since the dual of a graph of treewidth tw and genus β has treewidth
O(tw + β) (Mazoit, Proposition 2 [13]), K has treewidth O(β 2 ).
Grohe showed that if Gi is a vortex attached to a face of K, then tw(Gi ∪ K) ≤
(pw(Gi ) + 1)(tw(K) + 1) − 1 (Lemma 2 [12]). Adding in each of the vortices G1 , G2 , . . . , Gβ to
Sβ
K and using Grohe’s result gives that the treewidth of MST(G) ∪ ( i=1 Ci ∪ Gi ) is O(β β+2 ).
Sβ
Sβ
Since MST(G) ∪ ( i=1 Ci ∪ Gi ) is the subgraph of a greedy spanner, MST(G) ∪ ( i=1 Ci ∪ Gi )
is a greedy spanner itself (Lemma 4) and by Equation (2), we have:
Pβ

i=1

(w(Ci ) + w(Gi )) ≤ g(O(β β+2 ), ) · w(MST(G)).

(4)

b be the graph obtained
Bounding the surface-embedded part of the spanner Let G
from G0 by contracting the cycles {C1 , C2 , . . . , Cβ } bounding the vortices into vertices
{c1 , c2 , . . . , cβ }, removing loops and removing parallel edges. Let TG
b be the minimum
b and let X be the set of edges that has smallest summed weight such that
spanning tree of G

Arxiv

6

Light spanners bounded treewidth graphs and H-minor-free graphs

cutting open the surface Σ along TG
b ∪ X creates a disk; |X| ≤ 2β (see, e.g. Eppstein [6]).
Since TG
⊆
MST(G)
and
an
edge
in the spanner is also the shortest path between its
b
endpoints, we have:
w(TG
b ∪ X) ≤ (2β + 1)w(MST(G))

(5)
S
β



Cutting the surface open along X ∪ TG
i=1 Ci creates β + 1 disks: one disk for each
b∪
face that a vortex is attached to and one disk ∆ corresponding to the remainder of the
surface. The boundary of ∆, ∂∆, is formed by two copies of each of the edges of TG
b ∪ X and
one copy of each of the edges in ∪βi=1 Ci (see Figure 3 in Appendix C). Therefore we can use
Equations (4) and (5) to bound the weight of the boundary of ∆:
w(∂∆) ≤ (4β + 2 + g(O(β β+2 ), )) · w(MST(G))

(6)

Let E∆ be the set of edges of G that are not in MST(G), X or any of the vortices or their
boundaries. That is, E∆ contains all the edges that we have not yet bounded. Since ∂∆
spans G0 , there is a 1-simple charging scheme to ∂∆ (less an edge, Lemma 6). Therefore, by
Lemma 5 and Lemma 4,
w(E∆ ) ≤ (1 + 1/) · (4β + 2 + g(O(β β+2 ), )) · w(MST(G))

(7)

Total weight of the spanner Since every edge of G is either in MST(G), X, E∆ or Gi ∪ Ci
(for some i), summing Equations (4), (5) and (7) gives us Equation (3):

w(G) ≤ 2 + 2β + (1 + 1/)(4β + 2 + g(O(β β+2 ), )) + g(O(β β+2 ), ) w(MST(G))
|
{z
}
q(β,)
(8)

3.3

Adding apices and clique-sums

We are now ready to prove Theorem 2 by considering the apices and clique-sums of the
decomposition. Let G = J1 ⊕ J2 ⊕ . . . ⊕ Jγ be the β(|H|)-clique-sum of β(|H|)-almostembeddable graphs J1 , J2 , . . . , Jγ given by the Graph Minor Structure Theorem. For Ji , let
Ai be its set of apices, let Ji1 , . . . , Jiβ be its set of vortices and let Ji0 be the graph embedded
on a surface of genus at most β, as provided by the definition of β(|H|)-almost-embeddable.
We assume the representation includes no edges between apices and the internal vertices of
vortices (vertices that are not in Ji0 ) by Claim 8.
Let S be the greedy (1 + )-spanner of G. For each Ji , we define Si as the set of spanner
edges in the apex-free β(|H|)-almost-embeddable part of Ji (formally, Si = S ∩ (∪` Ji` )).
Consider the spanning forest of Si that is induced by MST(G): Fi = MST(G) ∩ Si . We
choose a subset of edges Ei of Si \Fi such that:
(i) The number of components of Fi ∪ Ei is minimized.
(ii) Subject to (i), the size of Ei is minimized.
(iii) Subject to (i) and (ii), the weight of Ei is minimized.
By the choice of Ei and since Ai has no edges to the internal vertices of vortices, each tree of
Fi ∪ Ei is a minimum spanning tree for each apex-free β(|H|)-almost-embeddable component
of Si . Since Si is a subgraph of a greedy spanner, it is its own greedy spanner (Lemma 4)
and so, by Equation (3), we have w(Si ) ≤ q(β(|H|), )(w(Fi ) + w(Ei )). Summing over i, we
have:

Pγ
Pγ 
i=1 w(Si ) ≤ q(β(|H|), )
i=1 w(Fi ) + w(Ei )


Pγ
≤ q(β(|H|), ) w(MST(G)) + i=1 w(Ei )
(9)

G. Borradaile and H. Le

7

Let S(Ai ) be edges of S incident to vertices in Ai . Then, S ∩ Ji = Si ∪ S(Ai ) and hence
Sγ
S = i=1 (Si ∪ S(Ai )). Therefore, we have:
w(S) ≤

Pγ

i=1

w(Si ) +

Pγ

i=1

w(S(Ai ))

(10)

Now define Ji0 = Fi ∪ Ei ∪ S(Ai ). Then tw(Ji0 ) ≤ |Ai | + 1 ≤ β(|H|) + 1. Let G0 =
J10 ⊕ J20 ⊕ . . . ⊕ Jγ0 . We get that tw(G0 ) ≤ maxi tw(Ji0 ) ≤ β(|H|) + 1 by a result of Demaine et
al. (Lemma 3 [4]). Note that MST(G0 ) = MST(G). We have (by Lemma 4 and Equation (2)):
Pγ

i=1

w(Fi ) + w(Ei ) + w(S(Ai )) ≤ g(β(|H|) + 1, ) · w(MST(G))

(11)

By Equations 9, 10 and 11, we get Theorem 2:


w(S) ≤ (q(β(|H|), ) + 1) · g(β(|H|) + 1, ) + q(β(|H|), ) w(MST(G)).

4

The greedy spanner for bounded pathwidth graphs is light

Grigni and Hung proved that graphs of pathwidth pw have a (1 + )-spanner of lightness
O(pw3 /) [10]. They do so by building a spanning tree that is monotone with respect to the
path decomposition of weight O(pw2 ) w(MST) (Lemma 2 [10]) and devising what we observe
to be an O(pw)-simple charging scheme to the monotone spanning tree (Lemma 3 [10]).
We prove that graphs of pathwidth pw have light greedy (1 + )-spanners by showing that
there is an O(pw2 )-simple charging scheme to the MST, forgoing the need for constructing
a monotone spanning tree, giving Theorem 3. Our proof gives an evidence that one can
avoid the pathwidth-specific monotonicity argument, opening a door to show that graphs of
bounded treewidth may have light greedy (1 + )-spanners as well. We discuss the challenges
for bounded treewidth graphs at the end of the paper. Throughout this section G refers to
the greedy (1 + )-spanner of some graph of pathwidth pw.
Smooth decompositions It will be convenient for our proofs to work with a standardized
path decomposition. We assume that bags are ordered linearly, i.e, Xi and Xi+1 are adjacent
(1 ≤ i ≤ |I| − 1), and the path decomposition is smooth. A path decomposition (X , P) is
smooth if |Xi | = pw + 1 ∀i ∈ I and |Xi ∩ Xi+1 | = pw for all 1 ≤ i ≤ |I| − 1. Bodlaender [2]
showed that a path decomposition can be turned into a smooth path decomposition of the
same width in linear time. We root the path decomposition (X , P) at the bag X|I| .
For adjacent bags Xi , Xi+1 , we call the vertex in Xi+1 \Xi the introduced vertex of Xi+1
and the vertex in Xi \Xi+1 the forgotten vertex of Xi . All vertices of X1 are introduced
vertices and all vertices of X|I| are forgotten vertices.
Overview: designing an O(pw2 )-simple charging scheme In designing an O(pw2 )-simple
charging scheme, one needs to guarantee (i) each non-tree edge is charged at most once and
(ii) each tree edge3 is charged at most O(pw2 ) times. At high level, we use the charging
scheme for edges in X0 ∪ . . . ∪ Xi−1 to design a charging scheme for the edges introduced to
Xi . Let u be the introduce vertex of Xi . We need to define charging pairs for all non-tree
edges between vertices of u and Xi \ {u}.

3

A tree edge is an edge of the minimum spanning tree.

Arxiv

8

Light spanners bounded treewidth graphs and H-minor-free graphs

The simpler case is when there is a tree edge uv incident to u in Xi . For a non-tree edge
wu incident to u in Xi , we define a charging path for wu using the edges uv (a tree edge)
and vw (an edge that already has a defined charging path since vw is in a descendant bag of
Xi ). (This will be formalized as the triangle rule.) However, to guarantee condition (i), we
must prevent the use of wu in charging paths in the future. We keep track of this by way
of a charging forest whose vertices are the edges of G; in this case we add an edge to the
charging forest connecting uv and wu.
The harder case is when there is no tree edge incident to u in Xi . In this case, we consider
the u-to-v spanning-tree path that contains only edges of ancestor bags of Xi . We use this
path as a sit-in for the edge uv of the previous case. To guarantee condition (ii), we must
be careful to not use tree-edges in ancestor bags too many times. Since u may have an
ancestral spanning-tree path to multiple vertices of Xi \ {u}, we delay the choice of which
paths to use in defining a charging pair for edges incident to u by adding dashed edges to the
charging forest corresponding to all possible constructions. Then, to achieve condition (ii),
we carefully select which dashed edges to convert in defining the charging pairs for edges
incident to u in Xi .
Normalized graph We simplify the presentation of the formal argument, we use a normalized
graph which merges a graph G with its smooth path decomposition (X , P). For each bag Xi ,
define the bag graph Gi = (Xi , Ei ) to be a subgraph of G where Ei is a maximal subset of
edges of G[Xi ] incident to introduced vertices of Xi . This implies that each edge of MST(G)
appears in exactly one bag graph. For adjacent bags Xi , Xi+1 , we add edges between two
copies of the same vertex of G in Gi and Gi+1 . We call the resulting graph the normalized
graph of G with respect to the path decomposition (X , P) and denote it by GP (VP , EP ). We
assign weight 0 to edges between bag graphs and weight w(e) for the copy of the edge e in G.
See Figure 4 in Appendix C for an example. Since the distances between vertices in G and the
distances between their copies in GP are the same: w(MST(GP )) = w(MST(G)). Further,
since distances are preserved, we can define a charging scheme for the greedy (1 + )-spanner
of GP to MST(GP ). In fact, we prove:
I Theorem 9. There is a O(pw2 )-simple charging scheme for the greedy (1 + )-spanner of
GP to MST(GP ).
This theorem, along with the equivalence of the metrics of GP and G and Lemma 5, gives
Theorem 3. To simplify the construction of the charging scheme, we assume that G is a
k-path; this is without loss of generality by Lemma 7.

4.1

The charging forest

The main difficulty in defining the charging scheme is the existence of introduced vertices that
are connected to the MST via an edge that is in an ancestor bag of the path decomposition.
For the other types of introduced vertices, there is a triangle in the vertex’s bag graph that
allows us to pay for the non-tree edges incident to that vertex. Throughout this section MST
refers to MST(GP ).
To define the O(pw2 )-simple charging scheme, we construct a charging forest Φ to guide
the charging. The charging forest is a rooted spanning forest of the line graph4 of G, with

4

The nodes of the line graph of a graph G are the edges of G; the edges of the line graph are between
nodes whose corresponding edges of G share an endpoint.

G. Borradaile and H. Le

9

one tree rooted at a vertex corresponding to each edge of MST(G) (that is, each non-zero
edge of the MST(GP )). We call the nodes of Φ φ-vertices and denote a φ-vertex of Φ by
(u, v) where uv is an edge of G.
We use three types of edges in constructing Φ: dashed edges, bold edges and mixed edges.
We construct Φ iteratively; Φi will be an intermediate forest of the line graph of G[∪j≤i Xi ].
Φi may contain all three types of edges but Φ = Φ|I| will contain only bold and mixed edges.
From Φi−1 to Φi , a dashed edge may be deleted or converted to a mixed edge and newly
added edges will either all be bold or all be dashed. A dashed-free tree of Φi is a maximal
tree of Φi that contains no dashed edge. Trees of the intermediate forests may be unrooted,
but each tree of an intermediate forest will contain at most one root.
We also maintain a contracted forest Λi spanning vertices of Xi . Intuitively, Λi tells us
the connections between vertices of Xi in MST[∪j≤i Xj ]. Λi is used to handle introduced
vertices that have no tree edges to other vertices of the same bag. We also assign unique
positive rank to each edge of MST in G and assign rank 0 to all edges in MST added to GP
by the normalizing process. Ranks of edges of MST are used to define edge-rank in Λi as
follows: the rank of an edge uv in Λi , denoted by ri (uv), is the minimum rank over the edges
in the u-to-v path of MST[∪j≤i Xi ]. We assign rank to each edge of MST in a way that the
rank of each edge in Λi is unique.
The triangle rule We say that an edge ((u, v), (u, w)) of the line graph satisfies the triangle
rule if vw ∈ MST(G) and (u, v) and (u, w) are in distinct dashed-free trees, both of which
do not contain roots (i.e. φ-vertices that correspond to edges of MST(G)). We will add
edges that satisfy the triangle rule to the charging forest. To maintain the acyclicity of the
intermediate charging forests, if adding ((u, v), (u, w)) introduces a cycle, the most recently
added dashed edge on the path in the charging forest from (u, v) to (u, w) is deleted.
Invariants of the charging forest Let Φi be the charging forest for GP [∪j≤i Xj ]. We say
that a φ-vertex (u, v) of Φi is active if u, v ∈ Xi+1 . We will show that Φi satisfies the
following invariants:
(i) For two trees T1 and T2 of MST[∪j≤i Xj ], all the φ-vertices of the form (u, v) such that
u ∈ T1 and v ∈ T2 are in a common unrooted tree of Φi . Further every unrooted tree of
Φi contains φ-vertices spanning components of MST[∪j≤i Xj ].
(ii) For a tree T of MST[∪j≤i Xj ], all the φ-vertices of the form (u, v) such that u, v ∈ T are
in rooted dashed-free trees of Φi .
(iii) Each unrooted dashed-free tree of Φi contains at least one active φ-vertex.
(iv) For any j ≤ i and any two distinct trees T1 , T2 of MST[∪i`=j X` ], (yj,1 , yj,2 ) and (yi,1 , yi,2 )
are in the same unrooted dashed-free tree of Φi where y`,k ∈ Tk ∩ X` for ` = i, j and
k = 1, 2.

4.1.1

Initializing the charging forest

We define Φ1 as a forest of only bold edges. Recall that G1 is a complete graph so there is a
φ-vertex for every unordered pair of vertices in X1 . We greedily include bold edges in Φ1
that satisfy the triangle rule. Equivalently, consider the subgraph H of the line graph of G1
consisting of edges ((u, v), (u, w)) where vw ∈ MST; Φ1 corresponds to any maximal forest of
H each tree of which contains at most one root (φ-vertex corresponding to an edge of MST).
We arbitrarily assign an unique rank to each edge of MST[X1 ] from the set {1, 2, . . . , m1 }
where m1 is the number of edges of MST[X1 ] so that the highest-ranked edge is incident
to the forgotten vertex of X1 . We define Λ1 to be the forest obtained from MST[X1 ] by

Arxiv

10

Light spanners bounded treewidth graphs and H-minor-free graphs

contracting the highest-ranked edge incident to the forgotten vertex of MST[X1 ]. We observe
that each edge in Λ1 has a unique rank, since the rank of each edge of MST[X1 ] is unique.
We prove that Φ1 satisfies four invariants in Appendix B.
I Claim 10. Charging forest Φ1 satisfies all invariants.

4.1.2

Growing the charging forest

We build Φi from Φi−1 and show that Φi will satisfy the invariants using the fact that Φi−1
satisfies the invariants. Let u be the introduced vertex of non-leaf bag Xi . If u isolated
in MST[Xi ], we say that u is a free vertex. The construction of Φi from Φi−1 depends on
whether or not u is free.

u is a free vertex
Let Λi−1 be the contracted forest of Xi−1 . To obtain Φi from Φi−1 , we add φ-vertices
(u, w) ∀w ∈ (Xi \{u}) and add dashed edges ((u, wj ), (u, wk )) for each edge wj wk in Λi−1 .
We assign rank to the dashed edge ((u, wj ), (u, wk )) to be the rank of wj wk in Λi−1 . We
additionally change some dashed edges to mixed edges which we describe below. Since
converting dashed edges to mixed edges does not affect these invariants, we have:
I Claim 11. Charging forest Φi satisfies Invariants (i), (ii) and (iv).
We include the formal proof of Claim 11 in Appendix B.
Converting dashed edges to mixed edges To ensure that Φi will satisfy Invariant (iii),
we convert some dashed edges to mixed edges. First, consider the newly-added φ-vertex
(u, v) where v is the forgotten vertex of Xi . To ensure that (u, v) will be in a dashed-free
tree that contains an active φ-vertex, we convert the added dashed edge ((u, v), (u, w)), that
has highest rank among newly added dashed edges, to a mixed edge. Second, suppose that
τ is a dashed-free tree of Φi−1 such that its active φ-vertex is of the form (v, w) for some
w ∈ Xi \{u}. The tree τ is at risk of becoming inactive in Φi . However, by Invariant (i), τ
is a subtree of a component τ̂ of Φi−1 that consists of φ-vertices (u1 , u2 ) such that uk ∈ Tk
where Tk is a component of MST[∪j≤i−1 Xi ] for k = 1, 2. Further, since T1 and T2 must be
connected in MST by a path through ancestor nodes of the path decomposition, there must
be vertices in Tk ∩ Xi+1 ; w.l.o.g., we take (u1 , u2 ) to be an active φ-vertex in τ̂ . We greedily
convert dashed edges in τ̂ to mixed edges to grow τ until such an active φ-vertex is connected
to (v, w) by mixed and bold edges, thus ensuring that Φi will satisfy Invariant (iii). We break
ties between dashed edges for conversion to mixed edges by selecting the dashed edges that
were first added to the charging forest and if there are multiple dashed edges which were
added to the charging forest at the same time, we break ties by converting the dashed edges
that have higher ranks to mixed edges. Note that by converting dashed edges into mixed
edges, we add edges between dashed-free trees. Thus, Invariant (i), (ii), (iv) are unchanged.
Finally, we need to update Λi from Λi−1 . Let {v1 , v2 , . . . , vq } be the set of neighbors of v
such that ri−1 (vv1 ) ≤ . . . ≤ ri−1 (vvq ). Delete v from Λi−1 and if q ≥ 2, add edges vj vj+1
(1 ≤ j ≤ q − 1) to Λi−1 to obtained the forest Λi . Then, by definition, ri (vj vj+1 ) = ri−1 (vvj )
and ri (xy) = ri−1 (xy) for all other edges of Λi . Thus, by induction hypothesis, the rank of
each edge of Λi is unique.

G. Borradaile and H. Le

11

u is not a free vertex
To build Φi from Φi−1 , we add φ-vertices (u, w)∀w ∈ Xi \{u} and greedily add bold edges
that satisfy the triangle rule. We include the formal proof that Φi satisfies Invariant (i), (ii),
and (iv) in Appendix B.
I Claim 12. Charging forest Φi satisfies Invariants (i), (ii) and (iv).
We show that Φi satisfies Invariant (iii) here. Let v be the forgotten vertex of Xi . Note
that u may have no tree edge to the forgotten vertex of Xi . In this case, we will ensure that
previously active φ-vertices of the form (v, w) for w ∈ Xi get connected to dashed-free trees
that contain active φ-vertices, we convert dashed edges to mixed edges. We do so in the
same way as for the above described method for when u was a free vertex, guaranteeing that
Φi will satisfy Invariant (iii). Otherwise, we consider two subcases:
1. If u = v, then any φ-vertex that was active in Φi−1 is still active in Φi . Thus, (u, w) is
connected to existing φ-vertices that remain active for any w ∈ Xi \ {u}.
2. If u 6= v, then φ-vertex (x, v) will become inactive in Φi . However, (x, v) is connected to
(x, u) by the triangle rule or it was already connected to a root in a dashed-free tree. In
either case, Φi satisfy Invariant (iii).
Finally, we show how to update Λi . Let v be the forgotten vertex of Xi and u1 , u2 , . . . , up be
neighbors of u in MST[Xi ] such that u1 = v if uv ∈ MST[Xi ]. Let r0 be the maximum rank
of over ranked edges of MST[∪j≤i−1 Xj ]. We assign rank ri (u, uj ) = r0 + j for all 1 ≤ j ≤ p.
We will update Λi from Λi−1 depending on the relationship between u and v:
1. If u = v, then we add edges p − 1 edges uj uj+1 , 1 ≤ j ≤ p − 1, to Λi−1 .
2. If u 6= v and uv ∈ MST[Xi ], we replace v in Λi−1 by u and add p edges uuj to Λi−1 .
3. Otherwise, we add u and p edges uuj to Λi−1 . Let {v1 , v2 , . . . , vq } be the set of neighbors
of v such that ri−1 (vv1 ) ≤ . . . ≤ ri−1 (vvq ). We delete v from Λi−1 and add q − 1 edges
vj vj+1 .
I Claim 13. Each edge of the forest Λi has a distinct rank.
We include the proof of Claim 13 in Appendix B. See Figure 5 in Appendix C for an example
of a charging forest and contracted forests.

4.1.3

Using the charging forest to define an O(pw2 )-simple charging
scheme

By Invariant (ii), all trees in Φ are rooted at φ-vertices correspond to edges of MST. Order
the edges of E(G)\MST(G) given by DFS pre-order of Φ. Let (ui−1 , vi−1 ) and (ui , vi ) (i ≥ 2)
be two φ-vertices of a component T of Φ in this order. Define Pi to be the (unique) ui -to-vi
path in T ∪ {(ui−1 , vi−1 )} that contains the edge (ui−1 , vi−1 ). We take (Pi , (ui , vi )) to be
the charging pair for (ui , vi ). Note that the roots of Φ are edges of MST(G), so the charging
paths are well-defined.
We prove that the charging scheme defined by the charging pairs is O(pw2 )-simple by
bounding the number of times non-zero edges of MST are charged to. By the triangle
rule, if ((u, v), (u, w)) is a bold edge of Φ, then vw ∈ MST. We call the set of 3 vertices
{u, v, w} a charging triangle. If ((u, v), (u, w)) is a mixed edge, vw ∈
/ MST(G). In this
case, we call {u, v, w} a charging pseudo-triangle. The v-to-w path in MST(G) is called the
pseudo-edge; vw is said to be associated with the charging (pseudo-) triangle. We say the
edge ((u, v), (u, w)) represents the charging (pseudo-) triangle.

Arxiv

12

Light spanners bounded treewidth graphs and H-minor-free graphs

I Claim 14. There are at most pw − 2 charging triangles associated with each non-zero edge
of MST.
Proof. A charging triangle consists of one non-zero weight edge of MST and one edge not in
the MST in the same bag graph. Note that each non-zero weight edge of MST is in exactly
one bag graph and each bag graph has at most pw − 2 edges not in the MST; that implies
the claim.
J

The proof of the following is in Appendix B.
I Lemma 15. Each edge of MST(G) is in the paths corresponding to the pseudo-edges of at
most 2pw2 charging pseudo-triangles.
Consider each charging pair (Pi , (ui , vi )) in which Pi contains (ui−1 , vi−1 ) that precedes
(ui , vi ) in the DFS pre-order of a given component of Φ. Let (ui , vi ) = (û0 , v̂0 ), . . . , (ût , v̂t ) =
(ui−1 , vi−1 ) be the set of φ-vertices of the path between (ui , vi ) and (ui−1 , vi−1 ) in Φ. We
define Qj (1 ≤ j ≤ t) be the ûj−1 -to-v̂j−1 path of MST ∪ {(ûj , v̂j )} containing edge ûj v̂j .
Then we have:
Pi = Q1

Q2

...

Qt

where is the symmetric difference between two sets. Hence, charging tree edges of Pi is
equivalent to charging the tree edges of Q1 , Q2 , . . . , Qt . We observe that tree edges of Qj
are the tree edges of the (pseudo-) triangle represented by ((ûj , v̂j ), (ûj−1 , v̂j−1 )). Since each
edge of Φ appears twice in the collection of paths between (ui , vi ) and (ui−1 , vi−1 ) in Φ for
all i and since different edges of Φ represents different charging (pseudo-) triangles, the tree
edges of each charging (pseudo-) triangle are charged to twice. By Claim 14 and Lemma 15,
each non-zero tree edge is charged to by at most 2(pw − 2) + 2(2pw2 ) = O(pw2 ) times. Hence,
the charging scheme is O(pw2 )-simple.

4.2

Toward light spanners for bounded treewidth graphs

The main difficulty in designing a simple charging scheme for bounded pathwidth graphs is
the existence of free vertices. We introduce dashed edges to the charging forest when we
handle free vertices and change a subset of dashed edges into mixed edges. By changing a
dashed edge, say ((w, u), (w, v)) into a mixed edge, we charge to the u-to-v path in the MST
once. Unfortunately, for bounded treewidth graphs, such charging can be very expensive.
However, we observe that the φ-vertex (v, w) is contained in a rooted tree of Φ. That means
we can used vw to charge to one of two edges uv or uw. In general, for each non-tree edge
uv of the spanner in a bag Xi , we say uv is a simple edge if u, v are in the same component
of the MST restricted to descendant bags of Xi only or ancestor bags of Xi only. Simple
edges can be paid for in the spanner “cheaply”. Now, if uv be an edge of the spanner in
Xi such that the u-to-v path PMST (u, v) of MST crosses back and forth through Xi . Let
w1 , w2 , . . . , wk be the set of vertices of Xi in this order on the path PMST (u, v). Then, we
can charge the edge uv by the set of simple edges uw1 , w1 w2 , . . . , wk v. We believe that this
idea, with further refinement, will prove the existence of light spanners for bounded treewdith
graphs.

G. Borradaile and H. Le

13

References
1
2

3

4

5
6

7

8

9

10

11

12
13
14

I. Althofer, G. Das, D. Dobkin, D. Joseph, and L. Soares. On sparse spanners of weighted
graphs. Discrete and Computational Geometry, 9(1):81–100, 1993.
H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth.
In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC ’93,
pages 226–234. ACM, 1993.
E. Demaine, M. Hajiaghayi, and K. Kawarabayashi. Contraction decomposition in Hminor-free graphs and algorithmic applications. In Proceedings of the 43rd Annual ACM
Symposium on Theory of Computing, page to appear, June 6–8 2011.
E. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, and D. Thilikos. Approximation
algorithms for classes of graphs excluding single-crossing graphs as minors. Journal of
Computer and System Sciences, 69(2):166–195, 2004.
D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275–
291, 2000. Special issue on treewidth, graph minors, and algorithms.
D. Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the
14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘03, pages 599–608,
2003.
A. Filtser and S. Solomon. The greedy spanner is existentially optimal. In Proceedings of
the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, pages 9–17,
2016.
M. Grigni. Approximate tsp in graphs with forbidden minors. In Automata, Languages and
Programming, volume 1853 of Lecture Notes in Computer Science, pages 869–877. Springer
Berlin Heidelberg, 2000.
M. Sigurd and M. Zachariasen. Construction of Minimum-Weight Spanners. In Proceedings
of the 12th Annual European Symposium on Algorithms, ESA’04, pages 797–808. SpringerVerlag, 2004.
M. Grigni and H. Hung. Light spanners in bounded pathwidth graphs. In Proceedings
of the 37th International Conference on Mathematical Foundations of Computer Science,
MFCS’12, pages 467–477. Springer-Verlag, 2012.
M. Grigni and P. Sissokho. Light spanners and approximate tsp in weighted graphs with
forbidden minors. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’02, pages 852–857, Philadelphia, PA, US, 2002. Society for Industrial
and Applied Mathematics.
M. Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica, 23(4):613–632, 2003.
F. Mazoit. Tree-width of hypergraphs and surface duality. Journal of Combinatorial Theory,
Series B, 102(3):671–687, 2012.
N. Robertson and P.D. Seymour. Graph minors. XVI. Excluding a non-planar graph.
Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003.

Arxiv

14

Light spanners bounded treewidth graphs and H-minor-free graphs

A

Notation

We denote G = (V (G), E(G)) to be the graph with vertex set V (G) and edge set E(G) and
use n, m to denote the number of vertices and edges, respectively. The order of G, denoted
by |G|, is the number of vertices of G. Each edge e of E(G) is a assigned a weight w(e). We
P
define w(H) = e∈E(H) w(e) to be the weight of edges of a subgraph H of G. The minimum
spanning tree of G is denoted by MST(G). For two vertices u, v, we denote the shortest
distance between them by dG (u, v). Given a subset of vertices S and u a vertex of G, we
define dG (u, S) = minv∈S {dG (u, v)} for v = arg minv∈S {dG (u, v)}. We omit the subscript G
when G is clear from context. The subgraph of G induced by S is denoted by G[S].

B

Omitted Proofs

Proof of Lemma 4. Let SH be the greedy (1 + )-spanner of H. We will prove that SH = H.
Note that SH is a subgraph of H and shares the same set of vertices with H. Suppose
for a contradiction that there is an edge e = uv ∈ H \ SH . Since uv is not added to the
greedy spanner of H, there must be a u-to-v-path PSH (uv) in SH that witnesses the fact
that uv is not added (i.e. (1 + )w(e) > w(PSH (uv))). However, PSH (uv) ⊆ S, contradicting
Equation 1.
J
Proof of Lemma 5. If S has a k-simple charging scheme then:
X
(1 + )w(S\T ) ≤
w(PS (e)) ≤ k · w(T ) + w(S\T )
e∈S\T

where the first inequality follows from edges in S\T having charging paths and the second
inequality follows from each edge in T appearing in charging paths at most k times and each
edge in S\T appearing in charging paths at most once. Rearranging the left- and right-most
sides of this inequality gives us Lemma 5.
J
Proof of Lemma 6. Let e be the edge on the boundary of G that is not in T . Let T ∗ be
the spanning tree of the dual graph containing all the edges that do not correspond to edges
of T . We construct a charging scheme for G by traversing T ∗ in post-order, considering all
the non-outer faces. Consider visiting face f with children f1 , . . . , fk and parent f0 . Let ei
be the edge of G between f and fi for all i and let P0 be the path between e0 ’s endpoints
in T ∪ {e1 , e2 , . . . , ek } that contains all the edges {e1 , e2 , . . . , ek }. Then, by Equation 1,
(e0 , P0 ) is a charging pair for e0 . Also, since we visit T ∗ in post-order, none of the edges
{e1 , e2 , . . . , ek } will be charged to when we build charging pairs for higher-ordered edges
which are edges between faces of higher orders. Thus, the set of charging pairs produced
from this process is a 1-simple charging scheme to T .
J
1 e 10
2

9

3

8
4

7
5

6

Figure 1 An outer planar graph G. Bold edges are edges of T , dashed edges are non-tree edges
and dotted edges are edges of the dual spanning tree, less the dual of e.

G. Borradaile and H. Le

15

Proof of Lemma 7. Consider an edge ê ∈ Ŝ \ S. We first argue that Ŝ \ {ê} has a weak
k-simple charging scheme. Since T ⊆ S ∩ Ŝ, ê ∈
/ T and so ê can be charged to at most once.
If ê is in the charging path PŜ (e) for another edge e of Ŝ, then we define the charging path
for e to be the simple path between e’s endpoints that is in PŜ (e) ∪ PŜ (ê) \ {ê}. The resulting
set of paths is a weak k-simple charging scheme since every edge of PŜ (ê) is charged to one
fewer time (by the removal of ê) and at most once more (by e).
By induction, S has a weak k-simple charging scheme to T . Since S is a greedy spanner,
Equation (1) holds for every charging pair, so the weak k-simple charging scheme to T is a
k-simple charging scheme to T .
J
Proof of Claim 8. Let Va be the set of vertices in vortex V that are adjacent to apex a. Split
vertex a into two vertices a and aV connected by a zero-weight edge so that aV ’s neighbors
are Va ∪ {a} and so that contracting the zero-weight edge gives the original graph. Add aV
to all of the bags of the path decomposition of V . Now all the edges that connected a to V
are within the vortex.
Consider the face in the surface-embedded part of the β-almost-embeddable graph to
which V is attached and let xy be edge in that face that is between the first and last bags of
V and such that y is in the first bag of V . Add the edges xaV and aV y to the embedded
part of the graph and give them weight equal to the distance between their endpoints. Now
xaV is the edge in that face that is between the first and last bags of the vortex and a is
adjacent to a vertex that is in the surface-embedded part of the β-almost-embeddable graph.
See Figure 2.
The splitting of a into aV increases the pathwidth of the vortex by 1. Repeating this
process for all apex-vortex pairs increases the pathwidth of each vortex by at most β.

x

y

a

(a)

a

y

x
aV

y

(b)

Figure 2 Apex a and the vortices it is adjacent to before (a) and after (b) the reduction of
Claim 8

J
Proof of Claim 10. Note first that since there are only bold edges, the dashed-free trees of
Φ1 are just the trees of Φ1 .

Arxiv

16

Light spanners bounded treewidth graphs and H-minor-free graphs

Invarint (i) Consider distinct trees T1 and T2 of MST[X1 ] and consider x, y ∈ T1 and
z ∈ T2 . The φ-vertices (x, z) and (y, z) are in the same component of H as witnessed by
the edges of the x-to-y path in T1 . Further, (x, z) cannot be connected to (x, u) in H where
xu ∈ MST since that would imply xz ∈ MST, contradicting that T1 and T2 are distinct
trees of MST[X1 ]. Therefore, there is a maximal unrooted tree of H that will contain all the
φ-vertices of the form (u, v) such that u ∈ T1 and v ∈ T2 .
Invariant (ii) Consider a path u0 , u1 , . . . , uk in MST[X1 ] for k ≥ 2; ((u0 , ui ), (u0 , ui+1 )) are
edges in H for i = 1, . . . , k − 1. Therefore (u0 , u1 ) (a root) and (u0 , uk ) are in a common
component of H. Therefore any maximal tree of H that contains (u0 , uk ) will contain a root.
(iii) Consider the component of H described in showing Φ1 satisfies Invariant (i). Since T1 and
T2 must be connected in MST by a path through ancestor nodes of the path decomposition,
there is a vertex ui ∈ Ti such that ui ∈ X2 for i = 1, 2. Therefore (u1 , u2 ) is an active
φ-vertex in this component of H and will be included in the maximal tree of this component.
Invariant (iv)

In this case, Invariant (iv) reduces to Invariant (i).

J

Proof of Claim 11. We show that Φi satisfies Invariants (i), (ii) and (iv) in turn:
(i) The only new tree of MST[∪j≤i X` ] compared to MST[∪j≤i−1 X` ] is u. For any pair
of trees in MST[∪i−1
`=j X` ], Invariant (i) holds for Φi because it helps for Φi−1 . For a
component C of Λi−1 , the addition of the edges ((u, wj ), (u, wk )) creates a new (unrooted)
component spanning all φ-vertices (u, v) where v is in the corresponding component of
MST[∪j≤i Xj ]. Therefore, Invariant (i) holds for Φi .
(ii) Since u is free and no new φ-vertices of the form (u, v) where u and v are in the same
tree of MST[∪j≤i Xj ] are introduced, Invariant (ii) holds for Φi because it holds for Φi−1 .
(iv) As with (i), the only new tree of MST[∪i`=j X` ] is u, which only has a non-zero intersection
with Xi . So, for j < i, Invariant (iv) holds for Φi because it holds for Φi−1 . For j = i, all
the components of MST[∪i`=j X` ] are isolated vertices, so the invariant holds trivially.
J
Proof of Claim 12. We prove that Φi satisfies each of the invariants in turn.
Invariant (i) Let T1 and T2 be distinct trees of MST[∪j≤i Xj ]. If T1 and T2 are distinct
trees of MST[∪j≤i−1 Xj ], then the invariant holds for Φi because it holds for Φi−1 . Otherwise, we may assume w.l.o.g. that T1 contains u and a subtree T3 that is a component of
MST[∪j≤i−1 Xj ]. Let x be a vertex of T3 ∩ Xi and w be a vertex of T2 ∩ Xi . Then ux is an
edge of MST and (u, w), (w, x) will be connected in Φi by greedy applications of the triangle
rule. By the same argument as used for showing that Φ1 satisfies Invariant (i), (u, w) will
not be connected to a root φ-vertex (a φ-vertex corresponding to a tree edge) in Φi .
Invariant (ii) We need only prove this for the tree T of MST[∪j≤i Xi ] that contains u as
other cases are covered by the fact that Φi−1 satisfies Invariant (ii). Let T1 and T2 be distinct
trees of MST[∪j≤i−1 Xi ] that are subtrees of T . Let u1 and u2 be vertices of T1 ∩ Xi and
T2 ∩ Xi , respectively.
We start by showing that (u1 , u2 ) is in a rooted dashed free tree of Φi . Let v1 and v2
be the neighbors of u in T1 and T2 , respectively. (Note, it may be that, e.g., u1 = v1 .) By
Invariant (ii), (v2 , u2 ) is in a rooted dashed-free tree of Φi−1 . By the triangle rule, (v1 , u2 )
will be connected by (a possibly non-trivial sequence of) bold edges to (u, u2 ) which in turn

G. Borradaile and H. Le

17

will be connected by (a possibly non-trivial sequence of) bold edges to (v2 , u2 ). Therefore,
(v1 , u2 ) will be in a rooted dashed-free tree of Φi . In this next paragraph, we show that
(u1 , u2 ) and (v1 , u2 ) are in the same dashed-free tree of Φi−1 , which we have just shown
belongs to a rooted dashed-free tree of Φi , showing that (u1 , u2 ) is in a rooted dashed free
tree of Φi .
To show that (u1 , u2 ) and (v1 , u2 ) are in the same dashed-free tree of Φi−1 , consider an
index k such that u1 and v1 are connected to x1 in MST[∪i`=k X` ] and u2 is connected to x2
in MST[∪i`=k X` ]. Then by Invariant (iv) for Φi−1 , (x1 , x2 ) is in the same dashed-free tree as
(u1 , u2 ) and (v1 , u2 ).
Now consider a φ-vertex (x1 , x2 ) where xk ∈ Tk ∩ Xj for k = 1, 2 and j < i. Let Tk0 be
0
the subtree of Tk that is in MST[∪i−1
`=j X` ] and let uk = Tk ∩ Xi for k = 1, 2. We just showed
that (u1 , u2 ) is in a rooted dashed-free tree of Φi . By Invariant (iv) for Φi−1 , (x1 , x2 ) and
(u1 , u2 ) are in the same dashed-free tree. Therefore, (x1 , x2 ) is in a rooted dashed-free tree
of Φi .
Invariant (iv) Consider j ≤ i, trees T1 , T2 of MST[∪i`=j X` ], and φ-vertices (yj,1 , yj,2 ) and
(yi,1 , yi,2 ) as defined in Invariant (iv). For the case j = i, the proof that Φi satisfies
Invariant (iv) is the same as for Φ1 . Further, if u ∈
/ T1 , T2 , Φi satisfies Invariant (iv) because
Φi−1 satisfies Invariant (iv), therefore, we assume w.l.o.g. that u ∈ T1 . Finally, consider
the components of T1 in MST[∪i−1
`=j X` ]; if yj,1 and yi,1 are in the same component, then Φi
satisfies Invariant (iv) because Φi−1 satisfies Invariant (iv). Therefore, we assume they are in
different components, T1p and T1q , respectively.
Let x be the neighbor of u in T1p . By Invariant (iv) for Φi−1 , (x, yi,2 ) and (yj,1 , yj,2 ) are in
a common unrooted dashed-free tree. We show that (x, yi,2 ) and (yi,1 , yi,2 ) are in a common
unrooted dashed-free tree of Φi , proving this invariant is held. Let y be the neighbor of u in
T1q .
1. By the triangle rule, (x, yi,2 ) will get connected by (a possibly non-trivial sequence of)
bold edges to (u, yi,2 ) because xu ∈ MST and (u, yi,2 ) will get connected by (a possibly
non-trivial sequence of) bold edges to (y, yi,2 ) because yu ∈ MST.
2. Let k be the index such that y and yi,1 are connected to a in MST[∪i`=k X` ] and yi,2 is
connected to b in MST[∪i`=k X` ]. Then by Invariant (iv), (a, b) is in the same unrooted
dashed-free tree as (y, yi,2 ) and (yi,1 , yi,2 ).
Together these connections show that (x, yi,2 ) and (yi,1 , yi,2 ) are in a common unrooted
dashed-free tree.
J
Proof of Claim 13. We prove the claim for each case of the construction of Λi :
1. If u = v, we only add new edges to Λi−1 to obtain Λi . Since each added edge has distinct
rank that is larger than the ranks of edges of Λi−1 , the claim follows.
2. If u 6= v and uv ∈ MST[Xi ], since ri (xy) = ri−1 (xy) for any edge xy such that x, y 6= u,
we only need to consider the case when u ∈ {x, y}. Observe that for each neighbor w
of u, ri (uw) = ri−1 (vw) if vw ∈ Λi−1 or uw is among the edges that are added to Λi−1 .
Since each newly added edge has unique rank, the claim follows.
3. Otherwise, we have ri (vj vj+1 ) = ri−1 (v)vj for 1 ≤ j ≤ p − 1 and ri (xy) = ri−1 (xy) for
all other edges. Thus, each edge in Λi has unique rank by the induction hypothesis.
J
r
Let wk (k = 1, 2) be a vertex in Ni−1
(vk ) ∪ {vk } such that:

Proof of Lemma 15. We investigate how dashed edges are changed into mixed edges as
this is when a charging pseudo-triangle arises. Recall that dashed edges are added to Φ

Arxiv

18

Light spanners bounded treewidth graphs and H-minor-free graphs

when we process free vertices. Let u be a free vertex that is introduced in bag Xi and
let ((u, v1 ), (u, v2 )) be a mixed edge (that is, a dashed edge in Φi that is later converted
to a mixed edge). Then by our construction, v1 and v2 are in the same component of
MST[∪k≤i−1 Xk ]. For each j ≥ i and w ∈ Xi , let Twij be the component of MST[∪i≤k≤j Xk ]
containing w. We will say that an introduced vertex of a bag Xj is branching if it is not free,
is not the forgotten vertex of Xj and is not connected to the forgotten vertex of Xj by MST.
Note that dashed edges are converted to mixed edges when processing free and branching
vertices.
We say that a tree Twij ∈ MST[∪i≤k≤j Xk ] is forgotten in Xj if j = |I| or :
Twij ∩ Xj = {v} which is the forgotten vertex of Xj .
the introduced vertex of Xj is branching or free.
We note that at most one tree can be forgotten in each bag Xj .
r
For each vertex x ∈ Λi−1 , let Ni−1
(x) be the set of vertices in Λi−1 reachable from x via
ij
ij
r
paths consisting of edges of ranks larger than r in Λi−1 . Let Fx,r
= ∪w∈Ni−1
(x)∪{x} Tw . We
ij
ij
say that the forest Fx,r
is forgotten in Xj if every tree in Fx,r
is forgotten in Xj 0 for some
0
ij
j ≤ j and Fx,r ∩ Xj 6= ∅.
I Claim 16. Let r be the rank of the edge v1 v2 ∈ Λi−1 . If the dashed edge ((u, v1 ), (u, v2 )) is
changed into a mixed edge, there exists a bag Xj for j ≥ i such that Tuij ∩ {Fvij1 ,r ∪ Fvij2 ,r } = ∅,
Tuij ∩ Xj 6= ∅ and exactly one of the forests Fvij1 ,r , Fvij2 ,r is forgotten in Xj .
Proof. Suppose that the claim fails, then there are two cases:
1. There exists j ≥ i such that Tuij = Twij for some w ∈ Fvij1 ,r and Fvij2 ,r ∩ Xj 6= ∅. In this
case, i < j since u is a free vertex. Let p be the index such that u and w are connected
r
to x in MST[∪i≤q≤p Xq ]. Let wk (k = 1, 2) be a vertex in Ni−1
(vk ) ∪ {vk } such that:
ij
(i) Twk ∩ Xp 6= ∅
(ii) Subject to (i), the distance dΛi−1 (wk , vk ) is minimum.
Let yk = Twijk ∩ Xp . Since the tie-breaking rule prefers changing the dashed edges of
higher ranks into mixed edges, (u, vk ) is in the same dashed-free tree of Φp as (u, wk ). By
Invariant (iv), (u, wk ) and (w, wk ) are in the same dashed-free tree of Φp as (x, yk ). Since
(w, wk ) is in a rooted dashed-free tree of Φp , by Invariant (i), (u, vk ) is in a rooted dashed
free tree. Therefore, the dashed edge ((u, v1 ), (u, v2 )) is not converted to a mixed edge.
2. There exists j ≥ i such that Tuij is forgotten and both forests Fvij1 ,r , Fvij2 ,r are not forgotten
in Xj . Since u is a free vertex, there must be a vertex û in Xi such that û ∈ Tuij . Let p be
the index such that u and û are connected to x in MST[∪i≤q≤p Xq ]. Let wk (k = 1, 2) be a
r
vertex in Ni−1
(vk ) ∪ {vk } as in the first case and yk = Twijk ∩ Xp . Then, by the tie-breaking
rule, (u, vk ) and (u, wk ) are in the same dashed-free tree of Φp . By Invariant (iv), (u, wk )
and (û, wk ) are in the same dashed-free tree of Φp as (x, yk ). Therefore, there is a cycle
in which ((u, v1 ), (u, v2 )) is the most recent added dashed edge. Thus, ((u, v1 ), (u, v2 )) is
deleted and not converted to a mixed edge.
J
We now bound the number of pseudo-triangles that contain an edge e of MST(G). Let Xi
be the bag that containing e and Λi be the corresponding contracted forest. Let u0 , v0 be
two vertices of Λi in the same tree of Λi such that e is in the u0 -to-v0 path PMST (u0 , v0 ).
We say that a pseudo-triangle strongly contains PMST (u0 , v0 ) if PMST (u0 , v0 ) is a subpath of
the pseudo-edge and the rank of every edge of the psedudo-edge of the triangle is at least
the minimum rank over edges of PMST (u0 , v0 ).
I Claim 17. There are at most pw pseudo-triangles strongly containing PMST (u0 , v0 ).

G. Borradaile and H. Le

19

Proof. Let ∆1 , . . . , ∆q be pseudo-triangles that strongly contain PMST (u0 , v0 ). Let ∆k =
{uk , vk , wk } and Xsk be the bag that has wk as the introduced vertex (1 ≤ k ≤ q). Let
r be the minimum rank over edges of PMST (u0 , v0 ) and X` be the bag in which one of
the forests Fui`0 ,r , Fvi`0 ,r , say Fui`0 ,r , is forgotten. Then, uk ∈ Fui`0 ,r and vk ∈ Fvi`,r
. We can
0
sk `
i`
assume w.l.o.g that s1 ≤ s2 ≤ . . . ≤ sq . Then, Fuk ,r = Fu0 ,r ∩ MST[∪sk ≤j≤` Xj ] and
Fvskk,r` = Fvi`0 ,r ∩ MST[∪sk ≤j≤` Xj ]. By Claim 16, Twskk` ∩ X` 6= ∅. Furthermore, all the tree
s `

Twskk` must be disjoint since otherwise, say Twjj is a subtree of Twskk` (k ≤ j), the second case
of the proof of Claim 16 implies that the dashed edge ((wj , uj ), (wj , vj )) is removed from Φ.
Hence, q ≤ pw.
J
Let e be an arbitrary edge of MST(G). Let Xi be the bag that containing e and Λi be
the corresponding contracted forest. By the way we build the contracted forest, there are
at most two edges, say u0 v0 and v0 w0 , of Λi that are incident to the same vertex v0 such
that e ∈ PMST (u0 , v0 ) ∩ PMST (v0 , w0 ). We observe that any pseudo-triangle that contains e
in the pseudo-edge must contain the path PMST (u, v) for some u, v ∈ Λi such that one of
two edges u0 v0 , v0 w0 is in the path PΛi−1 (u, v). Let Γ(u0 , v0 ) be the set of pseudo-triangles
that have PΛi−1 (u, v) containing u0 v0 . We define Γ(v0 , w0 ) similarly. We will show that
|Γ(u0 , v0 )|, |Γ(u0 , w0 )| ≤ pw2 , thereby, proving the lemma.
We only need to show that |Γ(u0 , v0 )| ≤ pw2 since |Γ(u0 , w0 )| ≤ pw2 can be proved
similarly. Let ∆1 , ∆2 , . . . , ∆p be the pseudo-triangles containing e in the pseudo-forest such
that for each k:
1. Each triangle ∆k contains distinct path PMST (uk , vk ) as subpath in the pseudo-edge.
2. Edge u0 v0 is in the path PΛi−1 (uk , vk ) of Λi−1 .
3. Each path PMST (uk , vk ) has distinct rank.
Then, by the way we construct the contracted forest, if the minimum rank over edges of
PMST (uj , vj ) is smaller than the minimum rank over edges of PMST (uk , vk ), then PΛi (uk , vk ) (
PΛi (uj , vj ) for 1 ≤ j 6= k ≤ p. Therefore, we can rearrange ∆1 , ∆2 , . . . , ∆k such that
PΛi (u1 , v1 ) ( PΛi (u2 , v2 ) ( . . . ( PΛi (up , vp ). Thus, p ≤ pw . By Claim 17, for each k,
there are at most pw pseudo-triangles containing the same subpath PMST (uk , vk ). Therefore,
|Γ(u0 , v0 )| ≤ pw2 .
J

C

Figures
(1)

(2)

Figure 3 The surface (2) is obtained by cutting the surface Σ in (1) along TG
b ∪ X. Small ovals
are cycles C1 , C2 , . . . , Cβ .

Arxiv

20

Light spanners bounded treewidth graphs and H-minor-free graphs

6

5

7

4

8

3

2
1
3

1,3,8

3

3,4,8

8
3
1

(2)

2

1
1,2,3

(1)

4,7,5

4,8,7

4
8

4

7
8

(3)

7,4,6

7

5
4

5

6
7

Figure 4 The normalized graph (3) of a graph (1) with path decomposition (2). Bold edges in
(3) are edges of the original graph and thin edges in (3) are zero weighted edges.

G. Borradaile and H. Le

7

2

1

21

9

X3

X4 X5

10

15

14

13

12

11

8

16

17

18

3

6
4

5

X1

X2
2
5

1
3

3

4

3

1
3

5

2

7

6

2

2

8

12

3
2

(1,2)

(8,5)

(1,4)
(1,5)
(1,6)

(2,6)

(7,2)

(8,7)

(10,8)

12

11

13

12

16

(13,8)

9

(15,14)

2

11

(7)
17
12

12

14
13

16

(12)

(11)
(14,8)

3
3

12

14

12

(16,11)

(14,13)

(17,13)
(17,14)

(14,11)

(18,17)
(18,14)

(16,14)

(14,12)

(12,8)

(14,9)

(10,3)

(15,11)

(13,11)

(11,3)

(3,5)

11

13

2

10

(6)

9

13

(9,8)

(3,4)

9

(5)

(11,8)

(8,4)

(2,5)
(1,3)

(4)

(11,3)

(8,3)

(2,4)

9

4

9

2

3

(10)

(9)

(8,2)
(2,3)

4

12

11

(8)

5

8

3
2

3

2

7

2

2

11

3

9

9

10

3

(3)

(2)

(1)

1

4

4

3

3

7
5

X6 X7 X8 X9 X10 X11 X12 X13

(16,13)

(17,16)

(18,16)

(15,12)

(12,3)

(13,12)

(17,12)

(18,12)

(17,9)

(18,9)

(15,9)

(3,6)

(7,3)

(13,9)

(9,3)

(4,5)

(10,4) (11,10)

(4,6)

(7,4)

(9,4)

(5,6)

(7,5)

(9,5)

(7,6)

(16,12)

(12,11)

(11,9)
(10,9)

(16,9)

(12,9)

(9,7)
(15,13)

(10,5)

(11,4)

(12,10)

Figure 5 Top: A normalized graph and its MST. Dotted edges are non-tree edges. Non-dotted
edges are edges of the MST. Thin edges are zero weighted edges. Center: Contracted forest
Λ1 , . . . , Λ12 . Small numbers are ranks of the edges of the contracted forests. Bottom: Charging
forest for the graph. Dotted edges are mixed edges. Hollow vertices are roots of the charging forest

Arxiv

