On constant multi-commodity flow-cut gaps
for directed minor-free graphs

arXiv:1711.01370v1 [] 4 Nov 2017

Ario Salmasi∗

Anastasios Sidiropoulos†

Vijay Sridhar‡

Abstract
The multi-commodity flow-cut gap is a fundamental parameter that affects the performance
of several divide & conquer algorithms, and has been extensively studied for various classes of
undirected graphs. It has been shown by Linial, London and Rabinovich [15] and by Aumann
and Rabani [3] that for general n-vertex graphs it is bounded by Oplog nq and the GuptaNewman-Rabinovich-Sinclair conjecture [9] asserts that it is Op1q for any family of graphs that
excludes some fixed minor.
The flow-cut gap is poorly understood for the case of directed graphs. We show that for
uniform demands it is Op1q on directed series-parallel graphs, and on directed graphs of bounded
pathwidth. These are the first constant upper bounds of this type for some non-trivial family of
directed graphs. We also obtain Op1q upper bounds for the general multi-commodity flow-cut
gap on directed trees and cycles. These bounds are obtained via new embeddings and Lipschitz
quasipartitions for quasimetric spaces, which generalize analogous results form the metric case,
and could be of independent interest. Finally, we discuss limitations of methods that were
developed for undirected graphs, such as random partitions, and random embeddings.
∗

Dept. of Computer Science & Engineering, The Ohio State University, salmasi.1@osu.edu.
Dept. of Computer Science, University of Illinois at Chicago, sidiropo@uic.edu.
‡
Dept. of Computer Science & Engineering, The Ohio State University, sridhar.38@osu.edu.

†

1

Introduction

The multi-commodity flow-cut gap is a fundamental parameter that has been proven instrumental
in the design of routing and divide & conquer algorithms in graphs. Bounds on this parameter
generalize the max-flow/min-cut theorem, and lead to deep connections between algorithm design,
graph theory, and geometry [15, 3, 2]. While the flow-cut gap for several classes of undirected graphs
has been studied extensively, the case of directed graphs is poorly understood despite significant
efforts. In this work we make progress towards overcoming this limitation by showing constant
flow-cut gaps for some directed graph families. Consequently we also develop constant-factor approximation algorithms for certain directed cut problems on these graphs.

1.1

Multi-commodity flow-cut gaps

A multi-commodity flow instance in an undirected graph G is defined by two non-negative functions:
c : EpGq Ñ R and d : V pGq ˆ V pGq Ñ R. We refer to c and d as the capacity and demand functions
respectively. The maximum concurrent flow is the maximal value ε such that for every u, v P V pGq,
ε ¨ dpu, vq can be simultaneously routed between u and v, without violating the edge capacities. We
refer to this value as maxflowpG, c, dq.
For every S Ď V pGq, the sparsity of S is defined as follows:
ř
pu,vqPEpGq cpu, vq|1S puq ´ 1S pvq|
ř
,
u,vPV pGq dpu, vq|1S puq ´ 1S pvq|
where 1S : V pGq Ñ t0, 1u is the indicator variable for membership in S. The sparsity of a cut is
a natural upper bound for maxflowpG, c, dq. The multi-commodity max-flow min-cut gap for G,
denoted by gappGq, is the maximum gap between the value of the flow and the upper bounds
given by the sparsity formula, over all multi-commodity flow instances on G. The flow-cut gap
on undirected graphs has been studied extensively, and several upper and lower bounds have been
obtained for various graph classes. The gap is referred to as the uniform multi-commodity flow-cut
gap for the special case where there is a unit demand between every pair of vertices. Leighton
and Rao [14] showed that the uniform flow-cut gap is Θplog nq in undirected graphs. Subsequently
Lineal, London and Rabinovich [15] showed that the non-uniform multi-commodity flow-cut gap
for the Sparsest Cut problem with k demand pairs is upper bounded by Oplog kq. Besides these
there are various studies of the flow-cut gap for specific graph families. A central conjecture posed
by Gupta, Newman, Rabinovich, and Sinclair in [9] asserts the following.
Conjecture 1 (GNRS Conjecture [9]). For every family of finite graphs F, we have gappFq “ Op1q
iff F forbids some minor.
Conjecture 1 has been verified for the case of series-parallel graphs [9], Op1q-outerplanar graphs
[5], Op1q-pathwidth graphs [13], and for some special classes of planar metrics [18]. For graphs
excluding any fixed minor the flow-cut gap with k terminal pairs is known to be Op1q for uniform
demands and Oplog kq for arbitrary demands [11].
For the case of directed graphs, the flow-cut gap is defined in terms of the Directed NonBipartite Sparsest Cut problem which is an asymmetric variant of the Sparsest Cut problem, and
is defined as follows. Let G be a directed graph and let c : EpGq Ñ Rě0 be a capacity function.
Let T “ tps1 , t1 q, ps2 , t2 q, . . . , psk , tk qu be a set of terminal pairs, where each terminal pair psi , ti q
1

