1 Introduction↩︎

Decomposing graphs into well-structured pieces is a central paradigm in the design of graph algorithms. In particular, low diameter decompositions (LDDs), which are a distribution over partitions of the vertices into bounded-diameter clusters such that nearby vertices are likely to be clustered together, have played a central role in undirected graphs. They serve as key primitive underlying a wide range of problems, a partial list of examples include: metric embedding [1]–[5], multi-commodity flow [6], [7], Steiner point removal [8], near-linear SDD solvers [9], Lipschitz extension [10], spanners [11], [12], and more. In undirected graphs, low diameter decompositions have been extensively studied not only in general graphs, but also in structured graph classes [6], [13]–[18], where additional structure often leads to improved guarantees.

Recently, there has been a growing interest in extending low diameter decompositions to directed graphs [19]–[22], despite the inherent technical challenges compared to the undirected setting. A notable application of this line of work is a recent near-linear time algorithm for the negative-weight single-source shortest path (SSSP) problem [20]. A strongly connected component of a directed graph \(G\), an SCC in short, is a maximal subgraph \(H\) of \(G\) such that for every pair \(u,v\) of vertices in \(H\), both \(u\) is reachable from \(v\) and \(v\) is reachable from \(u\). For vertices \(u,v\) of \(G\), let \(d_G(u,v)\) denote the length of a shortest directed path from \(u\) to \(v\) in \(G\), with \(d_G(u,v)=\infty\) if no such path exists. For a subgraph \(H\subseteq G\), the strong diameter of \(H\) is \(\max_{u,v\in V(H)} d_H(u,v)\), whereas the weak diameter of \(H\) is \(\max_{u,v\in V(H)} d_G(u,v)\). Here, \(V(H)\) denotes the vertex set of \(H\).

On the other hand, a parallel line of work has focused on quasipartitions for directed graphs [23]–[25], motivated by their connection to the integrality gap of the directed sparsest cut problem and the directed multicut problem [26].

Notably, quasipartitions impose strictly stronger constraints than LDDs, and thus any \((\beta, \Delta)\)-quasipartition immediately yields a \((\beta,\Delta)\)-LDD, but not vice versa. Intuitively, in the quasipartition construction, one has to enforce that the distance between endpoints of every valid path is at most \(\Delta\). In contrast, the LDD construction only restricts the distance between endpoints of the paths within a strongly connected component. One specific example is directed acyclic graphs (DAGs), which are directed graphs avoiding directed cycles. It is easy to observe that every DAG itself is a \((0, \Delta)\)-LDD for every parameter \(\Delta>0\) since its SCCs are isolated singletons. On the other hand, constructing a quasipartition with a small loss parameter on a DAG remains highly non-trivial, as a DAG still might contain arbitrarily long paths that must be cut. This separation is also reflected in a polynomial gap over the achievable loss parameters. While every directed graph on \(n\) vertices admits an \((O(\log n \cdot \log\log n), \Delta)\)-LDD [21], there exists an \(n\)-vertex directed graph that does not admit any \((o(n^{1/7}\log^{4/7} n), \Delta)\)-quasipartition [23].

Quasipartitions and LDDs are not merely theoretical concepts. Rather, they play a crucial role in driving distance-preserving graph sparsification scheme. Here, the goal is to obtain a simplified representation of the given graph while approximately preserving its distances. A number of such structures for directed graphs have been studied: including spanners [27], distance preservers [28], hopsets [29], and more. From the aforementioned lower bound for the quasipartition construction, [23] showed that one cannot efficiently embed a directed graph into quasiultrametric space, which is equivalent to the shortest path metric in directed trees. In contrast, by changing the viewpoint to LDDs, Assadi, Hoppenworth, and Wein [30] showed that one can (stochastically) embed any directed graph into two DAGs with distortion \(O(\log^3 n)\). Very recently, the distortion bound has been improved to \(O(\log n\cdot \log\log n)\) by Filtser [31].

In structured directed graph classes, the distinction between the two decompositions remains poorly explored. First, all known LDD results for structured directed graphs have an indirect nature: Instead of being tailored directly to LDDs, they are either obtained via quasipartition constructions (bounded pathwidth and bounded treewidth [23], [25]) or simply bypassed by applying general graph bounds [21] (planar graphs [24]). In addition, there are no techniques that are specifically tailored to constructing LDDs in this setting.

Second, among the prior works that are indirectly derived from the quasipartition constructions, the resulting bounds fail to yield a clear improvement over the general graph bounds. Specifically, the loss parameter either suffers from a polynomial dependence on treewidth [23] or even worse, an exponential dependency on pathwidth [25]. Consequently, these results surpass the general bounds of [21] only when the parameters are strictly sublogarithmic in the graph size.

To overcome these barriers, a natural starting point is to focus on pathwidth [32]- one of the most standard and well-studied graph parameters which intuitively measures the degree to which a given graph resembles a path. Indeed, based on their structural advantage, bounded pathwidth graphs admit a wide range of efficient algorithms for fundamental graph problems [33]–[37]. From the perspective of LDDs, such graphs also enjoy improved guarantees on the loss parameter compared to general graphs in the undirected setting [15]. Hence, it is natural to ask whether the same phenomenon holds in the directed setting.

Motivated by these insights and the gap between the undirected and directed settings, we initiate the study of LDDs in structured directed graphs, especially bounded pathwidth graphs, moving beyond those obtained indirectly via quasipartition approaches. Our main result is that every directed graph of pathwidth \(\mathsf{pw}\) admits an \((O(\mathsf{pw}), \Delta)\)-LDD. This significantly improves the previous best-known result of \((2^{O(\mathsf{pw}^2)}, \Delta)\)-LDD [23] in this setting.

Classical constructions of (undirected/directed) LDDs rely on the ball carving technique [1], where we recursively compute clusters by removing regions defined by distance thresholds around a center. In graphs of bounded pathwidth, prior work for undirected graphs [15] bypasses the general bound of [1] via a path-carving approach: repeatedly choosing a shortest path as a backbone and removing a distance-threshold neighborhood around it, exploiting the path-like structure of the graph. Provided that one can efficiently remove this neighborhood [15], [40], this approach yields an improved loss bound compared to [1].

On the other hand, in general directed graphs, one natural difficulty is that, once we carve a nearby region around a center as a cluster, we cannot guarantee the diameter of the cluster. To overcome this difficulty, all prior works that directly compute LDDs [19]–[22] recursively apply the ball carving approach for each carved cluster. It seems difficult to eliminate the \(\log n\) dependency on the loss parameter under this approach.

Our main technical contribution is a novel carving procedure with respect to a shortest path, which we call scissors carving, that avoids this difficulty. In essence, our approach carefully decomposes a shortest path into shorter subpaths, and applies the ball carving to each segment in a “local" sense. The key insight is that, we can efficiently carve away a path whose length is sufficiently short³. In addition, we ensure that any carved cluster from such short paths has a small diameter. We believe that our technique provides a first step toward developing LDD techniques tailored to structured directed graphs, and that the technique itself is of independent interest.

As a secondary contribution, we revisit quasipartitions in directed graphs of bounded treewidth [23], and improve the \(O(\mathsf{tw}\log^2 n)\) bound on the integrality gap of the directed non-bipartite sparsest cut [23] by a factor of \(O(\log n)\), through a better analysis. Previous and new results about the integrality gap are summarized in Table 2. See Section 5 for the problem definitions and details of prior works on it.

2 Preliminaries↩︎

For a positive integer \(n\), we denote by \([n]\) the set of all positive integers at most \(n\).

2.0.0.1 Graph notations.

Let \(G = (V, E, w)\) be an edge-weighted directed graph, with \(n\) vertices. We often use \(V(G)\) and \(E(G)\) to denote the vertex set and the edge set in \(G\), respectively. For a set \(A\) of vertices in \(G\), we use \(G\setminus A\) to denote the graph obtained from \(G\) by removing all vertices in \(A\) and their adjacent edges. We use \(G[A]\) to denote a induced subgraph of \(G\) with respect to \(A\). That is, \(G[A]=G\setminus (V\setminus A)\). Similarly, for a set \(B\) of edges in \(G\), we use \(G\setminus B\) to denote the graph obtained from \(G\) by removing all edges in \(B\). Two vertices \(u,v\) in \(G\) are strongly connected if there exist both a \(u\)-\(v\) path and a \(v\)-\(u\) path in \(G\). A graph \(G\) is strongly connected if there is a \(u\)-\(v\) path for every \(u,v\in V\). A strongly connected component of \(G\), an SCC in short, is a maximal strongly connected subgraph of \(G\). For a path \(P\) in \(G\), the length of \(P\) is defined as the total edge weight in \(P\). We use \(d_G(u,v)\) to denote the distance between \(u\) and \(v\) in \(G\). The diameter of \(G\) is defined as the maximum value of \(d_G(u,v)\) among every pair \((u,v)\in V\times V\).