has a non-negative demand dempiq. A cut in G is a subset of directed edges of EpGq. For a cut
S Ď EpGq in G, let IS be the set of all indices i P t1, 2, . . . , ku such that all paths from si to ti have
ř
CpSq
at least one edge in S. Let DpSq “ iPIS dempiq be the demand separated by S. Let W pSq “ DpSq
be the sparsity of S. The goal is to find the cut with minimum sparsity. The LP relaxation of this
problem corresponds to the dual of the LP formulation of the directed maximum concurrent flow
problem, and the integrality gap of this LP relaxation is the directed multi-commodity flow-cut
?
gap. Hajiyaghayi and Räcke [10] showed an upper bound of Op nq for the flow-cut gap. This
upper bound on the gap has been further improved by Agarwal, Alon and Charikar to Õpn11{23 q
in [1]. For directed graphs of treewidth t, it has been shown that the gap is at most t logOp1q n
by Mémoli, Sidiropoulos and Sridhar [16]. On the lower bound side Saks et al. [17] showed that
for general directed graphs the flow-cut gap is at least k ´ ε, for any constant ε ą 0, and for any
1
k “ Oplog n{ log log nq. Chuzhoy and Khanna showed a Ω̃pn 7 q lower bound for the flow-cut gap in
[8].
A natural generalization of the GNRS Conjecture for directed graphs poses the question of
whether the multi-commodity flow-cut gap is Op1q for any family of minor free directed graphs. In
this paper, we provide the first constant gaps for some non-trivial family of graphs. Throughout
this paper, when we refer to a directed family of graphs we mean that it is obtained from an
undirected family of graphs by assigning arbitrary directions to the edge sets. We state below our
two main results pertaining to the flow-cut gap.
Theorem 1.1. The uniform multi-commodity flow-cut gap on directed series-parallel graphs and
directed bounded pathwidth graphs is Op1q.
Theorem 1.2. The non-uniform multi-commodity flow-cut gap on directed cycles and directed trees
is Op1q.

1.2

Cut problems of directed graphs

Better bounds on the flow-cut gap typically also imply better approximation ratios for solving cut
problems. For the Directed Non-Bipartite Sparsest Cut problem the flow-cut gap upper bounds of
?
[10] and [1] are also accompanied by Op nq and Opñ11{23 q polynomial time approximation algorithms respectively. Similarly for graphs of treewidth t, a t logOp1q n polynomial time approximation
algorithm is also provided in [16].
Another closely related cut problem is the Directed Multicut problem which is defined as
follows. Let G be a directed graph and let c : EpGq Ñ Rě0 be a capacity function. Let
T “ tps1 , t1 q, ps2 , t2 q, . . . , psk , tk quřbe a set of terminal pairs. A cut in G is a subset of EpGq.
The capacity of a cut S is cpSq “ ePS cpeq. The goal is to find a cut separating
all terminal pairs,
?
minimizing the capacity of the cut. This problem is NP-hard. An Op n log nq approximation
algorithm for Directed Multicut was presented by Cheriyan, Karloff and Rabani [6]. Subsequently
an Õpn2{3 {OPT1{3 q-approximation was given due to Kortsarts, Kortsarz and Nutov [12]. Finally
[1] also gives an improved Õpn11{23 q-approximation algorithm for this problem. Again for graphs
of treewidth t a t logOp1q n approximation algorithm was also shown in [16].
On the hardness side [7] demonstrated an Ωp logloglogn n q-hardness for the Directed Non-Bipartite
Sparsest Cut problem and the Directed Multicut problem under the assumption that NP Ę DTIME
1´ε
Op1q
pnlog n q. This was further improved by them in a subsequent work [8] to obtain an 2Ωplog nq hardness result for both problems for any constant ε ą 0 assuming that NP Ď ZPP .
Our main results for these problems are the following theorems.
2

Theorem 1.3. There exists a polynomial time Op1q-approximation algorithm for the Uniform
Directed Sparsest Cut problem on series parallel graphs and graphs of bounded pathwidth.
Theorem 1.4. There exists a polynomial time Op1q-approximation algorithm for the Directed
Multicut problem on series parallel graphs and graphs of bounded pathwidth.
We remark that in the above results the running time in the case of graphs of pathwidth k
is nOp1q . That is, the running time does not depend on k. Typically, algorithms for graphs of
pathwidth k have running time of the form either f pkqnOp1q , or nf pkq , for some function f , due to
the use of dynamic programming. Our algorithms are based on LP relaxations, and thus avoid this
overhead.

1.3

Quasimetric spaces and embeddings

Random quasipartitions. A Quasimetric space is a pair pX, dq where X is a set of points and
d : X ˆ X Ñ R` Y t`8u, that satisfies the following two conditions:
(1) For all x, y P X, dpx, yq “ 0 iff x “ y.
(2) For all x, y, z P X, dpx, yq ď dpx, zq ` dpz, yq.
The notion of random quasipartitions was introduced in [16]. A quasipartition is a transitive
reflexive relation. Let M “ pX, dq be a quasimetric space. For a fixed r ě 0, we say that a
quasipartition Q of M is r-bounded if for every x, y P X with px, yq P Q, we have dpx, yq ď r. Let
D be a distribution over r-bounded quasipartitions of M . We say that D is r-bounded. Let β ą 0.
We say that D is β-Lipschitz if for any x, y P X, we have that
Pr rpx, yq R P s ď β

P „D

dpx, yq
.
r

Given a distribution D over quasipartitions we sometimes use the term random quasipartition
(with distribution D) to refer to any quasipartition P sampled from D. We consider the quasimetric space obtained from the shortest path distance of a directed graph. Mémoli, Sidiropoulos and
Sridhar in [16] find an Op1q-Lipschitz distribution over r-bounded quasipartitions of tree quasimetric spaces. They also prove the existence of a Opt log nq-Lipschitz distribution over r-bounded
quasipartitions for any quasimetric that is obtained from a directed graph of treewidth t.
Our main results for finding Lipschitz quasipartitions are the following theorems.
Theorem 1.5. Let G be a directed graph of treewidth 2. Let M “ pV pGq, dG q denote the shortestpath quasimetric space of G. Then for all r ą 0, there exists some Op1q-Lipschitz distribution over
r-bounded quasipartitions of M .
Theorem 1.6. Let G be a directed graph of of pathwidth k. Let M “ pV pGq, dG q denote the
2
shortest-path quasimetric space of G. Then for all ∆ ą 0, there exists some 2Opk q -Lipschitz
distribution over ∆-bounded quasipartitions of M .

3

Random embeddings. Before stating our embedding results, we first need to introduce some
notations and definitions. Let M “ pX, dq and M 1 “ pX 1 , d1 q be quasimetric spaces. A mapping
f : X Ñ X 1 is called an embedding of distortion c ě 1 if there exists some α ą 0, such that for
all x, y P X, we have dpx, yq ď α ¨ d1 pf pxq, f pyqq ď c ¨ dpx, yq. We say that f is isometric when
c “ 1. Let D be a distribution over pairs pM 1 , f q, where f : X Ñ X 1 . We say that D is a random
embedding of distortion c ě 1 if for all x, y P X, the following conditions are satisfied:
(1) PrpM 1 ,f q„D rd1 pf pxq, f pyqq ě dpx, yqs “ 1.
(2) EpM 1 ,f q„D rd1 pf pxq, f pyqqs ď c ¨ dpx, yq.
Directed `1 (Charikar
et al. ř[4]) The
ř directed `1 distance between two points x and y is
ř
given by d`1 px, yq “ |xi ´ yi | ` |xi | ´ |yi |.
i

i

i

The following theorems are our main results for random embeddings.
Theorem 1.7. Let G be a directed cycle and let M “ pV pGq, dG q be the shortest-path quasimetric space of G. Then M admits a constant-distortion embedding into directed `1 . Moreover the
embedding is computable in polynomial time.
Theorem 1.8. Let G “ pV, Eq be a directed tree, and let X “ pV, dq be the quasimetric induced by
G. Then X embeds into directed `1 .
Limitations. We further discuss some limitations of methods that were developed for undirected
graphs. Klein, Plotkin, and Rao in [11] introduced the notion of random partitions for undirected
graphs. In Section 8, we show that this method can not be used or generalized for the case of
directed graphs. Furthermore, we complete our paper with a lower bound result that is stated in
the following theorem.
Theorem 1.9. There exists a directed cycle G “ pV, Eq such that any non-contracting random
embedding of G into directed trees has distortion Ωpnq.

1.4

Organization

In Sections 3 and 4, we provide efficient algorithms for computing random quasipartitions for
directed graphs of treewidth 2 and bounded pathwidth graphs respectively. In Section 5, we describe
an algorithm for computing an Op1q-distortion embedding of the directed cycles into directed `1 .
In Section 6, we provide an algorithm for embedding directed trees into directed `1 with distortion
one. In Section 7 we discuss the applications to directed cut problems. In Section 8 we discuss the
limitations of random partitions for the directed case, and finally in Section 9 we provide a lower
for non-contracting embeddings of directed cycle into directed trees.

2

Notation and preliminaries

We now introduce some notation that will be used throughout the paper.

4

Directed graphs and treewidth. From any undirected graph GUN we can obtain a directed
graph G as follows. We set V pGq “ V pGUN q and EpGq “ tpu, vq, pv, uq : tu, vu P EpGUN qu; i.e. for
every undirected edge tu, vu in EpGUN q we add directed edges pu, vq and pv, uq to EpGq. We refer
to GUN as the underlying undirected graph of G. We say that G is a directed graph of treewidth k
if its underlying undirected graph has treewidth k, for some k ě 1. Similarly, we say that G is a
directed tree (resp. directed cycle) if its underlying undirected graph is a tree (resp. cycle).
Directed cut metrics and 0-1 quasimetrics (Charikar et al. [4]) Given a set X and a
subset S Ă X, the corresponding directed cut metric distance for any pair of elements u, v P X is
given by,
"
1 if x P S, y R S;
dS px, yq “
0 otherwise ;
A 0-1 Quasimetric space is a pair pX, dq where for all u, v P X we have that dpu, vq “ 0 or
dpu, vq “ 1 and for all u, v, w P X we have that dpu, wq ď dpu, vq ` dpv, wq.

3

Lipschitz quasipartitions of treewidth-2 directed graphs

In this Section we provide a proof for Theorem 1.5. Note that since all series-parallel graphs
have treewidth at most 2 this result automatically holds for any series-parallel graph. We present
an efficient algorithm for computing a random quasipartition of a directed graph of treewidth 2.
We begin by describing some special type of graphs of treewidth 2, which we refer to as trees
of hexagons. We show that any graph of treewidth 2 admits an isometric embedding into some
tree of hexagons. We then further show how to preprocess a tree of hexagons such that it can
be inductively constructed via a sequence of either slack or tight paths similar to [9]. Finally, we
present the algorithm for computing the random quasipartition, and we analyze the correctness of
the algorithm.

3.1

Trees of hexagons

Let G be a directed graph of treewidth 2. We can construct GUN as follows. Start with a single
edge and sequentially perform the following operation. Pick an arbitrary existing edge e “ tu, vu.
Add a new vertex x and edges tx, uu and tx, vu. Let Γ “ pu, x, vq be the added path. We say that e
is the parent of Γ. Finally, remove an arbitrary subset of edges. Now we may assume w.l.o.g. that
no edges are removed in the last step while constructing GUN . Suppose this is not the case then
we can replace the removed edges with edges that have weight equal to the shortest path distance
between the two end points. This will ensure that the induced shortest path quasimetric of G
remains the same. The parent relation induces a rooted tree decomposition pT , X q of GUN of width
2, where each bubble induces a triangle in GUN .
For any path Γ “ pu, x, vq of GUN whose parent edge is e “ tu, vu we say that the directed edge
pu, vq is the parent of the directed path pu, x, vq in G and the directed edge pv, uq is the parent of
the directed path pv, x, uq in G.
We construct a new graph G1 as follows. We start with G and modify it in the following
fashion. For all B P X we consider the sub-graph GrBs and proceed as follows. Let u, v, w be
the vertices of B. We duplicate each vertex of B and add edges of weight 0 in both directions
5

Figure 1: Hexagons

between the two copies of a vertex (See Figure 1). By doing so, every directed triangle in GrBs
corresponds to a directed hexagon in G1 , where u1 , u2 , v 1 , v 2 , w1 , w2 are the vertices of the hexagon.
The edges e1 “ pu, vq, e2 “ pv, wq, e3 “ pw, uq correspond to e11 “ pu2 , v 1 q, e12 “ pv 2 , w1 q, and
e13 “ pw2 , u1 q respectively in G1 with the same weight. Similarly, the edges e4 “ pv, uq, e5 “ pw, vq,
and e6 “ pu, wq correspond to e14 “ pv 1 , u2 q, e15 “ pw1 , v 2 q, and e16 “ pu1 , w2 q respectively in G1 with
the same weight (See Figure 1). Therefore, we get a new graph G1 .
For any triangle tu, w, vu in G where the edge e “ tu, vu is the parent of the path Γ “ tu, w, vu,
let the corresponding hexagon in G1 be tu1 , u2 , w1 , w2 , v 1 , v 2 u. We call the directed edge e1 “ pu2 , v 1 q
the parent edge of the directed path Γ1 “ tu2 , u1 , w2 , w1 , v 2 , v 1 u and of every edge in it. Similarly
we call e2 “ pv 1 , u2 q the parent edge of the directed path Γ2 “ tv 1 , v 2 , w1 , w2 , u1 , u2 u and every edge
in it. This parent relation induces a rooted tree decomposition of G1UN , pT 1 , X 1 q of width 5, where
each bubble B P X 1 induces a hexagon in G1UN . We say that G1 is a tree of hexagons.
Let e1 “ pu1 , v1 q be the parent edge of a path Γ1 . For any edge e0 “ pu0 , v0 q in Γ1 we define
the tail of e0 , tailpu0 , v0 q, to be the subpath of Γ1 from u1 to v0 .
The above discussion immediately implies the following.
Lemma 3.1 (Embedding into a tree of hexagons). There exists a polynomial-time algorithm which
given a directed graph G of treewidth 2, computes an isometric embedding of G into some tree of
hexagons G1 .

3.2

Slack and tight paths

Let G be the input graph, and let w be a non-negative weight function on the edges of G. By
Lemma 3.1 we may assume w.l.o.g. that G is a tree of hexagons, and we have a tree decomposition
of G1UN , pT , X q rooted at some B ˚ P X . For any two vertices x, y P V pGq, we pick a unique shortest
path from x to y denoted by pxy to use in our algorithm. We always pick pxy to be a shortest path
with the fewest number of edges. If there are multiple such paths we pick one maintaining the
condition that the intersection of any two shortest paths is a (possiply empty) path. For a path P ,
let lenpP q denote the length of P . Let e P EpGq. For any child path Γ of e, we say that Γ is slack
if lenpΓq ě 2wpeq, and we say that Γ is tight if lenpΓq “ wpeq.
Let x P B ˚ be an arbitrary vertex. Let l : X Ñ Zě0 be a level function where lpB ˚ q “ 0,
and for any other B P X , lpBq denotes the length of the shortest path from B ˚ to B in T . Let
B1 , B2 , . . . , Bk be the leaf vertices of T . For every i P 1, 2, . . . , k, let li P Bi be an arbitrary vertex
6

Figure 2: Complementary path

in G. For every i P 1, 2, . . . , k, let Pi be the unique shortest paths in T from B ˚ to Bi . Let pi “ pxli
and let qi “ pli x . For every pi , we define the complementary path pˆi as follows. Let Pi be the path
of hexagons corresponding to pi . Let Pi1 be the subgraph of Pi obtained by deleting all the edges of
pi , i.e. Pi1 “ Pi zpi . We set pˆi to be the unique path from x to li in Pi1 (See Figure 2). For every pi ,
we define the flattened complementary graph pi as follows. Start with pi “ pˆi , and for every tight
path Γ with a parent edge e P pi add Γ to pi and repeat until we don’t add any new paths. We can
similarly define the complementary path qˆi and the flattened complementary graph qi for every qi .
Let P be a path in G. We say that P is down-monotone if when traversing P we visit the bubbles
of T in non-decreasing distance from the root of T . Similarly, we say that P is up-monotone if
when traversing P we visit the bubbles of T in non-increasing distance from the root of T .
We say that some tree of hexagons G is canonical if for all e P EpGq, every child of e is either
tight or slack. We first show that any directed graph of treewidth 2 admits a constant-distortion
embedding into a canonical directed tree of hexagons. This allows us to focus on canonical graphs.
Lemma 3.2 (Embedding into a canonical graph). Given a directed tree of hexagons G, we can
compute in polynomial time some embedding of G into some canonical tree of hexagons G1 , with
distortion at most 2.
Proof. The algorithm proceeds by inductively modifying the graph G. We intially mark all edges
as unresolved. We mark all edges with no parent as resolved. While there are unresolved edges,
we pick some unresolved edge e, whose parent e1 is resolved, and let Γ be the child path of e1 that
contains e. If Γ is neither slack nor tight then for all e P EpΓq, we set wpeq “ wpeq ¨ wpe1 q{lenpΓq.
We all mark edges in Γ as resolved. We set G1 be the graph obtained at the end of this inductive
process. It is immediate the G1 is canonical. At each iteration the number of unresolved edges
decreases by at least one, so the algorithm terminates in polynomial time. By the definition of
tight and slack paths, it follows that the length of each edge changes by at most a factor of 2. Thus
the distortion of the induced embedding is at most 2, which concludes proof.

3.3

Computing a random quasipartition

The algorithm for computing a random quasipartition is as follows. The input consists of some
directed tree of hexagons G, a non-negative weight function w on the edges of G, and some r ą 0.
The output is a random r-bounded quasipartition of the shortest-path quasimetric space of G.

7

Input: A directed canonical tree of hexagons G, and a tree decomposition of GUN , pT , X q rooted
at some B ˚ P X . and r ą 0.
Output: Random quasipartition of the shortest-path quasimetric space of G, pM, dG q.
Initialization. Set G˚ “ G and Q “ EpGq.
Step 1. Let x P B ˚ be an arbitrary vertex. Pick z P r0, rs uniformly at random.
Step 2. For all pu, vq P EpG˚ q remove pu, vq from Q if dG px, vq ą i ¨ r ` z and dG px, uq ď i ¨ r ` z
for some integer i ě 0.
Step 3. For all pu, vq P EpG˚ q remove pu, vq from Q if dpj px, vq ą i ¨ r ` z and dpj px, uq ď i ¨ r ` z
for some integer i ě 0 and some integer j P t0, . . . , ku.
Step 4. For all pu, vq P EpG˚ q that are removed from Q in Step 3 do the following:
Step 4.1. For each uncut child path Γ “ pu, w, q, o, p, vq of pu, vq remove one of the edges
pu, wq, pw, qq, pq, oq, po, pq or pp, vq from Q, chosen randomly with probability dpu,wq
lenpΓq ,
dpw,qq dpq,oq dpo,pq
lenpΓq , lenpΓq , lenpΓq

and

dpp,vq
lenpΓq

respectively.

Step 4.2. Recursively perform Step 4.1 on the removed edge.
Step 5. For all pu, vq P EpG˚ q remove pu, vq from Q if dpv, xq ď i ¨ r ` z and dpu, xq ą i ¨ r ` z for
some integer i ě 0.
Step 6. For all pu, vq P EpG˚ q remove pu, vq from Q if dqj pv, xq ď i ¨ r ` z and dqj pu, xq ą i ¨ r ` z
for some integer i ě 0 and some j P t0, . . . , ku.
Step 7. For all pu, vq P EpG˚ q that are removed from Q in step 6 do the following:
Step 7.1. For each uncut child path Γ “ pu, w, q, o, p, vq of pu, vq remove one of the edges
pu, wq, pw, qq, pq, oq, po, pq or pp, vq from Q, chosen randomly with probability dpu,wq
lenpΓq ,
dpw,qq dpq,oq dpo,pq
lenpΓq , lenpΓq , lenpΓq

and

dpp,vq
lenpΓq

respectively.

Step 7.2. Recursively perform Step 7.1 on the removed edge.
Step 8. For any pu, vq P Q, if dpu, vq ą

r
10 ,

remove pu, vq from Q.

Step 9. Enforce transitivity on Q; that is, for all u, v, w P V pGq if pu, vq P Q and pv, wq P Q then
add pu, wq to Q.
This concludes the description of the algorithm for computing a random quasipartition.
Analysis. We now analyze the performance of the above algorithm. We begin by showing that
the probability that an edge is removed from the quasipartition is small. This statement is shown
by considering separately all possible steps of the algorithm where an edge can be removed.
Lemma 3.3. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 2s ď

8

dpu,vq
r .

Proof. The edge pu, vq is removed from Q in Step 2 when dpx, uq ď z`ir and dpx, vq ą z`ir for some
integer i ě 0. By the triangle inequality this implies that P rrpu, vq is removed from Q in Step 2s ď
dpx,vq´dpx,uq
ď dpu,vq
r
r , as required.
Lemma 3.4. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in step 5s ď

dpu,vq
r .

Proof. The proof of this case is similar to the proof of Lemma 3.3.
Lemma 3.5. Let pu, vq P EpGq. Suppose that pu, vq P pˆi and pu, vq P pˆj for some i, j P t0, . . . , ku,
then dpi px, uq “ dpj px, uq and dpi px, vq “ dpj px, vq.
Proof. Let τ be the hexagon containing u and v. Let py, oq be the parent edge of pu, vq. Note
that it is possible that y “ u or o “ u. Since any complement subpath from x to pu, vq must end
with the unique subpath tailpu, vq, it follows that tailpu, vq P pˆi and tailpu, vq P pˆj . The fact that
the complement contains y also means that pxo is contained in pi and pj . Therefore we have that
pˆi and pˆj share the same sub-path from x to y. Combined with the fact that tailpu, vq P pˆi and
tailpu, vq P pˆj this implies that pˆi and pˆj share the same sub-path from x to v ending with the edge
pu, vq.
Since pˆi and pˆj share the same sub-path from x to v ending with the edge pu, vq we have that
dpi px, uq “ dpj px, uq and dpi px, vq “ dpj px, vq.
Lemma 3.6. Let i P t0, . . . , ku. Suppose that pi traverses the parent edge pu, vq of a tight path Γ.
Then pi does not visit any vertex in Γ other than u and v.
Proof. Let Γ “ pu, o, w, f, y, vq. Since pu, vq is the parent edge of a tight path pu, o, w, f, y, vq we
have that puy “ pu, o, w, f, yq. Suppose pi visits some vertex in Γ other than u and v we have that
pi intersects the shortest path puy more than once which is a contradiction.
Lemma 3.7. Let pu, vq P EpGq. Suppose that pu, vq P pi , pu, vq R pˆi and pu, vq P pˆj for some
i, j P t0, . . . , ku, then dpi px, uq “ dpj px, uq and dpi px, vq “ dpj px, vq.
Proof. Let pt, zq P pˆi be the unique ancestor edge of pu, vq that is contained in pˆi . We have that
pt, zq is the ancestor edge of a tight path that contains pu, vq. This implies that ptv P pi . Now let
pb, cq be the parent edge of pt, zq. This implies that pxc Ă pi .
Let us suppose that the parent edge of pu, vq is py, oq. This implies that pj contains o. Since
py, oq is the parent edge of a tight path we also have that pyv “ tailpu, vq. This implies that
ptv “ pty Y tailpu, vq. From Lemma 3.6 we have that pj does not contain py, oq. Recursively
applying Lemma 3.6 we have that pj does not intersect with ptailpt, zqzpt, zqq Y ptv . Therefore we
have that pxc Ă pj and that ptailpt, zqzpt, zqq Y ptv Ă pˆj . Since pxc is common to both pi and pj ,
we have that pi and pj share the same subpath from x to b. Moreover they both also contain
ptailpt, zqzpt, zqq Y ptv which concludes the proof.
Lemma 3.8. Let pu, vq P EpGq. Suppose that pu, vq P pi and pu, vq P pj for some i, j P t0, . . . , ku,
then dpi px, uq “ dpj px, uq and dpi px, vq “ dpj px, vq.
Proof. Let pt, zq P pˆi be the unique ancestor edge of pu, vq that is contained in pˆi . Let pb, cq P pˆj be
the unique ancestor edge of pu, vq that is contained in pˆj . W.l.o.g. let pt, zq be the ancestor edge of
a tight path that contains pb, cq. From Lemma 3.7 we have that dpi px, bq “ dpj px, bq. Since pb, cq
is an ancestor edge of a tight path that contains pu, vq it follows that pi and pj both contain pbv .
This implies that dpi px, uq “ dpj px, uq and dpi px, vq “ dpj px, vq concluding the proof.
9

Lemma 3.9. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 3s ď

dpu,vq
r .

Proof. From Lemmas 3.5, 3.7 and 3.8 we have that pu, vq is only removed when, for some integer
i ě 0, and any j P t0, . . . , ku such that pu, vq is in pj , we have that dpj px, uq ď z ` ir and dpj px, vq ą
z ` ir . By the triangle inequality, this implies that P rrpu, vq is removed from Q in Step 3s ď
dpx,vq´dpx,uq
ď dpu,vq
r
r , as required.
Lemma 3.10. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 6s ď

dpu,vq
r .

Proof. The proof of this case is similar to the proof of Lemma 3.9.
Lemma 3.11. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 4s ď 2 dpu,vq
r .
Proof. We prove this by induction. For the base case suppose that pu, vq is an edge in B ˚
then it has no parent edge and therefore the assertion is immediate. Otherwise let e be the
parent edge of a child path Γ containing pu, vq and assume, by the inductive hypothesis, that
P rrpeq is removed from Q in Step 4s ď 2 dpeq
r . There are two cases:
Case 1: Suppose that Γ is a tight child path of e. Then we have
P rrpu, vq is removed from Q in Step 4s “ P rrpeq is removed from Q in Step 4s ¨
ď2

dpu, vq
dpeq

dpu, vq
r

Case 2: Suppose that Γ is a slack child path of e. Then we have
dpu, vq
lenG pΓq
dpu, vq
` P rrpeq is removed from Q in Step 3s ¨
lenG pΓq
dpeq dpu, vq dpeq dpu, vq
¨
`
¨
ď2
r
2dpeq
r
2dpeq
dpu, vq
ď2
r

P rrpu, vq is removed from Q in Step 4s “ P rrpeq is removed from Q in Step 4s ¨

Thus in either case the assertion is satisfied, concluding the proof.
Lemma 3.12. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 7s ď Op1q dpu,vq
r .
Proof. The proof for this is similar to the proof of Lemma 3.11.
Lemma 3.13. For all pu, vq P EpGq, we have P rrpu, vq is removed from Q in Step 8s ď 10 dpu,vq
r .
Proof. Since only edges of length greater than

r
10

are removed in Step 8 we have that

P rrpu, vq is removed from Q in step 8s ď 1 ă 10

10

dpu, vq
.
r

Lemma 3.14. For all pu, vq P EpGq, we have P rrpu, vq is removed from Qs ď 18 dpu,vq
r .
Proof. The assertion follows by combining Lemmas 3.3, 3.9, 3.11, 3.4, 3.10, 3.12 and 3.13 using the
union bound.
Finally we show that Q is 6r-bounded.
Lemma 3.15. Let e “ pu, vq P Q where u P Bu and v P Bv . Suppose that Bu is in the path from
B ˚ to Bv in T . If pu, vq P Q then there exists a monotone-down path P “ ta1 “ u, a2 , . . . , at “ vu
in G, where for all i P t1, 2, . . . , t ´ 1u we have pai , ai`1 q P Q.
Proof. Since pu, vq P Q, we have that at the beginning of step 9 there must have been a path
P0 “ ta1 “ u, a2 , . . . , at “ vu such that for all i P t1, 2, . . . , t ´ 1u we have pai , ai`1 q P Q. If P0
is monotone-down, we are done. Otherwise, we start with P0 and modify it to obtain the desired
P . Suppose that P0 is not monotone-down. Let X “ pBu , ..., Bv q be the shortest path from Bu to
Bv in T . Let A “ YaPBi ,Bi PV pXq a. Since P0 is not monotone-down, there exists ai P V pP0 q such
that ai R A. Let m P t1, 2, . . . , tu be the smallest number such that am has such property. Let
1
Cm,0
be the hexagon containing am´1 and am´2 (See Figure 3). Let as be the other neighbor of
1 , and let e “ pa
1
1
am´1 in Cm,0
0
m´1 , as q. Let Cm,1 be the next hexagon traversed by P0 after Cm,0 ,
1
1
and let e1 P Cm,1
be the other edge in Cm,1
which is not traversed by P0 . We similarly define
1
1
Cm,2 , . . . , Cm,l , and e2 , . . . , el´1 .
The main idea is that we are able to replace the subpath of P0 from am´1 to as with e0 .
Suppose that we are not able to do such replacement, and thus e0 is removed in the algorithm. Let
Γ “ pam´1 , am , am`1 , as´1 , as q. Γ is a child of e0 . First suppose that Γ is tight. In this case, since
e0 is removed, at least one of the edges of Γ should be removed after step 3, and thus e1 should
be removed by the algorithm. Second case is where Γ is a slack. In this case, since e0 is removed,
at least one of the edges of Γ should be removed after step 4, and again we have that e1 should
be removed by the algorithm. Using the same argument inductively, we get that el´1 should be
1
are removed,
removed by the algorithm. But note that none of the edges of the child of el´1 in Cm,l
which is a contradiction. Therefore, e0 is not removed by the algorithm and we can replace the
subpath of P0 from am´1 to as with e0 . Using the same argument, we can modify P0 such that it
only traverses vertices in A, as desired.
Lemma 3.16. Let e “ pu, vq P Q where u P Bu and v P Bv . Suppose that Bv is in the path from
B ˚ to Bu in T . If pu, vq P Q then there exists a monotone-up path P “ ta1 “ u, a2 , . . . , at “ vu in
G, where for all i P t1, 2, . . . , t ´ 1u we have pai , ai`1 q P Q.
Proof. A similar argument as in Lemma 3.15 applies here.
Lemma 3.17. Let e “ pu, vq P Q where u P Bu and v P Bv . Suppose that Bu is in the path from
B ˚ to Bv in T . If pu, vq P Q then we have dpu, vq ď 3r.
Proof. Let P “ ta1 “ u, a2 , . . . , at “ vu be the monotone-down path obtained by Lemma 3.15.
Suppose that the path from B ˚ to Bv in T , is a subpath of Pj for some j P t1, 2, . . . , ku, and let
pj be the corresponding path in G. Let f “ minai PP Xpj i, and let l “ maxai PP Xpj i. Let P 1 “
ta1 , a2 , . . . , af u, P 2 “ taf , af `1 , . . . , al u, and P 3 “ tal , al`1 , . . . , at u. For any i P t1, 2, . . . , f ´ 1u
we have that pai , ai`1 q is not removed after step 4. This implies that dpa1 , af q ď r. With a similar
argument, we can show that dpal , at q ď r. Finally, for any i P tf, f ` 1, . . . , l ´ 1u we have that
11

Figure 3: The path in Lemma 3.15.

pai , ai`1 q is not removed after step 2, and thus we have dpaf , al q ď r. Therefore by applying triangle
inequality, we get dpa1 , at q ď 3r, as required.
Lemma 3.18. Let e “ pu, vq P Q where u P Bu and v P Bv . Suppose that Bv is in the path from
B ˚ to Bu in T . If pu, vq P Q then we have dpu, vq ď 3r.
Proof. A similar argument as in Lemma 3.17 applies here.
Lemma 3.19. If e “ pu, vq P Q then we have dpu, vq ď 6r.
Proof. Since pu, vq P Q, we have that at the beginning of step 8 there must have been a path
P “ ta1 “ u, a2 , . . . , at “ vu such that for all i P t1, 2, . . . , t ´ 1u we have pai , ai`1 q P Q. Suppose
that u P Bu and v P Bv for some Bu , Bv P X . Let Bw P X be a vertex with minimum level
that has non-empty intersection with V pP q. Let w P Bw X V pP q be an arbitrary vertex. By the
construction, we have that Bw is in the paths from B ˚ to Bv and Bu . Moreover, we have pu, wq P Q
and pw, vq P Q. Therefore, by Lemmas 3.17 and 3.18, we have that dpu, wq ď 3r and dpw, vq ď 3r.
This implies that dpu, vq ď 6r, as desired.
Proof of Theorem 1.5. The proof follows by combining Lemmas 3.19 and 3.14.

4

Lipschitz quasipartitions for bounded pathwidth digraphs

In this Section we provide a proof for Theorem 1.6. We present an efficient algorithm for computing
a random quasipartition of a directed graph with bounded pathwidth. We begin by describing a
specific family of graphs of bounded pathwidth, which we refer to as path of cliques. We show
that any graph of pathwidth k admits an isometric embedding into a path of k-cliques. We then
describe an algorithm to obtain a random quasipartition of a path of k-cliques. Finally, we present
the analysis of the aforementioned algorithm.

12

4.1

Isometric embedding for bounded pathwidth digraphs into path of cliques

Path of cliques We call a digraph G a path of k-cliques if there exists a collection of pairwise
disjoint subsets of V pGq S1 , S2 , . . . Sl such that the following conditions hold:
1) S1 Y S2 Y . . . Y Sl “ V pGq.
2) |Si | “ k for any integer i P t1, . . . , lu.
3) EpGq “ tpu, vq, pv, uq|u, v P Si Y Si`1 , i P t1, . . . , l ´ 1uu.
We refer to the subsets S1 , S2 , . . . Sl as cliques. We call an edge pu, vq P EpGq a vertical edge
if u, v P Si for some i P t1, . . . , lu. We call all other edges in EpGq horizontal edges. Furthermore
if u P Si and v in Si`1 for some i P t1, . . . , lu we call the horizontal edge pu, vq left horizontal.
Otherwise if v P Si and u P Si`1 we call the horizontal edge pu, vq right horizontal. Let p be a
directed path in G from u to v where u, v P V pGq. We define dG ppq “ dG pu, vq. Let x, y P V pGq
be vertices that are traversed by p in that order. Then we denote the sub-path of p from x to y by
ppx, yq. We define the width of p to be max |p X Si |.
iPt1,...,lu

Theorem 4.1. Let G be a weighted digraph of pathwidth k. Then G embeds isometrically into a
path of pk ` 1q-cliques.
Proof. Let pX, P q denote a path decomposition of G with pathwidth k where X “ tX1 , . . . Xl u is a
collection of subsets of V pGq. First we observe that from the definition of pathwidth we have that
|Xi | ď k ` 1 for all i P t1, . . . , lu. W.l.o.g we may assume that |Xi | “ k ` 1 for all i since otherwise
we can add vertices to Xi from either Xi`1 or Xi´1 and we know that there exists some Xj such
that |Xj | “ k ` 1. Now we construct a path of cliques H as follows. We initialize V pHq and EpHq
to be H. For all i and for each vertex u P V pGq in Xi we add to V pHq a unique vertex ui . We call u
the parent of ui in G and denote this by u “ ppui q. Next we define the sets Si “ ui |u P Xi . Clearly
S1 Y S2 Y . . . Y Sl “ V pHq. Next for all i and for all x, y P Xi Y Xi`1 we add the directed edges
px, yq and py, xq to EpHq setting their weights to be dG pppxq, ppyqq and dG pppyq, ppxqq respectively.
Now we are ready to define the isometric mapping φ : V pGq Ñ V pHq. For each u P V pGq we pick
arbitrarily some v P V pHq such that ppvq “ u and set φpuq “ v. This gives us the desired mapping.
Now we observe that every edge in H has weight equal to the shortest path distance between the
corresponding parent vertices in G. This implies that distances don’t contract in the embedding.
Consider any directed path q “ ta1 , . . . , am u in G. For any u, v P V pHq such that ppuq “ ppvq we
have that there exist directed paths of length 0 from u to v and from v to u. This follows due to the
fact that H is constructed from a path decomposition of G. For the same reason it must also be that
for every directed edge pai , ai`1 q in q there exist u, v P V pHq such that ppuq “ ai and ppvq “ ai`1
and u, v both belong to Xj for some j. This implies that there is a corresponding directed edge
pu, vq P EpHq. Therefore there is a corresponding directed path in H with the same length as q.
So it follows that φ does not dilate distances. Therefore φ is an isometric embedding.

4.2

Algorithm

Input: A graph G of pathwidth k ´ 1 and a corresponding path of cliques B1 , B2 , ¨ ¨ ¨ , Bl , where
for each i P t1, 2, ¨ ¨ ¨ , lu we have |Bi | “ k.
Output: Random quasipartition Q of the shortest-path quasimetric space of G.
13

Initialization. Set G˚ “ G, Q “ EpGq, and i “ 1.
Step 1. Pick z P r0, rs uniformly at random.
Step 2. Pick v1,i P B1 such that Bl is reachable from v1,i in G˚ (There exists a directed path
from v1,i to Bl in G˚ ). Let si “ v1,i , and let ti P Bl be such that ti is reachable from si . Let
pi be a shortest path from si to ti in G˚ .
Step 3. For all pu, vq P EpG˚ q remove pu, vq from Q if dG˚ psi , vq ą j ¨r `z and dG˚ psi , uq ď j ¨r `z
for some integer j ě 0.
Step 4. For any pu, vq P pi , if pu, vq is horizontal in G then delete pu, vq from G˚ , and set i “ i ` 1.
If i ď k 2 , go back to Step 2.
Step 5. Set G˚ “ G, and i “ 1.
Step 6. Pick vl,i P Bl such that B1 is reachable from vl,i in G˚ (There exists a directed path from
vl,i to B1 in G˚ ). Let s1i “ vl,i , and let t1i P B1 be such that t1i is reachable from s1i . Let qi be
a shortest path from s1i to t1i in G˚ .
Step 7. For all pu, vq P EpG˚ q remove pu, vq from Q if dG˚ ps1i , vq ą j ¨r `z and dG˚ ps1i , uq ď j ¨r `z
for some integer j ě 0.
Step 8. For any pu, vq P qj , if pu, vq is horizontal in G then delete pu, vq from G˚ , and set i “ i ` 1.
If i ď k 2 , go back to Step 6.
Step 9. Remove every pu, vq P EpGq from Q with dpu, vq ě r.
Step 10. Let G1 be the subgraph of G with V pG1 q “ V pGq and EpG1 q “ Q.
Step 11. Enforce transitivity on Q; that is, for all u, v, w P V pGq if pu, vq P Q and pv, wq P Q
then add pu, wq to Q.

4.3

Analysis of the algorithm

We call an edge in G1 horizontal (resp. vertical ) if the corresponding edge in G is horizontal (resp.
vertical ). For all c P t1, . . . , ku,i P t1, . . . , k 2 u and j P t1, . . . , k 2 u we define Pc,i,j to be the set of all
directed paths in G1 with width c that do not traverse any horizontal edge in px and in qy for all
x ă i and y ă j and traverse at least one horizontal edge in pi and qj .
Lemma 4.2. Let pu, vq P Q after Step 11 of the algorithm. Then there exists a directed path from
u to v in G1 .
Proof. We have that pu, vq P Q after Step 11 of the algorithm. Combined with the fact that
step 11 enforces transitivity on Q this implies that there are two possibilities. The first case is that
pu, vq P EpGq and pu, vq is not removed from Q by the algorithm in steps 3 or 7. The other possibility
is that it must have been that there was a sequence of vertices a1 “ u, a2 , . . . , am “ v such that
for all i ă m pai , ai`1 q P EpGq and pai , ai`1 q P Q after step 9 of the algorithm. This implies that
the corresponding directed edges are present in G1 . Therefore the directed path P “ ta1 , . . . , am u
is also present in G1 .

14

Lemma 4.3. Let e P EpGq be a horizontal edge. Then there exists j P t1, 2, . . . , k 2 u such that
either e P pj or e P qj .
Proof. Let e “ pu, vq and w.l.o.g let u P Bi and v P Bi`1 for some i P t1, 2, . . . , lu. Since we delete
horizontal edges in step 4 and each pj begins at a vertex in B1 and ends at a vertex in Bl it follows
that each pj contains a unique horizontal edge from Bi to Bi`1 . Combined with the fact that
that there are exactly k 2 directed edges from Bi to Bi`1 for any i this implies that for all i every
horizontal edge from from Bi to Bi`1 is contained in some pj . A similar argument can be used
to show that for all i every horizontal edge from from Bi to Bi´1 is contained in some qj . This
concludes the proof.
Lemma 4.4. For every pu, vq P EpGq, we have P rrpu, vq is removed from Q by step 3s ď k 2 dpu,vq
r .
Proof. By the construction, an edge pu, vq is removed from Q by step 3 if dG˚ psj , vq ą i ¨ r ` z
and dG˚ psj , uq ď i ¨ r ` z for some integer i ě 0. This means that each time after running this
step we have that pu, vq is removed from Q with probabilty at most dpu,vq
r . The algorithm runs
2
this step exactly k times, and thus we have P rrpu, vq is removed from Q by step 3s ď k 2 dpu,vq
r , as
desired.
Lemma 4.5. For every pu, vq P EpGq, we have P rrpu, vq is removed from Q by step 7s ď k 2 dpu,vq
r .
Proof. A similar argument as in Lemma 3.9 applies here.
Lemma 4.6. For every pu, vq P EpGq, we have P rrpu, vq is removed from Q by step 9s ď

dpu,vq
r .

Proof. If dpu, vq ă r, then pu, vq is not removed by step 9. Otherwise, pu, vq is removed from Q
and we have P rrpu, vq is removed from Q by step 9s “ 1 ď dpu,vq
r .
Lemma 4.7. For every pu, vq P EpGq, we have P rrpu, vq is removed from Qs ď p2k 2 ` 1q dpu,vq
r .
Proof. This follows immediately by Lemmas 4.4, 4.5, and 4.6.
Now we show that Q is 2k

Op1q

r-bounded.

Lemma 4.8. Let u, v P V pGq and p P Pc,k2 `1,k2 `1 be a directed path in G1 from u to v. Then
dG pu, vq ď pc ´ 1qr.
Proof. We have that p does not traverse any horizontal edges in G1 that are in p1 , . . . , pk2 or
q1 , . . . , qk2 . But since all horizontal edges in G1 are either part of p1 , . . . , pk2 or part of q1 , . . . , qk2
this implies that p consists only of vertical edges of which there can be at most c ´ 1 since each
clique consists of at most k vertices of which p can visit at most c since p has width c. Since each
edge in G1 has length at most r from step 9 of the algorithm it follows that dG ppq ď pc ´ 1qr.
Lemma 4.9. Let u, v P V pGq and i P t1, . . . , k 2 u such that u and v are traversed by pi in that
order. Suppose there exists a path p from u to v that does not traverse any horizontal edge of pj
for all j ă i then dG pu, vq ď r.
Proof. The above lemma can be proved by considering the ith iteration of step 3 of the algorithm.
Since p does not traverse any horizontal edge of pj for all j ă i it follows that p is a path in G˚ .
However since no edge of p is removed in step 3 this implies that dG˚ psi , vq ´ dG˚ psi , uq ď r. This
combined with the fact that pi is a shortest path in G˚ implies that dG pu, vq ď r.
15

Figure 4: The path p in Lemma 4.10.

Lemma 4.10. Let u, v P V pGq and p P Pc,i,j be a directed path in G1 from u to v. Then dG pu, vq ď
2
cOp2k ´i´jq r.
Proof. We prove this by induction. Lemma 4.8 will be used as the base case. Suppose the statement
is true for directed paths in Pd,i,j ,Pc,z,j and Pc,i,o where d ă c, z ą i, and o ą j. We denote by vleft
and vright a pair of leftmost and rightmost vertices traversed by p. More precisely we pick a vertex
vleft from Ba where a is the smallest integer such that Ba X p ‰ H. Similarly we pick a vertex vright
from Bb where b is the largest integer such that Bb X p ‰ H. Suppose p traverses Ba before Bb ,
then we pick vleft to be the first vertex in Ba visited by p and we pick vright to be the last vertex in
Bb visited by p. Otherwise we pick vleft to be the last vertex in Ba visited by p and we pick vright
to be the first vertex in Bb visited by p. Note that if c “ 1, then either vleft “ u and vright “ v or
vleft “ v and vright “ u. Consider the case that p traverses vleft before vright (See figure 4). Then
we have that p “ ppu, vleft q Y ppvleft , vright q Y ppvright , vq. Next we observe that since the width of p
is c and the width of ppvleft , vright q is at least 1 it follows that ppu, vleft q and ppvright , vq have width
at most c ´ 1. Consider ppvleft , vright q. Let u1 be the first vertex in ppvleft , vright q that intersects pi .
Let v1 be the last vertex in ppvleft , vright q that intersects pi beyond u1 . Suppose ppv1 , vright q does
not traverse any horizontal edges of pi then we have that ppvleft , u1 q and ppv1 , vright q are in Pd,z,o
for some integers d ď c,z ą i and o ě j. We also have that ppu, vleft q, ppvright , vq P Pd,z,o for some
integers d ă c,z ě i and o ě j since ppvleft , vright q has width at least 1. So we can use the distance
bounds from the induction on ppvleft , u1 q, ppv1 , vright q, ppu, vleft q, and ppvright , vq. For ppu1 , v1 q we
may bound the distance using lemma 4.9. This gives us the required bound. Suppose ppv1 , vright q
traverses some horizontal edge of pi then let u2 be the first vertex in ppvleft , vright q traversed after
v1 that intersects pi . By the choice of v1 it must be that u2 is a vertex traversed before u1 by pi .
Let u1 belong to a clique Bt for some t P t1, . . . , lu. Now we have that p traverses some vertex
x1 P Bt after visiting v1 and before visiting u2 since u2 is in a clique with a lower index than u1 . Let
y1 P Bt be the last vertex in Bt traversed by p. Now it follows that ppx1 , y1 q has width at most c´1.
This is because ppx1 , y1 q does not intersect ppvleft q, u1 q and does not intersect ppy1 , vright q except
at y1 . From our choice of v1 it must be that ppy1 , vright q does not intersect any horizontal edge of
pi . Similarly ppv1 , x1 q does not intersect any horizontal edge of pi from our choice of u2 and x1 .
Thus again we can bound the distances of ppvleft , u1 q, ppv1 , x1 q, ppx1 , y1 q, ppy1 , vright q, ppu, vleft q, and
ppvright , vq using induction and bound the distance of ppu1 , v1 q using lemma 4.9 giving the required
bound on the distance. For the case that p traverses vright before vleft we use a similar argument
where we consider qj instead of pi .

16

Figure 5: The sub-path of p in Lemma 4.10.

∆
Proof of Theorem 1.6. The required quasipartition is obtained from Algorithm 4.2 setting r “ αk
2 2
where α is the constant in the asymptotic notation from Lemma 4.10. The proof follows from
Lemmas 4.10 and 4.7.

4.4

Derandomization

It is possible to derandomize the algorithm in subsection 4.2 to get a polynomial time algorithm
that enumerates the support of the distribution in Theorem 1.6. The approach is quite similar to
that used in Section 3 Theorem 14 of [16]. We observe that there can be at most n ´ 1 unique
combinations of ordered pair removals in each iteration of Step 3 of the algorithm. In order to
enumerate these we only need to consider values of z for which there exists u P V pG˚ q such that
dG˚ psi , uq “ j ¨ r ` z. Using a similar argument for each iteration of Step 3 we only need to consider
at most pn ´ 1qk 2 unique values of z in total to enumerate the support of the distribution obtained
in the algorithm.
Theorem 4.11. Let G be a directed graph of of pathwidth k. Let M “ pV pGq, dG q denote the
shortest-path quasimetric space of G. Then for all ∆ ą 0, there exists a polynomial time algo2
rithm with running time of the form nOp1q that can compute the support of some 2Opk q -Lipschitz
distribution over ∆-bounded quasipartitions of M .

5

Embedding directed cycles into directed `1

In this section we describe an algorithm for computing a constant-distortion embedding of the
shortest-path quasimetric space of directed cycles into a convex combination of 0-1 quasimetric
spaces.
We begin by introducing some notation. Consider a directed cycle G and fix a planar drawing
of G where G is drawn as a circle centered at the origin. Let w be a weight function on the edges
of G. Let X “ pV, dq be the shortest-path quasimetric space of G. We may assume w.l.o.g. that
every edge pu, vq P E is the shortest path from u to v in G. We denote by ∆ the diameter of G.
Ý
For all u, v P V we denote by Ð
p pu, vq the path from u to v in the counter-clockwise direction in the
Ð
Ý
Ý
Ý
drawing of G and by d pu, vq the length of Ð
p pu, vq. Similarly we denote by Ñ
p pu, vq the path from
Ñ
Ý
Ý
u to v in the clockwise direction in the drawing of G and by d pu, vq the length of Ñ
p pu, vq. We say
Ð
Ý
Ñ
Ý
that some v P V pGq is the meet-point of u if d pu, vq “ d pu, vq. For some pu, vq P V pGq ˆ V pGq,
Ð
Ý
Ñ
Ý
∆
∆
we say that pu, vq is short if d pu, vq ă 10
and d pu, vq ă 10
; otherwise we that pu, vq is long. Let
17

Ñ
Ý
Ð
Ý
∆
and d pu, vq ă
A Ď V where A “ tu : u P V, Dv P V such that d pu, vq ă 10
Ð
Ý
Ñ
Ý
∆
∆
B Ď V where B “ tv : v P V, Du P V such that d pu, vq ă 10
and d pu, vq ă 10
u.

∆
10 u.

Similarly let

Figure 6: The sets A and B.

Ý
Ý
Lemma 5.1. Let u1 , u2 , u3 P V pGq with Ñ
p pu1 , u2 q X Ñ
p pu2 , u3 q “ u2 . Let pu1 , v1 q, pu2 , v2 q, pu3 , v3 q
1
1
be short pairs. Let A “ tu1 , u2 , u3 u and B “ tv1 , v2 , v3 u. Then we have that all the vertices in B 1
Ý
Ý
Ý
are contained within one of Ñ
p pu1 , u2 q, Ñ
p pu2 , u3 q, Ñ
p pu3 , u1 q .
Proof. Suppose for the sake of contradiction that the assertion does not hold. W.l.o.g. assume that
Ñ
Ý
Ý
p pu1 , u2 q and Ñ
p pu2 , u3 q each intersect B 1 . We consider the following cases:
Ð
Ý
Ý
Ý
Case 1: Ñ
p pu1 , u2 q contains v1 and Ñ
p pu2 , u3 q contains v2 . In this case we have that d pu1 , v1 q ă
Ð
Ý
∆
∆
Ð
Ý
Ð
Ý
10 and d pu2 , v2 q ă 10 . But p pu1 , v1 q Y p pu2 , v2 q contains all the edges of G in the counterclockwise direction. This implies that the sum of the lengths of all the edges in the counter2∆
clockwise direction is at most 2∆
10 . However this means that the diameter of G is at most 10 which
is a contradiction.
Ñ
Ý
Ý
Ý
Case 2: Ñ
p pu1 , u2 q contains v2 and Ñ
p pu2 , u3 q contains v1 . In this case we have that d pu1 , v1 q ă
Ñ
Ý
∆
∆
Ñ
Ý
Ñ
Ý
10 and d pu2 , v2 q ă 10 . But p pu1 , v1 q Y p pu2 , v2 q contains all the edges of G in the clockwise
direction. This implies that the sum of the lengths of all the edges in the clockwise direction is at
2∆
most 2∆
10 . However this means that the diameter of G is at most 10 which is a contradiction.
Ñ
Ý
Ñ
Ý
Ñ
Ý
Case 3: p pu1 , u2 q contains v3 , p pu2 , u3 q contains v1 and p pu3 , u1 q contains v2 . In this case we
Ý
Ñ
Ý
Ñ
Ý
∆ Ñ
∆
∆
Ý
Ý
Ý
, d pu2 , v2 q ă 10
and d pu3 , v3 q ă 10
. But Ñ
p pu1 , v1 qYÑ
p pu2 , v2 qYÑ
p pu3 , v3 q
have that d pu1 , v1 q ă 10
contains all the edges of G in the clockwise direction. This implies that the sum of the lengths of
all the edges in the clockwise direction is at most 3∆
10 . However this means that the diameter of G
is at most 3∆
which
is
a
contradiction.
10
Ñ
Ý
Ý
Ý
Case 4: Ñ
p pu1 , u2 q contains v2 and Ñ
p pu3 , u1 q contains v1 . In this case we have that d pu1 , v1 q ă
Ñ
Ý
∆
∆
Ñ
Ý
Ñ
Ý
10 and d pu2 , v2 q ă 10 . But p pu1 , v1 q Y p pu2 , v2 q contains all the edges of G in the clockwise
direction. This implies that the sum of the lengths of all the edges in the clockwise direction is at
2∆
most 2∆
10 . However this means that the diameter of G is at most 10 which is a contradiction.
Ð
Ý
Ý
Ý
Case 5: Ñ
p pu1 , u2 q contains v1 and Ñ
p pu3 , u1 q contains v2 . In this case we have that d pu1 , v1 q ă
Ð
Ý
∆
∆
Ð
Ý
Ð
Ý
10 and d pu2 , v2 q ă 10 . But p pu1 , v1 q Y p pu2 , v2 q contains all the edges of G in the counterclockwise direction. This implies that the sum of the lengths of all the edges in the counter18

2∆
clockwise direction is at most 2∆
10 . However this means that the diameter of G is at most 10 which
is a contradiction.
All other cases are identical to the above cases up to relabeling of the vertices. Since we end
up with a contradiction in every case, this concludes the proof.

Lemma 5.1 implies that A and B are two disjoint consecutive segments of G. Let a1 , a2 , . . . , am
be the vertices of A in clockwise order. Let also b1 , b2 , . . . , bk be the vertices of B in clockwise
order. Let a11 and a1m be the meet-points of a1 and am respectively. If a1 and am do not have
such points we may introduce two vertices a11 and a1m by subdividing edges such that the induced
∆
∆
quasimetric does not change. By the construction, we have dpa1 , a11 q ă 10
and dpam , a1m q ă 10
.
1
1
Therefore, a1 lies between bi and bi`1 for some i P t1, 2, . . . , ku. Similarly, am lies between bj and
bj`1 for some j P t1, 2, . . . , ku (See Figure 6). Let B1 “ tb1 , b2 , . . . , bi u, B2 “ ta11 , bi`1 , . . . , a1m u, and
B3 “ taj`1 , . . . , bk u.

5.1

The algorithm for embedding into directed `1

We are now ready to describe the algorithm for computing a random quasipartition of G.
Input: A directed cycle G.
Output: A random quasipartition Q of the shortest-path quasimetric space of G.
Initialization: Set Q “ EpGq.
Step 1. Pick an arbitrary v1 P V . Let v1 , v2 , . . . , vn be the vertices of G in clockwise order. Let
∆
vn`1 “ v1 . Pick z1 , z2 P r0, 10
s uniformly at random.
Ñ
Ý
Step 2. For every j P t1, 2, . . . , nu, remove pvj , vj`1 q from Q if d pv1 , vj q ď i ¨
Ñ
Ý
∆
d pv1 , vj`1 q ą i ¨ 10
` z1 for some integer i ě 0.

∆
10

` z1 and

Ð
Ý
Step 3. For every j P t1, 2, . . . , nu, remove pvj`1 , vj q from Q if d pv1 , vj`1 q ď i ¨
Ð
Ý
∆
` z1 for some integer i ě 0.
d pv1 , vj q ą i ¨ 10

∆
10

` z1 and

Step 4. Pick z3 P r0, ∆s uniformly at random.
Ñ
Ý
Ñ
Ý
Ý
Step 5. For every pu, vq P EpÑ
p pa1 , a11 qq, remove pu, vq from Q if d pa1 , uq ď z3 and d pa1 , vq ą z3 .
Ð
Ý
Ð
Ý
Ý
Step 6. For every pu, vq P EpÐ
p pa1 , a11 qq, remove pu, vq from Q if d pa1 , uq ď z3 and d pa1 , vq ą z3 .
Ñ
Ý
Ñ
Ý
Ý
Step 7. For every pu, vq P EpÑ
p pam , a1m qq, remove pu, vq from Q if d pam , uq ď z3 and d pam , vq ą
z3 .
Ð
Ý
Ð
Ý
Ý
Step 8. For every pu, vq P EpÐ
p pam , a1m qq, remove pu, vq from Q if d pam , uq ď z3 and d pam , vq ą
z3 .
Ñ
Ý
Ñ
Ý
Ý
Step 9. For every pu, vq P EpÑ
p pa1 , a11 qq, remove pu, vq from Q if d pv, a11 q ď z3 and d pu, a11 q ą z3 .
Ð
Ý
Ð
Ý
Ý
Step 10. For every pu, vq P EpÐ
p pa1 , a11 qq, remove pu, vq from Q if d pv, a11 q ď z3 and d pu, a11 q ą
z3 .

19

Ñ
Ý
Ñ
Ý
Ý
Step 11. For every pu, vq P EpÑ
p pam , a1m qq, remove pu, vq from Q if d pv, a1m q ď z3 and d pu, a1m q ą
z3 .
Ð
Ý
Ð
Ý
Ý
Step 12. For every pu, vq P EpÐ
p pam , a1m qq, remove pu, vq from Q if d pv, a1m q ď z3 and d pu, a1m q ą
z3 .
Step 13. Enforce transitivity on Q. That is for all u, v, w P V pGq if pu, vq P Q and pv, wq P Q,
then add pu, wq to Q.
This concludes the description of the algorithm.

5.2

Analysis

We now analyze the random quasipartition computed by the above algorithm. We first argue that
the “probability of separation” is small for all pairs of vertices; this implies that the contraction of
the resulting embedding into `1 is bounded.
Lemma 5.2. For every u, v P V we have
Pr rpu, vq R Qs ě

Q„D

dpu, vq
.
2∆

Ý
Proof. Let X1 be the random event that there exists an edge e P Ñ
p pu, vq such that e R Q. Let X2
Ð
Ý
be the random event that there exists an edge e P p pu, vq such that e R Q. We want to show that
PrQ„D rX1 ^ X2 s ě dpu,vq
∆ .
Ð
Ý
Ñ
Ý
∆
∆
First suppose that pu, vq is a long pair. That is, either d pu, vq ě 10
or d pu, vq ě 10
. We
Ñ
Ý
∆
may assume w.l.o.g. that d pu, vq ě 10 (the analysis for the other case is similar). In this case,
by the Step 2 of the algorithm we have that PrQ„D rX1 s “ 1. This is because of the fact that
Ñ
Ý
∆
d pu, vq ě 10
. Also, from Step 3 of the algorithm we get PrQ„D rX2 s ě dpu,vq
∆ . Therefore, we have
dpu,vq
PrQ„D rX1 ^ X2 s ě ∆ .
Now suppose that pu, vq is a short pair. First suppose that v P B1 . In this case, by the
Ñ
Ý
construction we have that dpu, vq “ d pu, vq, and thus by Step 5 of the algorithm we have that
PrQ„D rX1 s ě dpu,vq
∆ . Also, by Steps 5 and 6 we have PrQ„D rX2 |X1 s “ 1, and hence we have
PrQ„D rX1 ^ X2 s ě dpu,vq
∆ , as desired. If v P B3 , a similar argument using Steps 7 and 8 of the
algorithm shows that PrQ„D rX1 ^ X2 s ě dpu,vq
∆ .
Ý
Ý
Ý
Ý
Now suppose that v P B2 . Let p1 “ Ñ
p pu, a11 q, p2 “ Ñ
p pam , vq, p3 “ Ð
p pu, a1m q, and p4 “ Ð
p pa1 , vq.
For every i P t1, 2, 3, 4u, let Yi be the random event that there exists an edge e P pi such that e R Q.
There are four cases:
Ñ
Ý
Ð
Ý
Ñ
Ý
Ð
Ý
Case 1. d pu, a11 q ě dpu, vq{2 and d pu, a1m q ě dpu, vq{2. First assume that d pu, a11 q ď d pu, a1m q.
Ñ
Ý
d pu,a11 q
By Step 6 of the algorithm we have that PrQ„D rX1 s ě PrQ„D rY1 s ě
ě dpu,vq
∆
2∆ .
Also by the construction and Step 10 of the algorithm, we have that PrQ„D rX2 |Y1 s “ 1.
Therefore, we have PrQ„D rX1 ^ X2 s ě dpu,vq
2∆ , as desired. The argument for the other case
Ñ
Ý
Ð
Ý
1
1
where d pu, a1 q ą d pu, am q is similar by considering Steps 8 and 12 of the algorithm.
Ñ
Ý
Ð
Ý
Ñ
Ý
Ð
Ý
Case 2. d pu, a11 q ě dpu, vq{2 and d pa1 , vq ě dpu, vq{2. If d pu, a11 q ď d pa1 , vq, then we follow a
similar argument as in the first case by considering Steps 9 and 10 of the algorithm. Otherwise,
we follow a similar argument by considering Steps 6 and 10.
20

Ñ
Ý
Ð
Ý
Ñ
Ý
Ð
Ý
Case 3. d pam , vq ě dpu, vq{2 and d pu, a1m q ě dpu, vq{2. If d pam , vq ď d pu, a1m q then a similar
argument as in the first case by considering Steps 7 and 8 applies here. Otherwise, a similar
argument considering Steps 8 and 12 applies here.
Ñ
Ý
Ð
Ý
Ñ
Ý
Ð
Ý
Case 4. d pam , vq ě dpu, vq{2 and d pa1 , vq ě dpu, vq{2. If d pam , vq ď d pa1 , vq, the a similar
argument using Steps 7 and 11 of the algorithm applies here. Otherwise, a similar argument
using Steps 5 and 6 applies here.
By considering all the above cases, we conclude that PrQ„D rpu, vq R Qs ě

dpu,vq
2∆ ,

as desired.

Next we prove that the probability of separation is not too large; this implies that the expansion
of the resulting embedding into directed `1 is bounded.
Lemma 5.3. For every pu, vq P E we have
Pr rpu, vq R Qs ď

Q„D

14dpu, vq
.
∆

Proof. Consider any edge pu, vq P E. First we observe that Steps 2,5,7,9 and 11 only remove edges in
the clockwise direction. Similarly Steps 3,6,8,10 and 12 only remove edges in the counter-clockwise
direction. W.l.o.g. let us assume that pu, vq is in the clockwise direction. This means that it may
10dpu,vq
be removed in Step 2 with probability at most wpu,vq
. Now in each of Steps 5,7,9 and 11
∆
∆{10 “
“ dpu,vq
we remove pu, vq with probability at most wpu,vq
∆
∆ . Taking the union bound we have that
the probability that pu, vq is removed from Q is at most 14dpu,vq
.
∆
Lemma 5.4. For every u, v P V we have
Pr rpu, vq R Qs ď

Q„D

14dpu, vq
.
∆

Proof. Let p be a shortest path from u to v in G. Suppose that pu, vq R Q. Since we enforce
transitivity in Step 13 this implies that an edge in p is removed before ř
Step 13. So we have
PrQ„D rpu, vq R Qs
that PrQ„D rpu, vq R Qs ď P rrAn edge in p is removed before Step 13s ď
pu,vqPp

using the union bound. Now applying Lemma 5.3 to all the edges of p we have that
Pr rpu, vq R Qs ď

Q„D

14dpu, vq
,
∆

which concludes the proof.
We are now ready to prove the main result of this Section.
Theorem 5.5. Let G be a directed cycle and let M “ pV pGq, dG q be its shortest-path quasimetric space. Then M admits a constant-distortion embedding into some convex combination of 0-1
quasimetric spaces denoted by D. Moreover we can sample a random 0-1 quasimetric space from
D in polynomial time.

21

Proof. The required convex combination of 0-1 quasimetrics is obtained from the distribution D
returned by the Algorithm. Every quasipartition Q in the support of D can be replaced with a 0-1
quasimetric where for any u, v P V dpu, vq “ 0 iff pu, vq P Q otherwise dpu, vq “ 0. Since D is a
probability distribution over quasipartitions this gives us a convex combination of 0-1 quasimetrics
φ. Now it remains to show that the distortion is Op1q.
For any u, v P V we denote the distance from u to v in φ dφ pu, vq. Now we have that ,
dφ pu, vq “ 1 ¨ P rQ„D rpu, vq R Qs ` 0 ¨ P rQ„D rpu, vq P Qs “ P rQ„D rpu, vq R Qs
From Lemmas 5.2 and 5.4 we have that,
1
1
ď dφ pu, vq ď 28dpu, vq ¨
2∆
2∆
This implies that the distortion is at most 28. The bound on the running time is immediate from
the description of the algorithm.
dpu, vq ¨

By using Theorem 5.5, we can obtain the following.
Proof of Theorem 1.7. First we observe that any quasipartition in the support of the distribution
D returned by the algorithm is obtained by removing at most 28 directed edges in EpGq and
enforcing transitivity. This follows immediately from our choice of z1 , z2 and z3 . Next consider any
u, v P V pGq and any Q P supppDq such that pu, vq R Q. Let S Ď EpGq denote the set of edges that
we remove before enforcing transitivity to obtain Q. Now we have |S| ď 28. We also have that
there exist e1 , e2 P S such that removing e1 and e2 from EpGq and enforcing transitivity ensures
that pu, vq is not in the resulting quasipartition. This is because G is a directed cycle and there
are exactly two directed paths from u to v. Therefore it suffices to remove a directed edge from
each of the two paths to obtain a quasipartition that does not contain pu, vq. This implies that
if we consider all possible ways to select two edges (one in the clockwise direction and one in the
counterclockwise direction such that they don’t overlap i.e. we do not pick px, yq and py, xq for all
px, yq P EpGq) from S, and then consider the quasipartition
`28˘obtained by removing them from EpGq
and enforcing transitivity we have a set PQ of at most 2 possible quasipartitions and pu, vq is
not in at least one of them. Now we consider the following distribution of quasipartitions. First
we pick Q from D. Then we pick uniformly at random a quasipartition from PQ . This gives us a
new distribution of quasipartitions D1 . Note that every quasipartition Q1 P supppD1 q is a directed
cut metric. This is because removing two directed edges in opposite directions as described earlier
and enforcing transitivity on the remaining edges to obtain Q1 partitions V pGq into U Ă V pGq and
V pGqzU such that px, yq R Q1 if x P U and y P V pGqzU and px, yq P Q1 otherwise. Therefore D1 is a
convex combination of directed cut metrics. Since the bound from lemma 5.2 decreases by at most
a factor of 28 when applied to D1 it follows that the distortion of D1 is at most 28 times larger than
that of D.

6

Embedding directed trees into directed `1

In this section we describe a method for embedding directed trees into directed `1 with distortion
one. Let G “ pV, Eq be a directed tree, and let w be a weight function on the edges of G. Let
M “ pX, dq be the shortest path quasimetric space induced by G. The following algorithm gives
us a distribution D over quasipartitions of G.
22

Input: A directed tree G.
Output: A random quasipartition Q.
Initialization:: Set Q “ EpGq.
ř
Step 1. Let W “
wpeq.
ePE

Step 2. Let DE be a distribution over E, where each edge e P E is sampled with probability
wpeq{W .
Step 3. Pick an edge e P E from the above distribution, and remove e from Q.
Step 4. Enforce transitivity on Q; that is, for all u, v, w P V pGq if pu, vq P Q and pv, wq P Q then
add pu, wq to Q.
Lemma 6.1. For every u, v P V we have PrQ„D rpu, vq R Qs “

dpu,vq
W .

Proof. Let P “ pa1 “ u, a2 , . . . , am “ vq be the unique shortest path from u to v in G. We have
that pu, vq R Q iff there exists an i P t1, 2, . . . , m ´ 1u such that pai , ai`1 q R Q. By the construction,
,ai`1 q
for every i P t1, 2, . . . , m ´ 1u we have that PrQ„D rpai , ai`1 q R Qs “ dpaiW
. Now note that the
algorithm only removes one edge from Q, and thus we have
Pr rpu, vq R Qs “

Q„D

m´1
ÿ
i“1

Pr rpai , ai`1 q R Qs “

Q„D

dpu, vq
,
W

as desired.
Now we are ready to prove the main result of this section.
Proof of Theorem 1.8. The above algorithm gives us a convex combination of quasipartitions, and
thus a convex combination of 0-1 quasimetrics with distortion one. The support of this convex
combination consists of 0-1 quasimetrics that are also directed cut metrics. This is equivalent to
an embedding into directed `1 , as desired.

7

Applications to directed cut problems

Directed Multicut problem Consider the Directed Multicut problem. Let P be the set of all
directed paths from a source terminal to its corresponding sink terminal. For every e P EpGq, we
define an indicator variable xpeq that indicates whether e belongs to a cut or not. We have the
following integer program for the problem:
ÿ
minimize
cpeqxpeq
subject to

ePEpGq
ÿ

xpeq ě 1,

@p P P

ePp

xpeq P t0, 1u, @e P EpGq
23

By relaxing this integer program, we get the following LP relaxation:
ÿ
minimize
cpeqxpeq
subject to

ePEpGq
ÿ

xpeq ě 1, @p P P

ePp

xpeq ě 0, @e P EpGq
Let x be the solution to the above LP relaxation. Let M be the quasimetric space induced by x.
Suppose there exists a p1 ´ εq-bounded β-Lipschitz distribution over quasipartitions of M D. Then
we can sample a quasipartition Q of M from D. Let SQ “ EpGqzQ. Since Q is p1 ´ εq-bounded,
we have that SQ is a valid Multicut solution. We have:
ÿ

ÿ
Epcpeqq “

EpcpSQ qq “
ePS

cpeq ¨ Prpe R Qq ď

ÿ

cpeq ¨ β

ePS

ePS

xpeq
β
ď
OPT
1´ε
1´ε

β
-approximation for the optimum Multicut solution.
This means that in expectation SQ is a 1´ε
β
Therefore it follows that there exists a quasipartition Q˚ P supppDq such that cpSQ˚ q ď 1´ε
OPT.

Proof of Theorem 1.4. The proof follows by combining the aforementioned result with the results
of Sections 3 and 4.
Directed Non-Bipartite Sparsest Cut The standard LP relaxation for this problem is as
follows:
ÿ
minimize
cpeqxpeq
subject to

ePEpGq
ÿ

dempiqdx psi , ti q ě 1

psi ,ti qPT

xpeq ě 0,

@e P EpGq

Here dx pu, vq denotes the shortest path distance induced by the function x in G. We also
denote
ÿ the optimal value of the objective function by OPT. Note that we may assume that
dempiqdx psi , ti q “ 1 when the optimum is achieved.
psi ,ti qPT

It is shown in [11] that the existence of a pσq, σ 1 Cq q-decomposition for undirected graphs implies
that the integrality gap for the (undirected) uniform demand Sparsest Cut problem is Opσσ 1 q. A
similar argument to the one used in Lemma 3.5 in that paper gives the following result.
Theorem 7.1. Let G be a directed graph. Suppose for all r ą 0 and all w : EpGq Ñ t0 Y R` u there
exists an r-bounded β-Lipschitz distribution over quasipartitions of the shortest path quasimetric
induced by w on G. Then the integrality gap of the LP relaxation for the Directed Non-Bipartite
Sparsest Cut problem with uniform demands and any choice of capacities on G is Opβq.
Proof. It is known that the solution of the LP relaxation for the Directed Non-Bipartite Sparsest Cut
problem is a weight function w : EpGq Ñ t0 Y R` u on G that induces a quasimetric space
M “ pV pGq, dq [16]. Let D be a 4n1 2 -bounded β-Lipschitz distribution over M . Every quasipartition Q P supppDq induces a cut SQ of G. If we pick randomly pick Q from D we have
24

βdpeq
ď 4n2 βOPT. This implies that there exists a quasipartition
r
i
Q˚ P supppDq such that SQ˚ ď 4n2 βOPT. Now consider the cut SQ˚ . Let T “ U1 , U2 , . . . , Um be
the collection of vertex sets of all maximal strongly connected components of GrEzSQ˚ s. Suppose
2
|Ui | ă 2n3 for all i P t1, . . . , mu. Then there exists r P t1, . . . , mu such that n6 ď |U1 Y . . . Y Ur | ď 5n
6
5n2
˚
and n6 ď |Ur`1 Y . . . Y Um | ď 5n
.
Furthermore
we
have
that
DpS
q
ě
.
This
is
because
for
all
Q
6
36
u P tU1 Y . . . Y Ur u and v P tUr`1 Y . . . Y Um u we have that either there is no path from u to v or
there is no path from v to u in GrEzSQ˚ s since each Ui is a maximal strongly connected component.
2
2
So we have that the sparsity of SQ˚ s is at most 4n5nβOPT
“ OpβOPTq. Suppose |Ui | ě 2n3 for some
2 {36
that the E rCpSQ qs ď

ÿ

cpeq

Q„D

i P t1, . . . , mu. Then we have that for all u, v P Ui dpu, vq ď 4n1 2 and dpv, uq ď 4n1 2 . So we can use
the same argument from Lemma 16 in [14] to obtain a cut with sparsity OpβOPTq. This implies
that the integrality gap of the LP relaxation is Opβq concluding the proof.
Proof of Theorem 1.1. The proof follows by combining Theorem 7.1 with Theorems 1.5 and 1.6.
Proof of Theorem 1.3. The proof follows by combining Theorem 7.1 with Theorems 1.5 and 4.11.
Proof of Theorem 1.2. Theorem A.1 from [4] due to Charikar, Makarychev and Makarychev implies
that, the non-uniform flow-cut gap for a digraph G is upper bounded by the minimum distortion for
embedding any shortest path quasimetric space supported on G, into a convex combination of 0-1
quasimetrics. Combined with Theorems 1.8 and 5.5 this implies the statement of the theorem.

8

Limitations of the Klein-Plotkin-Rao partitioning scheme

Let G be a directed planar graph, and let M denote the shortest-path quasimetric space of G. In
order to find a constant Lipschitz distribution over r-bounded quasipartitions of M , one may try
to generalize previous algorithm of [11], where their work is on undirected graphs. The following
algorithm is implicit in their work for planar undirected graphs.
Input: A planar connected graph G.
Output: A random r-bounded partition Q of the shortest-path metric space of G.
Initialization. Set G˚ “ G and Q “ EpGq.
Step 1. Pick z P r0, rs uniformly at random. Let c “ 3.
Step 2. For every connected component C of G˚ , proceed as follows. Pick an arbitrary x P V pCq.
For all pu, vq P EpG˚ q remove pu, vq from Q and EpG˚ q if dG˚ px, vq ą i ¨ r ` z and dG˚ px, uq ď
i ¨ r ` z for some integer i ě 0. Set c :“ c ´ 1.
Step 3. If c ą 0, recursively call Steps 1 ´ 2 for every connected component of G˚ .
Step 4. Enforce trasitivity on Q.

25

Figure 7: The graph G

Note that in this algorithm, we start with c “ 3, and thus the resulting partition is constant
Lipschitz. They show that for planar graphs, 3 rounds is enough to get an r-bounded partition.
However, this might not be true in the directed setting. A natural generalization of the above
algorithm to the directed setting is as follows. Instead of undirected edges in step 2, we consider
directed ones, and in step 3, we consider weakly connected components of G˚ . This generalization
fails to result in an r-bounded quasipartition for the directed case. We provide the following counter
example. Let G be the graph as shown in figure 7. It is easy to check that G is a graph of pathwidth 2. Now suppose that the first time we call step 2 of the algorithm, we pick x “ v0 . Therefore,
no edges will be removed from Q. Now suppose that the next call of step 2, picks x “ v1 , and
the next call picks x “ v2 , and so on. After 3 levels of calling the second step, we do not get an
r-bounded quasipartition. This means that in order to get an r-bounded quasipartition, we need
to call this step Ωpnq times, and thus the resulting quasipartition will not be Op1q-Lipschitz.

9

Lower bound for random embeddings of the directed cycle into
trees

Proof of Theorem 1.9. We will consider the directed cycle in the following description. Let the set
of vertices V “ tv0 , v2 , . . . , vn´1 u. Let the set of edges be E “ tpvi , vpi`1 mod nq q|i P r0, n ´ 1su.
Furthermore let all the edges have unit weight.
Let S denote the set of all non-contracting embeddings of G into directed trees. Let Q denote
the set of all distributions over edges in G. Let D denote the set of all distributions over S.
The least distortion of any
„ random
 embedding of G into directed trees is denoted by OPT where
dH pu, vq
OPT “ min max E
“ min max E rdH pu, vqs since all edges have unit weight.
F PD pu,vqPE H„F
hPD pu,vqPE H„F dG pu, vq
This is lower bounded by the Von Neumann dual problem given by max min E rdH pu, vqs.
qPQ HPS pu,vq„q

Therefore for all q P Q we have that min

E

HPS pu,vq„q

rdH pu, vqs ď OPT. Now we will set q to be the

uniform distribution over edges in E. Next consider any H P S. We have that

E

rdH pu, vqs “

pu,vq„q

1
n

ÿ

dH pvi , vpi`1 mod nq q. Let us denote the expression

ř

dH pvi , vpi`1 mod nq q by X. Let

iPr0,n´1s

iPr0,n´1s

L be the set of vertices of degree 1 in the underlying undirected graph of H. Furthermore let the
vertices in L be labeled as follows. L “ tvx0 , vx2 , . . . , vxm´1 u where for
ř any j P r0, m ´ 1s we have
that xj P r0, n ´ 1s and x1 ă x2 . . . ă xm . We have that X ě
dH pvi , vpi`1 mod mq q. Let
jPr0,m´1s

26

us denote

ř

dH pvi , vpi`1 mod mq q by Y . Note that Y is the length of a walk traversing all

jPr0,m´1s

the leaf vertices in H in the order given by the indices of the vertices in L and terminating at
the starting vertex vx0 . Since every directed edge in H separates at least one pair of leaves in one
direction it must be that ř
every directed edge in H is traversed at least once during this walk. So
this implies that Y ě
dH pu, vq. Now consider any directed edge pu, vq P EpHq. We have
pu,vqPEpHq

that dH pu, vq ` dH pv, uq ě n. This is because H is non-contracting and for any u, v P V pGq we have
that dG pu, vq ` dG pv, uq “ n. Therefore we have that X ě Y ě npn ´ 1q. This implies that given
1
our choice of q and for any H P S we have E rdH pu, vqs “ X ě Ωpnq. Therefore OPT ě Ωpnq,
n
pu,vq„q
which concludes the proof.

References
[1] Amit Agarwal, Noga Alon, and Moses S Charikar. Improved approximation for directed cut
problems. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing,
pages 671–680. ACM, 2007.
[2] Sanjeev Arora, James Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. Journal
of the American Mathematical Society, 21(1):1–21, 2008.
[3] Yonatan Aumann and Yuval Rabani. An o (log k) approximate min-cut max-flow theorem
and approximation algorithm. SIAM Journal on Computing, 27(1):291–301, 1998.
[4] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Directed metrics and directed
graph partitioning problems. In Proceedings of the seventeenth annual ACM-SIAM symposium
on Discrete algorithm, pages 51–60. Society for Industrial and Applied Mathematics, 2006.
[5] Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Embedding k-outerplanar graphs into l1. SIAM Journal on Discrete Mathematics, 20(1):119–136,
2006.
[6] Joseph Cheriyan, Howard Karloff, and Yuval Rabani. Approximating directed multicuts. Combinatorica, 25(3):251–269, 2005.
[7] Julia Chuzhoy and Sanjeev Khanna. Hardness of cut problems in directed graphs. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 527–536.
ACM, 2006.
[8] Julia Chuzhoy and Sanjeev Khanna. Polynomial flow-cut gaps and hardness of directed cut
problems. Journal of the ACM (JACM), 56(2):6, 2009.
[9] Anupam Gupta, Ilan Newman, Yuri Rabinovich, and Alistair Sinclair. Cuts, trees and 1embeddings of graphs. Combinatorica, 24(2):233–269, 2004.
[10] Mohammad Taghi Hajiaghayi and Harald Räcke. An-approximation algorithm for directed
sparsest cut. Information Processing Letters, 97(4):156–160, 2006.

27

[11] Philip Klein, Serge A Plotkin, and Satish Rao. Excluded minors, network decomposition, and
multicommodity flow. In Proceedings of the twenty-fifth annual ACM symposium on Theory
of computing, pages 682–690. ACM, 1993.
[12] Yana Kortsarts, Guy Kortsarz, and Zeev Nutov. Greedy approximation algorithms for directed
multicuts. Networks, 45(4):214–217, 2005.
[13] James R Lee and Anastasios Sidiropoulos. On the geometry of graphs with a forbidden minor.
In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 245–
254. ACM, 2009.
[14] Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in
designing approximation algorithms. Journal of the ACM (JACM), 46(6):787–832, 1999.
[15] Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its
algorithmic applications. In Foundations of Computer Science, 1994 Proceedings., 35th Annual
Symposium on, pages 577–591. IEEE, 1994.
[16] Facundo Mémoli, Anastasios Sidiropoulos, and Vijay Sridhar. Quasimetric embeddings and
their applications. arXiv preprint arXiv:1608.01396, 2016.
[17] Michael Saks, Alex Samorodnitsky, and Leonid Zosin. A lower bound on the integrality gap
for minimum multicut in directed networks. Combinatorica, 24(3):525–530, 2004.
[18] Anastasios Sidiropoulos. Non-positive curvature and the planar embedding conjecture. In
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages
177–186. IEEE, 2013.

28