2.0.0.2 Treewidth and Pathwidth.

A tree-decomposition (resp. path-decomposition) of an undirected graph \(G\) is a pair \((T, \{B_t\}_{t\in V(T)})\) consisting of a tree (resp. path) \(T\) and a family of sets \(\{B_t\}_{t\in V(T)}\) of vertices in \(G\) such that

1. \(V(G)=\bigcup_{t\in V(T)}B_t\),

2. for every edge \(uv \in E(G)\), there exists a node \(t \in V(T)\) such that \(\{u, v\} \subseteq B_t\), and

3. for every vertex \(v \in V(G)\), the set \(\{t\in V(T):v\in B_t\}\) induces a connected subtree (resp. subpath) of \(T\).

The width of a tree-decomposition (resp. path-decomposition) \((T, \{B_t\}_{t \in V(T)})\) is defined as \(\max_{t\in V(T)}\lvert B_t\rvert-1\). The treewidth \(\mathsf{tw}(G)\) (resp. pathwidth \(\mathsf{pw}(G)\)) of a graph \(G\) is the minimum width among all tree decompositions (resp. path decompositions) of \(G\).

For a directed graph \(G=(V,E)\), we consider the undirected graph \(\bar G\) obtained by ignoring the edge directions and removing any parallel edges. Formally speaking, \(\bar G\) has a vertex set \(V(\bar G)=V\) and an edge set \(E(\bar G)=\{\{u,v\}\mid (u,v)\in E \text{ or } (v,u)\in E\}\). We say that \(G\) has treewidth (resp. pathwidth) \(k\) if its underlying undirected graph \(\bar G\) has treewidth (resp. pathwidth) \(k\).

3 Technical Overview↩︎

3.0.0.1 Low diameter decomposition (LDD) for undirected graphs.

Let \(G=(V,E,w)\) be an undirected graph. A \((\beta, \Delta)\)-LDD of \(G\) is a distribution over vertex partitions of \(V\) such that in every partition, each cluster has a diameter of at most \(\Delta\), and for every pair \(u,v\in V\), the probability that \(u,v\) belong to different clusters is at most \(\beta\cdot \frac{d_G(u,v)}{\Delta}\). We call \(\beta\) the loss parameter. Every \(n\)-vertex graph admits an \((O(\log n), \Delta)\)-LDD for any \(\Delta>0\), which is tight [1].

Ball carving is a classical technique for computing an LDD. For a vertex \(u\in V\) and parameter \(R>0\), a ball \(B_G(u,R)\) is defined as the set of vertices \(v\in V\) such that \(d_G(u, v)\leq R\). We call \(R\) the radius of \(B_G(u,R)\). The algorithm of Bartal [1] repeatedly takes a vertex \(w\) from the remaining graph, samples a radius \(R\) from an exponential distribution with the parameter \(\Theta(\log n/\Delta)\), and removes the ball \(B_G(w, R)\) from the graph as a single cluster. Using the memoryless property of the exponential distribution, Bartal [1] showed that the algorithm yields an \((O(\log n), \Delta)\)-LDD.

3.0.0.2 Low diameter decomposition for bounded pathwidth graphs.

Abraham et al. [15] showed that if \(G\) has pathwidth \(\mathsf{pw}\), it admits an \((O(\log \mathsf{pw}),\Delta)\)-LDD. While this is a special case of a more general framework for minor-free graphs, we sketch their approach for the bounded pathwidth graphs. The following lemma was implicitly proved by several works (e.g., [15], [40]).

Their algorithm works in several rounds. In each round, for each connected component in the current graph, we pick a shortest path \(P\) connecting a vertex in the first bag and a vertex in the last bag (in a path decomposition), and compute a net \(N\) of that path using Lemma 1. Next, for each \(v\in N\), we sample a radius \(R_v\) from a truncated exponential distribution with a parameter \(\lambda\) over the range \([\frac{\Delta}{4}, \frac{\Delta}{2}]\) so that each cluster has a diameter at most \(\Delta\). That is, the exponential distribution with the parameter \(\lambda\) conditioned on the event that the output belongs to \([\frac{\Delta}{4}, \frac{\Delta}{2}]\). We will define \(\lambda\) later. Finally, we carve \(B_G(v,R_v)\) from the current graph as a single cluster.

Crucially, due to the covering property of Lemma 1, all vertices of \(P\) are carved away after the carving step. Moreover, since \(P\) is a path connecting a vertex in the first bag and a vertex in the last bag, \(P\) intersects every bag of the path decomposition. Therefore, the pathwidth of the graph decreases by at least one. Thus, the algorithm terminates after \(\mathsf{pw}\) rounds. Due to the sparsity property of Lemma 1, we can show that for every pair \(u,v \in V\), at most \(\nu = O(\mathsf{pw})\) balls, called threateners, affect the probability that \(u,v\) belong to different clusters.

Roughly speaking, the truncated exponential distribution behaves similarly to the exponential distribution, i.e., retaining a memoryless property, up to a small error. These errors from the sampled radii of different threateners are accumulated. In order to keep the total error negligible, the parameter should be at least logarithmic in the number of threateners. In light of this, Abraham et al. [15] set the parameter \(\lambda = \Theta(\frac{\log \nu}{\Delta})=\Theta(\frac{\log \mathsf{pw}}{\Delta})\), yielding an \((O(\log \mathsf{pw}), \Delta)\)-LDD of \(G\). This path-carving framework is the key ingredient that we will adapt to the directed setting later.

3.0.0.3 Low diameter decomposition for general directed graphs.

A directed analogue of the low diameter decomposition (Definition 1) was very recently introduced by Bernstein, Gutenberg, and Wulff-Nilsen [19] (though not stated explicitly), who showed that every \(n\)-vertex directed graph \(G\) admits an \((O(\log^2 n), \Delta)\)-LDD for every parameter \(\Delta>0\). Later, Bernstein, Nanongkai, and Wulff-Nilsen [20] explicitly defined the notion of a low diameter decomposition and presented a simpler algorithm yielding an \((O(\log^2 n), \Delta)\)-LDD. This bound has been improved to \(O(\log n \cdot \log\log n)\) by Bringmann et al. [21].

The algorithm of Bernstein et al. [20] follows the ball carving framework: it samples a radius and carves either an in-ball or an out-ball⁴ around a chosen vertex. A key difficulty in the directed setting is that, unlike the undirected case, one cannot guarantee the weak diameter bound of an SCC contained in a single ball. To resolve this, the algorithm of [20] recursively applies the same carving procedure to every SCC until all SCCs have a small weak diameter. By carefully selecting centers, Bernstein et al. [20] managed to bound the recursion depth by \(O(\log n)\). This yields an \(O(\log^2 n)\) bound on the loss parameter.

3.1 Low diameter decomposition for special classes of directed graphs↩︎

The aforementioned issue remains even for special classes of directed graphs, such as those with bounded pathwidth, bounded treewidth, or planar graphs. We briefly review some prior works that circumvented this issue. We remark that while all prior work primarily addressed random quasipartitions for those graph classes, their quasipartition results directly translate to low diameter decompositions with the same loss parameter⁵. Consequently, we present the prior work from the viewpoint of low diameter decompositions.

3.1.0.1 Separator-based approach.

Mémoli, Sidiropoulos, and Sridhar [23] showed that every \(n\)-vertex directed graph with treewidth \(\mathsf{tw}\) admits an \((O(\mathsf{tw}\log n), \Delta)\)-LDD for every parameter \(\Delta>0\). Their approach is based on a balanced separator. We call \(U\subset V(G)\) a balanced separator if the number of vertices in each connected component of \(G\setminus U\) is at most \(\frac{2}{3}|V(G)|\). It is well known that every graph \(G\) with treewidth \(\mathsf{tw}\) admits a balanced separator \(U\subset V(G)\) of size at most \(\mathsf{tw}+1\).

The algorithm of [23] computes a balanced separator \(U\), samples a radius, and constructs both in-balls and out-balls around each vertex of \(U\). Next, it adds the boundary edges of these balls to the cutset \(S\). Then, it recursively proceeds on each SCC of \(G\setminus U\). Critically, any SCC of \(G\setminus S\) is either disjoint from \(U\) or has a weak diameter of at most \(\Delta\). The loss parameter at a single recursion level is \(O(\mathsf{tw})\) since the algorithm computes a cutset through \(2|U|=O(\mathsf{tw})\) balls. In addition, the recursion depth is \(O(\log n)\). Overall, the algorithm of [23] yields an \((O(\mathsf{tw}\log n), \Delta)\)-LDD.

Kawarabayashi and Sidiropoulos [24] showed that every \(n\)-vertex planar directed graph admits an \((O(\log^2 n), \Delta)\)-LDD. Instead of a (balanced) vertex separator, they utilized the shortest path separator of [43], which consists of a constant number of shortest paths. Again, the \(O(\log n)\) factor arises from the fact that the recursion depth is \(O(\log n)\). We remark that it seems difficult to avoid the \(O(\log n)\) factor in any separator-based approach since the recursion depth is \(O(\log n)\) and the edge-cut probability incurred in each round must be handled independently.

3.1.0.2 LDD of constant loss parameter for bounded pathwidth directed graphs.

Salmasi, Sidiropoulos, and Sridhar [25] showed that every \(n\)-vertex directed graph \(G\) with pathwidth \(\mathsf{pw}\) admits a \((2^{O(\mathsf{pw}^2)}, \Delta)\)-LDD for every parameter \(\Delta>0\). This is the only known LDD result for structured directed graphs where the loss parameter is independent of \(n\).

We briefly sketch their approach at a high level. We start by setting the current graph to \(H=G\). In each round, [25] computes a \(u\)-\(v\) shortest path \(P\) that connects the first and last bags of the path decomposition. Instead of carving the balls around the net vertices along \(P\), the algorithm computes a random shift \(z\in [0,\Delta]\) and adds all edges crossing distances of \(i\Delta+z\) from \(u\) for every integer \(i\), to the cutset. Notably, after this, they remove the edge set of \(P\) from \(H\) (recall that in the ball carving framework, the cutset is removed) and recurse. Finally, the algorithm repeats the entire procedure in the reversed direction. The recursion depth is \(O(\mathsf{pw}^2)\).

Salmasi, Sidiropoulos, and Sridhar [25] managed to eliminate the dependency on \(n\) by carving away the boundary edges of concentric layers with a random shift. On the other hand, they remove the edge set of \(P\) instead of the cutset edges. This causes a more involved analysis of bounding the weak diameter, and yields a \((2^{O(\mathsf{pw}^2)}, \Delta)\)-LDD. We also remark that their analysis crucially utilizes the structure of the bounded pathwidth graphs, making it seemingly difficult to lift their result to bounded treewidth graphs or planar graphs.

3.2 Our solution: Scissors Carving↩︎

Our algorithm departs from the previous approaches. We develop a new carving procedure, which we call scissors carving. This is our main technical contribution that enables us to achieve an \((O(\mathsf{pw}), \Delta)\)-LDD. Let \(G=(V,E,w)\) be an edge-weighted directed graph. For a vertex \(u\in V\) and a parameter \(R>0\), we define the out-ball \(B_{G}^+(u,R)\) and the in-ball \(B_{G}^-(u,R)\) as \[\begin{align} &B_{G}^+(u,R) :=\{x\in V\mid d_G(u,x) \leq R\}, \text{ and } B_{G}^-(u,R) :=\{x\in V\mid d_G(x,u) \leq R\}, \text{ respectively.} \end{align}\] We call \(R\) the radius.

At a high level, suppose we are given a target \(x\)-\(y\) path \(P\) that we want to carve away. We compute an out-ball around \(x\) and an in-ball around \(y\) with radii proportional to \(d_G(x,y)\), and then remove their boundary edges. Then, we recurse on each SCC intersecting \(P\).

The key insight is that this approach always makes progress for each recursive SCC: either the length of the portion of \(P\) contained in each SCC, called the forward distance, is reduced, or the pathwidth of the SCC is decreased. Once the length of the current path becomes sufficiently small, we apply the same procedure in the reverse direction, i.e., computing an in-ball around \(x\) and an out-ball around \(y\), to reduce the backward distance \(d_G(y,x)\). The separation between the forward-reduction stage and the backward-reduction stage is essential, as reducing the backward distance using two balls is only possible once the forward distance is sufficiently small.

We demonstrate the two advantages of the scissors carving framework as follows. First, we recursively compute two balls of geometrically decreasing radii. Even though we may compute many balls across the recursion, most of them have radii much larger than \(\Delta\). This allows us to bound the edge cut probability by \(\Pr[e\in S]\leq O(1)\cdot \frac{w(e)}{\Delta}\).

Second, after both the forward-reduction stage and the backward-reduction stage, we ensure that both the forward distance and the backward distance of each remaining SCC \(H\) are sufficiently small. Using this structural advantage, we show that any SCC of \(H\) fully contained in a single ball of radius \(\Delta\) around \(u\in H\) has a weak diameter of at most \(O(\Delta)\). This overcomes the limitation that, in general directed graphs, an SCC contained in a single ball of radius \(\Delta\) can have an arbitrarily large diameter. This allows us to ensure the desired diameter bound.

Based on the scissors carving procedure, we compute an \((O(\mathsf{pw}), \Delta)\)-LDD following the framework of [15]. Specifically, we start by setting the current graph to \(H=G\). At each stage, we take a shortest path \(P\) in \(H\) that we want to carve away. In particular, we choose \(P\) such that \(\mathsf{pw}(H\setminus P) < \mathsf{pw}(H)\). Then, we apply scissors carving to \(P\) and update the cutset \(S\). This ensures that every SCC of \(H\setminus S\) either has a bounded weak diameter or a reduced pathwidth (See Lemma 2). Furthermore, we shall guarantee that every SCC disjoint from \(P\) has a reduced pathwidth. Then, we recurse on every SCC of \(H\setminus S\) whose weak diameter is greater than \(\Delta\). By taking the union \(S\) of the cutsets computed from all recursive calls, we ensure that every SCC of \(G\setminus S\) has a weak diameter of at most \(\Delta\). The recursion depth is at most \(\mathsf{pw}(G)\). Due to the union bound of probability, the probability bound of Lemma 2 yields \(\Pr[e\in S] \leq O(\mathsf{pw}(G))\cdot \frac{w(e)}{\Delta}\).

In the rest of this section, we explain the core idea of the scissors carving technique and give a proof sketch of Lemma [lem:reduce-pathwidth], especially for the first statement. We begin by defining some notation used in this paper. For a vertex set \(C\subseteq V\), we denote the set of edges whose source endpoint is in \(C\) and target endpoint is outside \(C\) by \(\delta^+(C)\). Similarly, we denote the set of edges whose source endpoint is outside \(C\) and target endpoint is inside \(C\) by \(\delta^-(C)\).

Let \(H\) be a subgraph of \(G\) and \(P\) be a shortest path in \(G\) whose two endpoints are contained in \(H\). For a strongly connected subgraph \(C\) of \(H\), let \(u\) and \(v\) be the first and the last vertices of \(P\cap C\) (along the order of \(P\)), respectively. We define the surviving subpath of \(P\) with respect to \(C\), denoted as \(P[C]\), as the \(u\)-\(v\) subpath of \(P\). Note that \(P[C]\) may not be fully contained in \(C\). We define the forward distance and the backward distance of \(C\) (with respect to \(P\)) as \(d_G(u,v)\) and \(d_G(v,u)\), respectively, and denote them by \(f_P(C)\) and \(b_P(C)\), respectively. Note that we analyze these distances with respect to the shortest paths in \(G\), rather than the current subgraph \(C\). This is sufficient for our purpose since our goal is to bound the weak diameter of each SCC.

We use the following lemma. See Figure 2 for an illustration and Section 4 for its proof.

Next, we explain the scissors carving procedure. We are given a strongly connected subgraph \(H\) of \(G\) and a shortest path \(P\) as input, such that the two endpoints of \(P\) are contained in \(H\), and \(\mathsf{pw}(H\setminus P)<\mathsf{pw}(H)\). The algorithm consists of three stages, and the first two stages operate recursively. As we will see below, these stages aim to reduce the forward distance, reduce the backward distance, and bound the weak diameter of each SCC, respectively.

3.2.0.1 First stage: reducing forward distance.

In the first stage we are given a strongly connected subgraph \(C\) of \(H\) as input. Let \(P[C]=\langle u,\ldots, v\rangle\) and \(\tau = f_P(C)\). We sample the radius \(R\) uniformly at random from \([\frac{1}{2}\tau, \frac{2}{3}\tau]\), and compute two balls \(B_1=B_{G}^+(u,R)\), \(B_2=B_{G}^-(v,R)\) and add their boundary edges \(\delta^+(B_1)\cup \delta^-(B_2)\) into the cutset \(S\). We then recursively apply this approach to each SCC of \(C\setminus S\) contained in \(B_1\cup B_2\). We halt the first stage when \(f_P(C)\leq \Delta\), and proceed to the second stage. This completes the algorithm for the first stage.

We show that the above procedure ensures that each resulting SCC for the recursive calls has a reduced forward distance, while the remaining SCCs have a reduced pathwidth. Hence, it suffices to proceed with the SCCs of the former type, i.e., those with a reduced forward distance. To see this, since we take \(R\) from the range \([\frac{1}{2}\tau, \frac{2}{3}\tau]\) and \(P[C]\) is a shortest path in \(G\), for every \(w\in P[C]\), either \(d_G(u, w)\leq R\) or \(d_G(w,v)\leq R\). Hence, \(P\subseteq B_1\cup B_2\). In addition, due to Lemma [lem:twoball-fin], every SCC of \(C\setminus S\) is either fully contained in \(B_1\), or fully contained in \(B_2\setminus B_1\), or disjoint from \(B_1\cup B_2\). Let \(C'\) be an SCC of \(C\setminus S\) and \(P[C']=\langle x,\ldots, y\rangle\). Since \(P[C']\) is a subpath of \(P\) and \(C'\subseteq C\), \(P[C']\) is a subpath of \(P[C]\). If \(C'\) is contained in \(B_1\), we have that \[d_G(x,y) \leq d_G(u, y) \stackrel{B_1}\leq R \leq \frac{2}{3}\tau.\] Otherwise, if \(C'\) is contained in \(B_2\setminus B_1\), we have that \[d_G(x,y)\leq d_G(x,v) \stackrel{B_2}\leq R \leq \frac{2}{3}\tau.\] Finally, if \(C'\) is disjoint from \(B_1\cup B_2\), \(P\subseteq B_1\cup B_2\) implies that \(C'\) is a subset of \(C\setminus P\). Then, we have that \(\mathsf{pw}(C') \leq \mathsf{pw}(C\setminus P) \leq \mathsf{pw}(H\setminus P) < \mathsf{pw}(H)\). Hence, we conclude that every SCC of \(G\setminus S\) either has a reduced forward distance or a reduced pathwidth, as desired.

3.2.0.2 Second stage: reducing backward distance.

In the second stage, we are given a strongly connected subgraph \(C\) of \(H\) as input with the additional property that \(f_P(C)\leq \Delta\). Let \(P[C]=\langle u,\ldots, v\rangle\) and \(b_P(C)=\tau'\). Importantly, throughout this stage, we ensure that the condition on \(f_P(C)\) always holds. Our algorithm is almost identical to that of the first stage, except that we compute two balls in the reversed direction and sample the radius \(R\) from a narrower interval. The reason we choose a narrower interval is to reduce the backward distance by a constant fraction.

More precisely, we sample \(R\) uniformly at random from \([\frac{1}{2}\tau', \frac{13}{24}\tau']\), compute two balls \(B_1=B_{G}^-(u,R),B_2=B_{G}^+(v,R)\) and add \(\delta^-(B_1)\cup \delta^+(B_2)\) to the cutset \(S\). We recursively apply this approach to each SCC of \(C\setminus S\) contained in \(B_1\cup B_2\). We halt the second stage when \(b_P(C)\leq 8\Delta\). Here, \(8\) is also a carefully chosen constant in order to bound the backward distance.

We show that a symmetrical property holds for this stage: Every SCC contained in \(B_1\cup B_2\) has a reduced backward distance, and every SCC disjoint from \(B_1\cup B_2\) has a reduced pathwidth. Let \(C'\) be an SCC of \(C\setminus S\) and \(P[C']=\langle x,\ldots, y\rangle\). First, we bound \(b_P(C')\) in the case where \(C'\subseteq B_1\cup B_2\). From Lemma [lem:twoball-fin], without loss of generality, let us assume \(C'\subseteq B_1\). The other case where \(C'\subseteq B_2\setminus B_1\) is analogous. From the argument of the first stage, \(P[C']\) is a subpath of \(P[C]\) and \(d_G(u,v) = f_P(C) \leq \Delta\). In addition, due to the triangle inequality, we have that: \[d_G(y,x) \stackrel{\triangle}\leq d_G(y, u) + d_G(u,x) \leq d_G(y,u) + d_G(u,v) \stackrel{B_1}\leq R + d_G(u,v) \leq R + \Delta \leq \frac{13}{24}\tau' + \Delta.\] Since the halting condition is \(\tau' \leq 8\Delta\), we have that \(\frac{13}{24}\tau' + \Delta \leq \frac{2}{3}\tau'\) throughout the second stage. Hence, the backward distance is reduced by \(2/3\).

Next, we bound the pathwidth of \(C'\) in the case where \(C'\) is disjoint from \(B_1\cup B_2\). The difference is that \(P[C]\) may not be fully contained in \(B_1\cup B_2\). For simplicity, let us assume that \(u\) and \(v\) are the leftmost and rightmost vertices of \(P\) in the path decomposition, respectively. That is, for two bags \(X_u\) and \(X_v\) containing \(u\) and \(v\) respectively, every bag \(X\) that intersects \(P\), lies between \(X_u\) and \(X_v\) in the path decomposition⁷. We consider a shortest \(v\)-\(u\) path \(P'\) of length \(\tau'\) in \(G\). Since \(R\geq \frac{1}{2}\tau'\), it is easy to check that \(P'\subseteq B_1\cup B_2\). Moreover, since \(P'\) intersects every bag \(X\) between \(X_u\) and \(X_v\), \(P'\) intersects every bag \(X\) that intersects \(P\). Since \(C'\) is disjoint from \(B_1\cup B_2\), it is disjoint from \(P'\) as well. Hence, for each bag \(X\) intersecting \(P\cap C'\), we have that: \[|C'\cap X| < |C'\cap X| + |P'\cap X| = |(C'\cup P')\cap X| \leq |C\cap X|.\] This establishes that \(\mathsf{pw}(C') < \mathsf{pw}(C)\), as desired. See Figure 3 (b) for an illustration.

3.2.0.3 Third stage: reducing the weak diameter.

Finally, the third stage serves as the base case. We are given a strongly connected subgraph \(C\) of \(H\) as input, where the two previous stages guarantee that \(f_P(C)\leq \Delta\) and \(b_P(C)\leq 8\Delta\). One might ask whether \(f_P(C), b_P(C) = O(\Delta)\) directly implies that the weak diameter of \(C\) is \(O(\Delta)\). This is not true in general. What we can guarantee is only the (bi-)distance between two endpoints of \(P[C]\), which does not necessarily bound the distance between every pair of vertices in \(C\). See Figure 4 for an illustration.

Let \(P[C]=\langle u,\ldots, v\rangle\). We compute two balls \(B_{G}^+(u, R_1)\) and \(B_{G}^-(u,R_2)\) around the same vertex \(u\), where we sample \(R_1,R_2\) uniformly at random from \([\Delta, 2\Delta]\) and \([9\Delta, 10\Delta]\), respectively. Then, we add \(\delta^+(B_1)\cup \delta^-(B_2)\) into the cutset \(S\). Every SCC contained in \(B_1\cap B_2\) has a small weak diameter, since for every pair of vertices in \(B_1\cap B_2\), we can draw a detour of length \(O(\Delta)\) through \(u\). In addition, it is straightforward to verify that \(P[C]\subset B_1\cap B_2\). Subsequently, every SCC disjoint from \(B_1\cap B_2\) has a reduced pathwidth. Due to Lemma [lem:twoball-fin] we conclude that every SCC of \(G\setminus S\) after the third stage either has a weak diameter of at most \(\Delta\) or a reduced pathwidth. This completes the proof sketch of Lemma 2.

3.2.0.4 Remark.

One may expect a logarithmic loss parameter of \(O(\log(\mathsf{ppw}(G)))\) as in [15]. However, our scissors carving framework differs from previous ball carving in the following sense. In previous work, once the interior of a ball was carved away, the resulting cluster became “safe", meaning that it was no longer affected by further ball carving steps. This allowed [15] to sample the radius from a (truncated) exponential distribution and utilize its (almost) memoryless property, ensuring them to bound the loss parameter by the logarithmic number of threateners.

In contrast, in our scissors carving, once we compute two balls that cover a shortest path, the interiors of these balls are conveyed to the next round. That is, each edge can be threatened multiple times regardless of whether it is inside a ball or not. Thus, the cut probability becomes linear in the number of threateners. We also remark that the same phenomenon is observed in the directed treewidth case [23].

4 Directed LDDs for Bounded-Pathwidth Directed Graphs↩︎

In this section, we prove Theorem [thm:ldd]. While we state our result in terms of pathwidth, we find it more convenient to use the notion of path partition-width (see Definition 3 below). This is a directed analogue of the (undirected) tree partition-width [44] for the directed graphs with small pathwidth.

To begin with, we apply an edge-preserving isometric embedding from a directed graph with bounded pathwidth into another directed graph with bounded path partition-width. Crucially, this embedding preserves the edge structure of the graph. This will allow us to lift an LDD of the embedded graph back to the original graph. Note that our embedding is not new. Filtser et al. [17] defined a similar embedding from (undirected) bounded treewidth graphs into graphs of bounded tree partition-width⁸ graphs. Although not stated explicitly, their embedding is also an edge-preserving isometric embedding.

While the ultimate goal is to design an LDD for directed graphs of bounded pathwidth, our construction algorithm is formally defined on graphs of bounded path partition-width. We remark that a similar approach was used by Filtser et al. [17] to compute an LDD for (undirected) graphs of bounded treewidth.

We show that there is an edge-preserving isometric embedding from graphs with bounded pathwidth into graphs with bounded path partition-width.

Crucially, an LDD of the embedded graph can be transferred back to the original graph without any additional loss.

Based on [lem:embed-LDD,lem:embed-width], it suffices to show the existence of \((O(k), \Delta)\)-LDD for the directed graphs with path partition-width at most \(k\). Throughout this section, we let \(G\) be a directed graph, and let \((\mathcal{P}, \mathcal{X}=\{X_1,X_2,\ldots, X_m\})\) be the path partition of \(G\) with width \(\mathsf{ppw}(G)\). If it is clear from the context, we slightly abuse the notation and simply denote the path partition \((\mathcal{P}, \mathcal{X})\) by \(\mathcal{P}\). Furthermore, we may assume that \(G\) is strongly connected as otherwise, we can independently execute our algorithm on each SCC of \(G\). For a subgraph \(H\) of \(G\), we define the induced path partition of \(H\) with respect to \(\mathcal{P}\) as \((\mathcal{P}, \{X_i\cap V(H)\mid X_i\in \mathcal{X}\})\), and denote it by \(\mathcal{P}[H]\). We denote the width of \(\mathcal{P}[H]\) by \(w(\mathcal{P}[H])\). Note that for every subgraph \(H\) of \(G\), \({\mathsf{w}(\mathcal{P}[H])}\leq {\mathsf{w}(\mathcal{P}[G])} = \mathsf{ppw}(G)\) trivially holds.

The remainder of this section is devoted to proving the following lemma.

Before proceeding to the main proof, we first establish the following auxiliary lemma, which will be useful throughout our analysis.

Next, we present a randomized recursive algorithm \(\textsf{Directed-LDD}\), which receives as input a directed graph \(G=(V,E,w)\), a path partition \(\mathcal{P}\) of \(G\), a strongly connected subgraph \(H\) of \(G\), and a parameter \(\Delta>0\). In addition, \(\textsf{Directed-LDD}\) computes a (randomized) cutset of \(H\) whose distribution induces a \((O({\mathsf{w}(\mathcal{P}[H])}), \Delta)\)-LDD of \(H\). See 5 for the pseudocode. The algorithm immediately terminates if \({\mathsf{w}(\mathcal{P}[H])}=0\), which implies that \(H\) is an empty subgraph. For the other case where \({\mathsf{w}(\mathcal{P}[H])}>0\), 5 calls Scissors-Carving algorithm⁹, whose function is summarized in the following lemma. We defer the detailed description of Scissors-Carving and the proof of Lemma [lem:reduce-pathwidth] to Sections 4.1 and 4.2, respectively.

Then, for each strongly connected component \(C\) of \(H\setminus S\) such that the weak diameter of \(C\) is greater than \(\Delta\), the algorithm executes a recursive call \(\textsf{Directed-LDD }(G,\mathcal{P},C,\Delta)\) to compute a random cutset \(S_C\) of \(C\). Finally, \(\textsf{Directed-LDD}\) returns the union of \(S\) and all cutsets \(S_C\) returned by the recursive calls. This completes the description of \(\textsf{Directed-LDD}\).

4.0.0.1 Analysis of \(\textsf{Directed-LDD}\).

In this part, we prove 3 assuming Lemma [lem:reduce-pathwidth]. Let \(S=\textsf{Directed-LDD}(G,\mathcal{P}, H, \Delta)\). First, we bound the weak diameter of every SCC in \(H\setminus S\).

Next, we analyze the edge-cut probability \(\Pr[e\in S]\) for an edge \(e\in E(H)\).

Finally, 3 follows from applying [lem:ldd-diameter,lem:ldd-prob] by taking \(H\leftarrow G\) and \(\Delta \leftarrow \frac{\Delta}{12}\).

4.1 Reducing path partition-width↩︎

In this section, we explain our key subroutine Scissors-Carving. To this end, we define some additional notation that will be used in this section. Recall that \(\mathcal{P}=(\mathcal{P}, \mathcal{X})\) consists of \(m\) bags \(X_1,X_2,\ldots X_m\). Let \(H\) be a strongly connected subgraph of \(G\). We say an index \(i\in [m]\) is a critical index of \(H\) if \(|V(H)\cap X_i|={\mathsf{w}(\mathcal{P}[H])}\). Equivalently, we refer to \(X_i\) as a critical bag of \(H\). Let \(\mathcal{C}(H)=\{j_1,j_2,\ldots, j_\ell\}\) be the set of critical indices of \(H\) such that \(1\leq j_1 <j_2<\ldots< j_\ell\leq m\).

We say a shortest \(u\)-\(v\) path \(P\) in \(G\) is a critical path with respect to \(H\) if \(u\in X_{j_1}\cap H\) and \(v\in X_{j_\ell}\cap H\). From the definition of a path partition, \(P\) intersects every bag \(X_t\) with \(j_1\leq t\leq j_\ell\). Hence, \(P\) intersects every critical bag of \(H\), which leads to the following observation.

Due to technical reasons, throughout the algorithm, we maintain a certain subsequence of the critical path \(P\), called a critical sequence, which is defined as follows. For each critical index \(j\) of \(H\), let \(v_j\in X_j\cap H\) be the vertex that appears earliest in \(P\) along the direction from \(u\) to \(v\). We may assume \(v=v_{j_\ell}\) as otherwise, we can take the \(u\)-\(v_{j_\ell}\) subpath of \(P\). Then, \(v_{j_1}, v_{j_2},\ldots, v_{j_\ell}\) are naturally ordered along the path \(P\). We call \(\langle v_{j_1},v_{j_2},\ldots v_{j_\ell}\rangle\) a critical sequence of \(H\) with respect to \(P\), and denote it by \(\bar P[H]\). Note that this critical sequence \(\bar P[H]\) is uniquely defined for a fixed \(H\) and \(P\). See Figure 6 (a) for an illustration. Since \(\bar P[H]\) intersects every critical bag of \(H\), we observe the following.

For a critical sequence \(\bar P=\langle u,\ldots, v\rangle\) of \(H\) with respect to \(P\), and a strongly connected subgraph \(C\) of \(H\), let \(x\) and \(y\) be the first and the last vertices of \(\bar P\cap C\), respectively. We define the surviving subsequence of \(\bar P\) with respect to \(C\), denoted by \(\bar P[C]\), as the consecutive subsequence of \(\bar P[H]\) that starts at \(x\) and ends at \(y\). Note that while \(\bar P[C]\) may not be fully contained in \(C\), the two endpoints \(x,y\) are contained in \(C\). See Figure 6 (b) for an illustration.

We define the forward disatnce and the backward distnace of \(C\) (with respect to \(P\)) as \(d_G(x,y)\) and \(d_G(y,x)\), respectively, and denote them by \(f_{\bar P}(C)\) and \(b_{\bar P}(C)\), respectively. Note that we analyze these distances with respect to the shortest paths in the original graph \(G\), rather than the subgraph \(C\). This is sufficient for our purpose since our goal is to bound the weak diameter of each SCC. We show that \(\bar P[C]\) plays the role of a “critical" sequence for \(C\). That is, the removal of \(\bar P[C]\) from \(C\) reduces its path partition-width. Based on the following lemma, in the remainder of this section, we slightly abuse the notation and refer to \(\bar P[C]\) as a critical sequence of \(C\).

The following observation is obvious from the definition of the critical path and critical sequence, but it is crucial for our analysis.

4.1.0.1 Algorithm.

Then, we describe our algorithm \(\textsf{Scissors-Carving }(G, \mathcal{P}, H, \bar P, \Delta)\). See 7 for the pseudocode. It receives as input a directed graph \(G\), a path partition \(\mathcal{P}\) of \(G\), a strongly connected subgraph \(H\) of \(G\), a critical sequence \(\bar P\) of \(H\) with respect to \(P\), and a parameter \(\Delta>0\). Moreover, it outputs a random cutset \(S\) of \(E(H)\) such that for every SCC \(C\) of \(H\setminus S\), either \({\mathsf{w}(\mathcal{P}[C])}<{\mathsf{w}(\mathcal{P}[H])}\) or the weak diameter of \(C\) is at most \(12\Delta\).

The algorithm is a recursive procedure with respect to \(H\) and \(\bar P\). Depending on the forward distance \(f_{\bar P}(H)\) and the backward distance \(b_{\bar P}(H)\) of \(H\), the procedure proceeds in one of three stages. The first stage is executed when \(f_{\bar P}(H)=\tau >\Delta\). At this stage, we sample a random radius \(R\) uniformly at random from \([\frac{1}{2}\tau, \frac{2}{3}\tau]\). Then, we compute two balls, an out-ball \(B_1=B_{G}^+(u,R)\) and an in-ball \(B_2=B_{G}^-(v,R)\), compute a set \(S_1\) of boundary edges of \(B_1\) and \(B_2\) that intersect \(H\), i.e., \(S_1=H\cap (\delta^+(B_1)\cup \delta^-(B_2))\). Next, we recursively apply the algorithm to each SCC \(C\) of \(H\setminus S_1\) which is fully contained in \(B_1\cup B_2\). In addition, we pass the surviving subsequence \(\bar P[C]\) as the critical sequence to the next recursive call. This completes the description of the first stage.

The second stage is executed when \(f_{\bar P}(H) \leq \Delta\) and \(b_{\bar P}(H)=\tau' > 8\Delta\). At this stage, we sample a random radius \(R\) uniformly at random from \([\frac{1}{2}\tau', \frac{13}{24}\tau']\). Then, we compute two balls, an in-ball \(B_1=B_{G}^-(u,R)\) and an out-ball \(B_2=B_{G}^+(v,R)\), compute a set \(S_1\) of boundary edges of \(B_1\) and \(B_2\) that intersect \(H\), i.e., \(S_1=H\cap (\delta^-(B_1)\cup \delta^+(B_2))\). Next, we recursively apply the algorithm to each SCC of \(H\setminus S_1\) which is fully contained in \(B_1\cup B_2\). In addition, we pass the surviving subsequence \(\bar P[C]\) to the next recursive call. This completes the description of the second stage.

The third stage is executed when \(f_{\bar P}(H) \leq \Delta\) and \(b_{\bar P}(H) \leq 8\Delta\). We sample two random radii \(R_1,R_2\) uniformly at random from \([\Delta, 2\Delta]\) and \([9\Delta, 10\Delta]\), respectively. Then, we compute two balls, an out-ball \(B_1=B_{G}^+(u,R_1)\) and an in-ball \(B_2=B_{G}^-(v,R_2)\), return \(H\cap (\delta^+(B_1)\cup \delta^-(B_2))\).

Finally, we provide a crucial technical remark: As an extreme case, our algorithm immediately returns the empty set whenever \(\bar P[C]\) is empty (lines 1-2). Intuitively, due to Lemma 6, \(\bar P[C]=\emptyset\) implies \({\mathsf{w}(\mathcal{P}[C])}<{\mathsf{w}(\mathcal{P}[H])}\), which satisfies our structural goal.

4.2 Analysis↩︎

In this section, we show that our algorithm \(\textsf{Scissors-Carving}\) satisfies the condition of Lemma [lem:reduce-pathwidth]. As we discussed in the previous section, this concludes the proof of Lemma 3 and therefore Theorem [thm:ldd]. As a base case, the lemma is obvious when \({\mathsf{w}(\mathcal{P}[H])}=0\), which implies \(H=\emptyset\) and \(S=\emptyset\). Hence, let us assume \({\mathsf{w}(\mathcal{P}[H])}>0\).

Before we prove Lemma [lem:reduce-pathwidth], we prove two technical lemmas. First, we verify the exceptional case (lines 1 and 2) such that if \(\bar P\) is the empty set, then \({\mathsf{w}(\mathcal{P}[H])}\) is reduced compared to that of the parent instance.

Next, we prove the technical lemma that settles the stages of the recursion tree.

Now, we are ready to prove Lemma [lem:reduce-pathwidth]. We prove the two items of Lemma [lem:reduce-pathwidth] separately, through [lem:gen-correct,lem:gen-prob], respectively.

Next, we bound the edge-cut probability.

5 Directed Sparsest Cut Problem for Bounded-Treewidth Digraphs↩︎

In this section, we study the directed non-bipartite sparsest cut problem and its LP relaxation, focusing on the integrality gap.

5.0.0.1 Directed non-bipartite sparsest cut problem.

Let \(G\) be an edge-weighted directed graph with capacities \(c(e)\) for all edges \(e\in E(G)\). Let \(T\) be a set of terminal pairs \(T=\{(s_1,t_1),(s_2,t_2),\ldots, (s_\ell,t_\ell)\}\) of vertices. For each \(i\in [\ell]\), let \(\textsf{dem}(i)\) be a non-negative real number, called the demand, for the terminal pair \((s_i, t_i)\). A cut \(S\) of \(G\) is a subset \(S\subseteq E(G)\) of edges. For a cut \(S\), let \(c(S):=\sum_{e\in S} c(e)\) be the capacity of \(S\). Let \(I_S\subseteq [\ell]\) be the set of integers \(i\) such that every \(s_i\)-\(t_i\) path (not necessarily a shortest path) contains at least one edge of \(S\). We define the demand of \(S\) by \(\textsf{dem}(S):=\sum_{i\in I_S}\textsf{dem}(i)\). The sparsity of \(S\) is defined by \(c(S)/\textsf{dem}(S)\). The goal of the directed non-bipartite sparsest cut problem is to find a cut \(S\) that minimizes the sparsity.

The integrality gap of the LP relaxation for this problem is called the directed multi-commodity flow cut-gap. For non-uniform demands, Hajiaghayi and Räcke showed an \(O(\sqrt n)\) upper bound for the flow-cut gap [41]. This has been improved to \(\tilde{O}(n^{11/23})\) by Agarwal, Alon, and Charikar [42]. On the other hand, the current best-known lower bound is due to Chuzhoy and Khanna [39], who showed a \(\tilde{\Omega}(n^{1/7})\) lower bound for the flow-cut gap.

Mémoli, Sidiropoulos, and Sridhar [23] showed that every \(n\)-vertex directed graph with treewidth \(\mathsf{tw}\) admits an \((O(\mathsf{tw}\log n), \Delta)\)-quasipartition for every parameter \(\Delta>0\). They used their quasipartition construction to show that the flow-cut gap is \(O(\mathsf{tw}\log^2 n)\) for such graphs. We now present the main result of this section.

This improves upon the \(\log n\) factor of the previously best-known bound from [23]. At a high level, we follow the procedure of [23], but provide a better analysis of their approach.

We briefly explain the approach of [23], which proved that the integrality gap is \(O(\mathsf{tw}\log^2 n)\). First, they showed that for every \(\Delta>0\), \(G\) admits a \((\beta, \Delta)\)-quasipartition with \(\beta=O(\mathsf{tw}\log n)\). Using this quasipartition, they proved that the quasimetric space with respect to the shortest path metric of \(G\) can be embedded into a convex combination of \(0\)-\(1\) quasimetric spaces (see Definition 5 and Lemma 11) with a distortion of \(O(\beta \log n)=O(\mathsf{tw}\log^2 n)\). Finally, by using the known relationship between the convex combination of \(0\)-\(1\) quasimetric spaces and the integrality gap for the directed non-bipartite sparsest cut problem [26], they showed that the integrality gap is \(O(\mathsf{tw}\log^2 n)\).

5.1 Deep dive into the approach of [23]↩︎

In this section, we carefully review the previous approach of [23] step-by-step, and then describe our improvement. First, we analyze the \((O(\mathsf{tw}\log n), \Delta))\)-quasipartition construction of [23].

The construction is achieved by a recursive approach. Given a tree decomposition \((T, \{B_t\}_{t\in T})\), we choose a central bag \(B_t\), meaning that each subgraph of \(G\) induced by the maximal subtree of \(T\setminus \{t\}\) contains at most \(\frac{2}{3} |V(G)|\) vertices. We then sample a radius \(R\) uniformly at random from \([\frac{1}{2}\Delta, \Delta]\). For each vertex \(v\in B_t\), we compute two balls, an out-ball \(B_1:=B_{G}^+(v, R)\) and an in-ball \(B_2:=B_{G}^-(v,R)\), add \(\delta^+(B_1) \cup \delta^-(B_2)\) to the cutset \(S\), and recursively apply this procedure to each subgraph induced by the connected components of \(T\setminus \{t\}\). Note that any \(x\)-\(y\) path intersecting \(v\) such that \(d_G(x,y)>2\Delta\) must intersect \(\delta^+(B_1) \cup \delta^-(B_2)\) because, due to the triangle inequality, we have that: \[\max(d_G(x,v), d_G(v,y)) \geq \frac{1}{2}(d_G(x,v) + d_G(v,y)) \geq \frac{1}{2}d_G(x,y) > \Delta.\] This implies that for every path (not necessarily a shortest path) connecting two vertices from different trees of \(T\setminus \{t\}\), either it intersects \(S\), or it satisfies \(d_G(x,y)\leq 2\Delta\). This justifies the recursion: after the recursion terminates, we can conclude that for every \(x\)-\(y\) path in \(G\setminus S\), we have \(d_G(x,y) \leq 2\Delta\).

We briefly analyze the probability that a single edge belongs to the cutset, i.e., \(\Pr[e\in S]\). Since \(B_t\) plays the role of a separator, each edge \(e\) is affected by at most one instance at each level of the recursion. Moreover, since \(B_t\) is a central bag, the recursion depth is \(O(\log n)\). At a single level, \(e\) is affected by at most \(2|B_t|=2(\mathsf{tw}+1)\) balls. Hence, due to the union bound on the probability, \[\begin{align} \Pr[e\in S]\leq O(\log n) \cdot O(\mathsf{tw}) \cdot \frac{w(e)}{\Delta} = O(\mathsf{tw}\log n) \cdot \frac{w(e)}{\Delta}. \end{align}\] This completes the analysis of the construction of the \((O(\mathsf{tw}\log n), \Delta)\)-quasipartition.

Next, we analyze the second part which gives an embedding of a quasimetric space into a convex combination of \(0\)-\(1\) quasimetric spaces (Lemma 11). For simplicity, suppose every edge weight of \(G\) is a positive integer and \(\max_{u,v}\{d_G(u,v)\}=2^k\) for some integer \(k=O(\log n)\). Then, for each scale \(i\in \{0,1,\ldots, k\}\), we compute a \((\beta, 2^i)\)-quasipartition \(\mathcal{D}_i\) of \(G\) using the above procedure. Importantly, each quasipartition \(\mathcal{D}_i\) is a distribution over a cutset \(S_i\subset E(G)\). Using these, we compute a random quasipartition of \(G\) according to the following procedure. Let \(c=2^{k+1}-1\). First, we select one \(\mathcal{D}_i\) among \(\{\mathcal{D}_0, \mathcal{D}_1, \ldots, \mathcal{D}_k\}\) with probability \(\frac{2^i}{c}\). Then, we pick a random cutset \(S\) from the chosen \(\mathcal{D}_i\). This yields a distribution \(\mathcal{D}\) over the cutsets.

Next, for each (random) cutset \(S\) sampled from \(\mathcal{D}\), we define a \(0\)-\(1\) quasimetric space \((V(G), d_S)\) where \(d_S(x,y)=0\) if there is an \(x\)-\(y\) path in \(G\setminus S\) and \(d_S(x,y)=1\) otherwise. This yields a distribution over \(0\)-\(1\) quasimetric spaces which can be expressed as a convex combination of \(0\)-\(1\) quasimetric spaces. Let \((V(G), d^*)\) be the resulting quasimetric space. Then, we have \[\begin{align} d^*(u,v) &= \Pr_{S\sim \mathcal{D}}[\text{there is no } u\text{-}v \text{ path in } G\setminus S] \tag{5} \\ &= \sum_{i=0}^k \frac{2^i}{c} \Pr_{S_i\sim \mathcal{D}_i}[\text{there is no } u\text{-}v \text{ path in } G\setminus S_i] \\ &\leq \sum_{i=0}^k \frac{2^i}{c} \beta \cdot\frac{d_G(u,v)}{2^i} \\ &= \frac{(k+1)\cdot \beta}{c} d_G(u,v). \tag{6} \end{align}\] For the other direction, [23] showed that \(d^*(u,v)\geq \frac{1}{c} \cdot d_G(u,v)\), yielding a distortion of \((k+1)\beta = O(\beta \log n)\).

5.2 Removing the extra \(O(\log n)\)actor from Lemma 11↩︎

In this section, we provide a better analysis that improves the distortion by a factor of \(O(\log n)\). We focus on the \(O(\log n)\) additional factor arising from Lemma 11. This factor comes from combining the distortion contributions across \(O(\log n)\) scales, where each scale contributes independently.

Our idea is to avoid this factor by considering all scales simultaneously. To formalize this idea, we revisit the construction in Section 5.1. For a fixed edge \(e=(x,y)\) and a scale \(i\), we compute a set \(V(e)\subset V(G)\) of size \(O(\mathsf{tw}\log n)\) as follows. For each recursive instance that contains \(e\), we add the vertices in the central bag to \(V(e)\). Since \(e\) is contained in \(O(\log n)\) instances (from the construction in Section 5.1), we have \(|V(e)|=O(\mathsf{tw}\log n)\). Note that \(V(e)\) is independent of the scale \(i\).

Now, we reinterpret the construction in Section 5.1 as follows. For every scale \(i\), we sample a radius \(R_i\) uniformly at random from \([2^{i-1},2^i]\), and we add \(e\) to the cutset \(S_i\) if \(e\) is contained in one of the boundaries of the (in- and out-) balls of radius \(R_i\in [2^{i-1}, 2^{i}]\) centered at some vertex in \(V(e)\). This defines the quasipartition \(\mathcal{D}_i\) over the cutsets. We prove the following useful lemma.

Using exactly the same argument, we can show the following lemma.

For an edge \(e\) and a vertex \(z\in V(e)\), let \(I(z,e)\) be the set of indices \(i\) such that \(\Pr[e\in \delta^+(B^+_G(z, R_i)) \cup \delta^-(B^-_G(z, R_i))]>0\) and \(2^i > w(e)\). Due to [lem:quasipartition-correct1,lem:quasipartition-correct2], we have that: \[\begin{align} \label{eq:18-13} |I(z,e)|=O(1). \end{align}\tag{7}\]

Let \(i\in I(z,e)\). Since \(R_i\) is chosen uniformly at random from \([2^{i-1}, 2^i]\), we have that: \[\begin{align} \label{eq:18-14} \Pr_{R_i}[(d_G(z,x) \leq R_i) \cap (d_G(z, y) > R_i))] \leq O(1)\cdot \frac{w(e)}{2^i}. \end{align}\tag{8}\]

Next, we analyze the probability \(q:=\Pr_{S\sim \mathcal{D}}[\text{there is no } u\text{-}v \text{ path in } G\setminus S]\). Our argument closely follows that of [23]. Let \(\mathcal{P}=\{p_1,p_2,\ldots, p_\ell\}\) be the set of all \(u\)-\(v\) paths in \(G\). For every \(m\in [\ell]\), let \(X_m\) be the event that \(p_m\) contains at least one edge in \(S\). Then, \(q= \Pr[X_1\wedge X_2\wedge \ldots \wedge X_\ell] \leq \Pr[X_m]\) for all \(m\in [\ell]\). Now let us consider a fixed shortest path \(p_m=\langle u=v_1,v_2,\ldots, v_t=v\rangle\in \mathcal{P}\). For every \(j\in [t-1]\), let \(Y_j\) be the event that \((v_j, v_{j+1})\in S\). Then, \(\Pr[X_m] =\Pr[Y_1\vee Y_2\vee\ldots \vee Y_{t-1}]\leq \sum_{j}\Pr[Y_j]\) due to the union bound of probability. In addition, let \(e_j=(v_j, v_{j+1})\). Then, \[\begin{align} \Pr[Y_j]=\Pr[e_j\in S] &= \sum_{i=0}^k \frac{2^i}{c} \cdot \Pr[e_j\in S_i] \\&\leq \sum_{i=0}^k \frac{2^i}{c} \cdot \sum_{z\in V(e_j)} \Pr_{R_i}[(d_G(z,v_j) \leq R_i) \cap (d_G(z, v_{j+1}) > R_i))] \\&= \sum_{z\in V(e_j)} \sum_{i=0}^k \frac{2^i}{c} \cdot \Pr_{R_i}[(d_G(z,v_j) \leq R_i) \cap (d_G(z, v_{j+1}) > R_i))]. \label{eq:18-12} \end{align}\tag{9}\] We analyze the inner summation over \(i\) as follows. We split the sum over \(k\) scales at \(i=\lfloor \log w(e_j)\rfloor\). Since \(I(z,e_j)\subseteq \{i:2^i>w(e_j)\}\), we can bound each part separately. Let \(P_{i,z}:=\Pr_{R_i}[(d_G(z,v_j) \leq R_i) \cap (d_G(z, v_{j+1}) > R_i))]\). Then, \[\begin{align} &\sum_{i=0}^k \frac{2^i}{c} \cdot \Pr_{R_i}[(d_G(z,v_j) \leq R_i) \cap (d_G(z, v_{j+1}) > R_i))] = \sum_{i=0}^k \frac{2^i}{c} \cdot P_{i,z} \\&=\sum_{i=0}^{\lfloor\log w(e_j) \rfloor} \frac{2^i}{c} \cdot P_{i,z} + \sum_{i=\lfloor \log w(e_j)\rfloor +1}^k \frac{2^i}{c} \cdot P_{i,z} \\&\leq \sum_{i=0}^{\lfloor \log w(e_j) \rfloor} \frac{2^i}{c}+ \sum_{i\in I(z, e_j)} \frac{2^i}{c}\cdot P_{i,z} \\&\stackrel{\eqref{eq:18-14}}\leq \frac{2\cdot w(e_j)}{c} + \sum_{i\in I(z, e_j)} \frac{2^i}{c} \cdot (O(1)\cdot \frac{w(e_j)}{2^i}) \stackrel{\eqref{eq:18-13}}= O(1)\cdot \frac{w(e_j)}{c}. \end{align}\] Returning to 9 , we obtain: \[\begin{align} \Pr[Y_j] &\leq \sum_{z\in V(e_j)} \sum_{i=0}^k \frac{2^i}{c} \cdot \Pr_{R_i}[(d_G(z,v_j) \leq R_i) \cap (d_G(z, v_{j+1}) > R_i))]. \\&\leq \sum_{z\in V(e_j)} O(1)\cdot \frac{w(e_j)}{c}=O(|V(e_j)|)\cdot \frac{w(e_j)}{c} = O(\mathsf{tw}\log n) \cdot \frac{w(e_j)}{c}. \end{align}\] Here, the last equality follows from the fact that \(|V(e)|=O(\mathsf{tw}\log n)\) for every edge \(e\). Since \(p_m\) is a shortest \(u\)-\(v\) path in \(G\), we have that: \[\begin{align} \label{eq:18-15} q \leq \Pr[X_m] \leq \sum_j \Pr[Y_j] \leq O(\mathsf{tw}\log n)\cdot \sum_j \frac{w(e_j)}{c} = O(\mathsf{tw}\log n)\cdot \frac{d_G(u, v)}{c}. \end{align}\tag{10}\] Putting everything together, we show that the probability bound from Eq.@eq:eq:5-16 to Eq.@eq:eq:5-20 can be improved as follows: \[\begin{align} d^*(u,v) = \Pr_{S\sim \mathcal{D}}[\text{there is no } u\text{-}v \text{ path in } G\setminus S] \stackrel{\eqref{eq:18-15}}\leq O(\mathsf{tw}\log n) \cdot \frac{d_G(u,v)}{c}. \end{align}\] This confirms the improved distortion guarantee for the algorithm of [23].

5.2.0.1 Remark.

In this section, we only analyzed the case where every edge weight is an integer and bounded by \(\text{poly}(n)\). However, our idea can be lifted to the general case as well: the problematic distortion loss comes from the scales that are much larger than \(w(e)\). In [23], this issue was addressed by introducing a so-called forced quasipartition. Roughly speaking, in a forced quasipartition, it is guaranteed that \(\Pr[e\in S]\) for a cutset \(S\) at scale \(i\) becomes zero when \(\frac{2^i}{w(e)} \geq n\) (assuming that \(n\) is power of two). In this way, they bounded their distortion by summing up \(O(\log n)\) scales \(i\) from \(\lfloor \log w(e) \rfloor\) to \(\lfloor \log (n\cdot w(e)) \rfloor \leq \lfloor \log w(e)\rfloor+\log n\).

In our argument, rather than considering the fixed scales between \(\lfloor \log w(e)\rfloor\) and \(\lfloor \log w(e) \rfloor+\log n\), we consider the probability \(\Pr_{R_i}[e\in \delta^+(B^+_G(z, R_i))\cup \delta^-(B^-_G(z, R_i))]\) for every \(z\in V(e)\), which is nonzero for only \(|I(z,e)|=O(1)\) scales. Our \(O(\mathsf{tw}\log n)\) distortion factor is derived solely from the fact that \(|V(e)| = O(\mathsf{tw}\log n)\) for every edge \(e\). In this way, we can remove the bounded weights assumption and conclude the following lemma.

By applying this improved bound to the reduction to the integrality gap of the sparsest cut problem [26], we obtain the main result of this section.

References↩︎

---

1. Email: shinwoo.an@biu.ac.il. This work was supported by the Isreal Science Foundation grant \(\#\)​1042/22, Israel Science Foundation grant \(\#\)​800/22, and US-Israel Binational Science Foundation Grant \(\#\)​2022/131.↩︎

2. Email: arnold.filtser@biu.ac.il. This work was supported by the Isreal Science Foundation grant \(\#\)​1042/22.↩︎

3. See Section 3.2 for more details.↩︎

4. We defer the definitions of an in-ball and an out-ball to Section 3.2↩︎

5. From [def:ldd,def:quasi], it is easy to check that every \((\beta,\Delta)\)-quasipartition is a \((\beta,\Delta)\)-LDD.↩︎

6. Here, we give an informal statement in order to hide several technical terms behind it. See Lemma [lem:reduce-pathwidth] for details.↩︎

7. Indeed, we can guarantee this assumption by carefully taking certain subpaths in each recursion step. See Section 4 for details.↩︎

8. Tree partition can be viewed as a natural generalization of path partition, in the same way that tree decomposition generalizes path decomposition.↩︎

9. The algorithm receives \(\bar P\) as an additional input parameter, where \(\bar P\) is a sequence of vertices in \(G\) satisfying certain conditions. We provide the details of \(\bar P\) in Section 4.1.↩︎