# New Safe Screening Rule for Fast Optimal Transport on Tree, Cycle and Cactus Graphs

Thu-Le Tran, Trang Ngo, Thanh-Tung Nguyen, Duy Nguyen, Ngan Nguyen, Kien Trung Nguyen

<figure><img src="image_1.png" /></figure>

## To cite this version:

Thu-Le Tran, Trang Ngo, Thanh-Tung Nguyen, Duy Nguyen, Ngan Nguyen, et al., New Safe Screening Rule for Fast Optimal Transport on Tree, Cycle and Cactus Graphs. 2026. hal-05511202

HAL Id: hal-05511202

https://hal.science/hal-05511202v1

Preprint submitted on 14 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# New Safe Screening Rule for Fast Optimal Transport on Tree, Cycle and Cactus Graphs

Thu-Le Tran¹*, Trang Ngo², Thanh-Tung Nguyen³,
Duy Nguyen¹, Ngan Nguyen¹, and Kien Trung Nguyen¹

¹Can Tho University, Can Tho, Vietnam

²Université Sorbonne Paris Nord, 93430 Villetaneuse, France

³Université Gustave Eiffel, 77420 Champs-sur-Marne, France

*Corresponding author ttle@ctu.edu.vn

February 14, 2026

## Abstract

Existing approaches to discrete balanced Optimal Transport (OT) face some important challenges. While the optimal transport problem can be solved in polynomial time on Euclidean spaces and graphs, the best known strongly polynomial algorithms require superlinear time complexity. Recent methods, Sliced-OT and Tree-Sliced OT, reduce this time complexity by approximating data points on Euclidean spaces using simple graphs such as paths and trees, where closed-form expressions for OT enable more efficient computations. However, these graph structures are too simple and cannot capture topological features such as loops.

In this work, we address both limitations by studying OT on simple cactus graphs, a class of graphs with loops that includes trees and cycles as special cases. Our main technical tool is a new safe screening rule, inspired by sparse optimization, for identifying zero entries in the OT plan on graphs. This rule allows us to characterize the structure of OT on graphs and leads to efficient computational methods. First, it provides a purely combinatorial proof of the closed-form expression for OT on trees, previously derived using Kantorovich duality theory. Second, it allows OT on a single cycle to be reformulated as a weighted median problem on a line, enabling an efficient solving method. Finally, we derive a decomposition formula for OT on cactus graphs by reducing the problem to computations on tree and cycle components. All the results show that OT on cactus graphs can be computed in linear time.

**Keywords:** Optimal Transport, Safe Screening, Graph, Path, Tree, Cycle, Cactus

## 1 Introduction

*Optimal Transport (OT)* is a powerful framework for comparing probability distributions and has become a central tool in modern data science. Originally introduced by Gaspard Monge and later rigorously formulated by Leonid Kantorovich, OT provides a principled way to quantify the cost of transporting mass between distributions. The OT distance is known under different names across domains: it is referred to as the *Earth Mover's Distance* in computer vision [Rubner et al., 2000], and as the *Wasserstein distance* in generative modeling [Arjovsky et al., 2017]. Its flexibility has led to numerous successful applications. Foundational and computational aspects of OT are presented in [Santambrogio, 2015, Peyré et al., 2019, Villani, 2021].

OT provides a mathematical framework for comparing two probability measures—typically interpreted as supply and demand distributions—defined over a metric space. The problem is called *discrete* if both measures are discrete, i.e., finite (or countable) sums of Dirac masses. It is called *continuous*
when both measures are absolutely continuous with respect to the Lebesgue measure and admit densities. The case where one measure is discrete and the other is continuous is referred to as *semi-discrete*. A *transport plan* describes how mass is transferred from supply to demand locations, and the total cost is computed using a given ground distance.

The classical formulation imposes strict *mass conservation*: all supply must be completely transported, and all demand must be exactly satisfied. This gives rise to the so-called *balanced OT* problem. However, in practical applications, such exact matching can be too rigid—especially in the presence of noise, outliers, or missing mass. To address this, various *unbalanced OT* models have been developed by relaxing the marginal constraints using penalty terms. These include *joint penalties* that measure the discrepancy between the marginals and the transport plan [Cuturi, 2013], as well as *marginal penalties* based on divergence terms [Chizat et al., 2016].

In this work, we focus on the *discrete balanced OT* setting, where both supply and demand are supported on fixed finite locations and have equal total mass. In this case, the transport plan is represented by a matrix that satisfies exact marginal constraints, and the cost is defined by a ground distance between locations. This setting is particularly appealing from both theoretical and algorithmic perspectives: it admits an elegant geometric interpretation of moving mass from supply to demand, enabling combinatorial analysis; and its formulation as a linear program allows the well-known simplex method or the scalable regularized solvers. For these reasons, we restrict our attention to the discrete balanced OT framework throughout this work.

However, computing OT faces two significant challenges in large-scale settings: (i) the high computational cost due to the large number of data points, and (ii) the curse of dimensionality when data lie in high-dimensional spaces. The first challenge stems from the massive number of data points required, particularly when working with images, text, or discretized continuous distributions. For instance, the OT problem on graphs can be formulated as a minimum cost flow problem [Essid and Solomon, 2018], solvable in a superlinear time, which is $O(n \log(n(m + n \log n)))$ where $n$ is the number of vertices and $m$ is the number of edges, using Orlin's algorithm [Orlin, 1988]. Alternatively, the well-known Sinkhorn algorithm, reintroduced in [Cuturi, 2013], iteratively solves the entropically regularized optimal transport problem and achieves an $O(n^2)$ time complexity per iteration. Nevertheless, both approaches remain computationally expensive for large datasets. The second challenge arises from the high dimensionality of data, which leads to the well-known "curse of dimensionality", see e.g., [Zhang et al., 2023]. In high-dimensional settings, estimating the Wasserstein distance and OT plans becomes increasingly challenging due to the curse of dimensionality. Specifically, the empirical estimates tend to converge very slowly to their true values as dimensionality increases. However, recent research has shown that if the two distributions differ primarily along a low-dimensional subspace, then projecting the data onto this informative subspace can greatly enhance the estimation accuracy. This highlights the importance of dimensionality reduction techniques in tackling high-dimensional OT problems [Zhang et al., 2023].

To accelerate the computation of OT, several research directions have been explored. Among them are the use of graphs to approximate the geometry of data points, and the application of safe screening techniques to reduce problem size in penalized formulations, both of which enable more efficient solvers.

In the first line of research, the supply and demand locations are approximated using simple graph structures. This approach offers two main benefits: it reduces the number of data points and maps high-dimensional data into simpler graph representations, which may help mitigate the curse of dimensionality. In this line of work, sliced OT [Bonneel and Coeurjolly, 2019] is a widely used method. It projects high-dimensional data onto lines and solves the OT problem in one dimension. For the balanced case, 1D OT admits a closed-form solution, allowing linear-time computation when locations of supply and demand are sorted. For unbalanced OT, an iterative strategy based on repeated balanced 1D OT solves the problem efficiently [Séjourné et al., 2022]. However, using lines is limited in capturing the geometry of data structures. To overcome this, tree-sliced OT [Le et al., 2019] replaces lines with tree graphs. The main advantage of this method is that balanced OT on trees also admits closed-form solutions, enabling linear-time computation [Le et al., 2019]. Examples of such structures include cluster-based trees [Le et al., 2019] and quadtrees [Indyk, 2003]. From a theoretical
viewpoint, it has been shown that OT on $R^n$ can be approximated using tree metrics [Sato et al., 2020]. Interestingly, several unbalanced OT models can also be solved efficiently on trees, such as the Kantorovich-Rubinstein distance [Sato et al., 2020], entropy-regularized partial OT [Le and Nguyen, 2021], and Sobolev OT [Le et al., 2022].

However, paths and trees are insufficient for representing complex data structures that contain loops. In particular, OT on important graph classes such as cycles has received limited attention. To the best of our knowledge, the only existing study is by Delon et al. [2010], which shows that OT on cycles can be approximately solved in $O(n \log(1/\epsilon))$ time, where $\epsilon$ denotes the desired precision.

Another recent direction for accelerating large-scale machine learning problems is the use of *safe screening*, a technique that safely eliminates the irrelevant features or samples in the training data with effecting the performance of the training model. In the language of optimization, it is equivalent to reducing the useless variables or constraints without affecting the optimal solutions. In regression and classification tasks, the input data are typically organized as a matrix, where columns represent features and rows represent samples. Existing safe screening methods exploit the sparsity inherent in models such as Lasso and Support Vector Machines (SVM) to eliminate nonessential features or samples, thereby reducing the problem's dimensionality or number of constraints.

Safe screening methods can be categorized in various ways. Possible classification criteria include their underlying principles or implementation strategies. Typical screening methods include both safe and unsafe approaches, with the latter encompassing strong screening [Tibshirani et al., 2012] and sure screening [Fan and Lv, 2018], which eliminate variables based on heuristics or probabilistic guarantees. Safe screening methods typically target sparse optimization problems, whereas squeezing [Elvira and Herzet, 2020] and relaxing [Guyard et al., 2022] techniques are designed for non-sparse settings. Regarding the sparse machine learning models, methods can be divided into three main categories: feature screening [Ghaoui et al., 2010], sample screening [Ogawa et al., 2013], and combined approaches [Shibagaki et al., 2016]. For a recent overview of safe screening methods, see Ndiaye [2018], Le Tran [2023].

In terms of implementation, safe screening methods can be classified according to their integration strategy: static screening, applied before solving the problem [Ghaoui et al., 2010]; dynamic screening, applied during the solver's iterations [Bonnefoy et al., 2014]; and sequential screening, applied across a sequence of problems with varying hyperparameters [Wang et al., 2013]. A central idea in many safe screening methods is the construction of a *safe region*—a set that is guaranteed to contain an optimal solution. Based on the geometry of these regions, methods can be categorized into ball and dome types. The dome region, defined as the intersection of a ball and a half-space, was first introduced in [Xiang and Ramadge, 2012] and later generalized in [Yamada and Yamada, 2021] and [Tran et al., 2022]. Nevertheless, most state-of-the-art safe screening methods rely on ball regions. Among them, the GAP ball [Fercq et al., 2015] is widely used, with a recent improvement known as the dynamic EDPP ball [Yamada and Yamada, 2021]. Both are unified under a general framework called the RYU ball [Tran et al., 2023].

Several studies have extended safe screening techniques to accelerate penalized OT problems. Here penalized OT problems are derived from the balanced OT and add penalty function to quantify the unbalancing the mass constraints. For entropy-regularized OT solved via the Sinkhorn algorithm, a safe screening approach has been developed for the dual problem [Alaya et al., 2019]. In the case of $L^2$ and Kullback-Leibler regularization, Lasso-based safe screening methods have been applied by reformulating the OT problem into a Lasso-like form [Su et al., 2023]. However, to the best of our knowledge, no safe screening rule has yet been proposed for unregularized OT.

In this paper, we develop a new safe screening technique for accelerating discrete balanced OT on *simple cactus* graphs. A simple cactus is a connected graph where any two cycles are vertex-disjoint; see e.g., Figure 1a. When all cycles shrink to single vertices, the graph becomes a tree, called the *bridge tree*; see Figure 1b. Thus, the simple cactus generalizes both trees and single cycles.

Note that, there is a *general cactus*, which permits any two cycles to share at most one vertex, see e.g., [Nguyen et al., 2017]. Here, we focus on simple cacti rather than general cacti due to technical challenges that arise from overlapping cycles. In contrast, simple cactus graphs ensure a clear
<figure><img src="image_3.png" /><figcaption>Figure 1: A simple cactus (top) and its bridge tree (bottom)</figcaption></figure>

separation between cycles, enabling structural decompositions that are more amenable to efficient computation. Despite this restriction, simple cactus graphs still form a broad class that includes many important cases of interest, such as trees, single cycles, and their combinations. Thus, they represent a natural and meaningful next step in extending OT computation beyond tree structures.

To achieve the goal, we introduce a new safe screening method for OT on graphs. Our screening technique identifies zero entries in the optimal transport plans. In principle, it functions similarly to feature elimination or variable screening methods in the literature; see e.g., [Su et al., 2023]. However, the key difference is that it is not designed to be used alongside a specific algorithm. Instead, we use it as a structural characterization tool to decompose the OT problem on a graph into smaller, more tractable subgraphs. This approach enables exact, linear-time computation on simple cactus graphs, including paths, trees, and cycles.

This paper makes four main contributions, each offering both theoretical insights and practical advancements:

* First, we introduce a novel safe screening rule for identifying zero entries in the OT plan on graphs using a necessary optimality condition. This reveals structural properties of the OT plan, enabling problem simplification and more efficient solution methods.

* Second, our screening rule allows for a purely combinatorial derivation of the closed-form solution for OT on trees, previously obtained through Kantorovich duality [Le et al., 2019]. This result offers a new perspective and a simplified proof, enriching the theoretical understanding of OT on tree structures.

* Third, we demonstrate that OT on a cycle graph can be reduced to a weighted median location problem on a line, which can be solved in linear time. This improves upon the approximate algorithm of Delon et al. [2010], providing an exact and more efficient solution.
* Finally, we establish a decomposition formula for computing OT on the class of simple cactus graphs, reducing it to computing OT on the bridge tree and each constituent cycle. As a result, our approach generalizes and unifies OT computation across trees, cycles, and cacti, all in linear time, thus, improving the classical superlinear time network flow methods.

Our work focuses on discrete balanced OT on simple graphs with cost defined as the graph distance. Several promising extensions remain open: generalizing to arbitrary cactus graphs, extending to continuous measures, adapting to unbalanced OT models, and exploring quadratic distance as a cost function. These directions are essential for broadening the scope and impact of our approach.

The paper is organized as follows. In Section 2, we introduce a new safe screening rule for identifying zero entries in the OT plan on general graphs. Section 3 applies this rule to derive a closed-form expression for OT on trees. In Section 4, we present a parameterized formula for computing OT on cycles. Finally, in Section 5, we integrate the developed results to compute OT on cacti in linear time.

## 2 Safe screening rule for OT on general graphs

In this section, we develop a new safe screening rule for OT on general graphs. We begin by recalling the definition of OT on graphs and the necessary optimality condition of the optimal transport plan. We then use this condition to derive the safe screening rule for both the case of graphs with bridges and the general case.

Let $\mathcal{G}$ be a simple undirected graph with $n$ vertices $v_1, \dots, v_n$. For a vertex $v$ in $\mathcal{G}$, we write $v \in \mathcal{G}$. Each edge in $\mathcal{G}$ has a positive length. Let $D \in \mathbb{R}^{n \times n}$ be the distance matrix, where $D_{ij} = D(v_i, v_j)$ represents the distance between vertices $v_i$ and $v_j$. We denote by $\delta_{v_i} \in \mathbb{R}_+$ the $i$-th unit basis vector. For a nonnegative vector $z \in \mathbb{R}_+^n$, we refer to it as weight vector on $\mathcal{G}$.

We call two weight vectors $a \in \mathbb{R}_+^n$ and $b \in \mathbb{R}_+^n$, the supply and demand, respectively. We assume that the supply and demand satisfy the balanced condition, i.e.,

$$ \sum_{i=1}^{n} a_i = \sum_{i=1}^{n} b_i. \qquad (1) $$

In this paper, we study the discrete balanced Optimal Transport (OT) problem. The goal of OT is to find the minimum cost of transporting mass from a supply vector $a$ to a demand vector $b$. A solution to this problem is a transportation plan, represented by a matrix $T \in \mathbb{R}_+^{n \times n}$, where $T_{ij}$ denotes the amount of mass transported from $a_i$ to $b_j$. Note that $D$ is symmetric but $T$ is not. The corresponding transportation cost is proportional to both the mass transported and the distance between nodes, and is given by $\sum_{i,j=1}^n D_{ij}T_{ij}$. Note that the OT value corresponding to this type of cost is also known as 1-Wasseinstein distance [Peyré et al., 2019] or Earth Mover's distance [Rubner et al., 2000]. The objective is to find a transport plan $T$ that minimizes the total cost, subject to the following supply and demand constraints:

* The total mass transported from $v_i$ to all destinations must equal the supply at $v_i$, i.e., $\sum_{j=1}^n T_{ij} = a_i$ for all $i = 1, \dots, n$.

* The total mass received at $v_j$ from all sources must equal the demand at $v_j$, i.e., $\sum_{i=1}^n T_{ij} = b_j$ for all $j = 1, \dots, n$.
The mathematical model of OT is given as a linear programming model.

$$ \min_{T \in \mathbb{R}_+^{n \times n}} \sum_{i,j=1}^{n} D_{ij} T_{ij} \qquad (\text{OT-2a}) $$

$$ \text{s.t.} \quad \sum_{j=1}^{n} T_{ij} = a_i, \forall i = 1, \dots, n \qquad (\text{OT-2b}) $$

$$ \sum_{i=1}^{n} T_{ij} = b_j, \forall j = 1, \dots, n \qquad (\text{OT-2c}) $$

We refer to the minimum value of OT problem (OT-2a)-(OT-2c) as OT$_G(a, b)$. Let denote an optimal plan $T^*$ as an optimal solution.

We now state the necessary condition of optimal plans. We say that the ordered vertices $(v_i, v_j, v_h, v_k)$ satisfy the *Monge condition* [Delon et al., 2010], also known as the *Shielding condition* [Schmitzer, 2016], if

$$ D_{ij} + D_{hk} < D_{ik} + D_{hj}. \qquad (3) $$

The next result ensures that if Monge condition holds, then one of the pair $(v_i, v_k)$ or $(v_h, v_j)$ must have zero transportation.

**Lemma 2.1** (Necessary optimality condition). Let $v_i, v_j, v_h, v_k \in G$ satisfy Monge condition (3). Then any optimal plan $T^*$ satisfies

$$ T_{ik}^* \cdot T_{hj}^* = 0. $$

*Proof.* We prove the lemma by contradiction. Suppose $T$ is an optimal transport plan that does not satisfy the required condition, i.e., $\varepsilon = \min\{T_{ik}, T_{hj}\} > 0$. We derive a contradiction by constructing a new plan $T^*$ with strictly lower objective value and satisfying the requirement.

To construct $T^*$, we keep all entries of $T$ unchanged, except for the following updates: decrease $T_{ik}$ and $T_{hj}$ by $\varepsilon$, and increase $T_{ij}$ and $T_{hk}$ by $\varepsilon$. The four pairs of indices $(i, j)$, $(i, k)$, $(h, j)$, $(h, k)$ form a rectangle. Therefore, $T^*$ remains feasible with respect to the OT constraints, and it satisfies the required condition $T_{ik}^* \cdot T_{hj}^* = 0$.

Moreover, the transportation cost under $T^*$ is strictly smaller than that under $T$, since

$$ \langle D, T^* \rangle = \langle D, T \rangle + [D_{ij} + D_{hk} - D_{ik} - D_{hj}]\varepsilon < \langle D, T \rangle. $$

This contradicts the optimality of $T$, completing the proof. □

<figure><img src="image_4.png" /><figcaption>Figure 2: A graph with bridge edge $e = (v_p, v_q)$ having $S(v_p, v_q) = G_+ \times G_-$</figcaption></figure>

Let us provide a concrete example in which Monge condition holds true. Note that if $e = (v_p, v_q)$ is a bridge edge decomposing the graph $G$ into connected subgraphs $G_+$ and $G_-$ with $v_p \in G_+$ and
$v_q \in \mathcal{G}_-$, see Figure 2. Let $v_i, v_j \in \mathcal{G}_+$ and $v_h, v_k \in \mathcal{G}_-$. Note that

$$D_{ij} \leq D_{ip} + D_{pj} \qquad (4a)$$

$$D_{hk} \leq D_{hq} + D_{qk} \qquad (4b)$$

$$D_{ik} = D_{ip} + D_{pq} + D_{qk} \qquad (4c)$$

$$D_{hj} = D_{hq} + D_{qp} + D_{pj} \qquad (4d)$$

Here the inequality (4a) and (4b) follow from the triangle inequality, while (4d) and (4c) follow from the facts that $(v_p, v_q)$ is a bridge edge. Therefore, if the bridge edge has positive edge length, i.e., $D_{pq} > 0$, then the Monge condition (3) holds.

From this observation, we present a safe screening rule for OT on graphs which identifies zero elements of optimal plan. The result basically says that if the total supply on $\mathcal{G}_+$ is greater than total demand, one should at least move some positive amount of mass from $\mathcal{G}_+$ to $\mathcal{G}_-$, and, in this case, we should not do backward.

**Theorem 2.2** (Safe screening rule for OT on graph with bridge). Let $(v_p, v_q)$ be a bridge with positive edge length and $T^*$ be any optimal transport plan. Consider the following statements

$$(i) \sum_{v_i \in \mathcal{G}_+} a_i > \sum_{v_j \in \mathcal{G}_+} b_j,$$

$$(ii) \text{ There exists a pair } (v_i, v_k) \in \mathcal{G}_+ \times \mathcal{G}_- \text{ such that } T_{ik}^* > 0,$$

$$(iii) \text{ For any pair } (v_h, v_j) \in \mathcal{G}_- \times \mathcal{G}_+, \text{ we have } T_{hj}^* = 0.$$

We have

$$(i) \implies (ii) \implies (iii). \qquad (5)$$

*Proof.* Since $(v_p, v_q)$ be a bridge with positive edge length, the Lemma 2.1 implies (ii) $\implies$ (iii) directly. We now prove (i) $\implies$ (ii).

Assume by contradiction that $T_{ik}^* = 0$ for all $(v_i, v_k) \in \mathcal{G}_+ \times \mathcal{G}_-$. Therefore,

$$\begin{aligned} \sum_{v_i \in \mathcal{G}_+} a_i &= \sum_{v_i \in \mathcal{G}_+} \sum_{v_j \in \mathcal{G}_-} T_{ij}^* \\ &= \sum_{v_i \in \mathcal{G}_+} \sum_{v_j \in \mathcal{G}_+} T_{ij}^* \\ &= \sum_{v_j \in \mathcal{G}_+} \sum_{v_i \in \mathcal{G}_+} T_{ij}^* \\ &\leq \sum_{v_j \in \mathcal{G}_+} \sum_{v_i \in \mathcal{G}_-} T_{ij}^* \\ &\leq \sum_{v_j \in \mathcal{G}_+} b_j. \end{aligned}$$

This contradicts to (i).

□

The Theorem 2.2 provides a practical method for safe screening, but it relies heavily on the assumption that the graph contains a bridge edge. While this assumption is particularly useful when working with trees and paths, it does not extend to graphs with cycles. In what follows, we present a more abstract yet general version of the safe screening rule that lifts this limitation.

Before proceeding, let us briefly reinterpret Theorem 2.2. Note that the theorem means that if there is a flow passing through the edge $(v_p, v_q)$ in the direction from $v_p$ to $v_q$, then moving mass in the reverse direction should be avoided. This insight allows us to generalize the result by removing the bridge-edge assumption on $(v_p, v_q)$.
For any two vertices $v_p$ and $v_q$, let $S(v_p, v_q)$ be the set of all pairs of vertices $(u, v)$ such that there exists a shortest path from $u$ to $v$ passing through $v_p$ before $v_q$, i.e.,

$$S(v_p, v_q) = \{(u, v) \in \mathcal{G} \times \mathcal{G} : D(u, v_p) + D(v_p, v_q) + D(v_q, v) = D(u, v)\}.$$

In Figure 2, we have $S(v_p, v_q) = \mathcal{G}_+ \times \mathcal{G}_-$ and $S(v_q, v_p) = \mathcal{G}_- \times \mathcal{G}_+$. The next theorem generalizes the implication (ii) $\Rightarrow$ (iii).

**Theorem 2.3 (Safe screening rule for OT on general graph).** Let $v_p, v_q \in \mathcal{G}$ such that $D(v_p, v_q) > 0$. Let $T^*$ be any optimal transportation plan. If $T^*$ is nonzero on $S(v_p, v_q)$, then it is zero on $S(v_q, v_p)$.

*Proof.* Proving the theorem is equivalent to showing that for any $(v_i, v_k) \in S(v_p, v_q)$ and $(v_h, v_j) \in S(v_q, v_p)$, we have $T_{ik}^* \cdot T_{hj}^* = 0$. Indeed, since $(v_i, v_k) \in S(v_p, v_q)$ and $(v_h, v_j) \in S(v_q, v_p)$, the inequalities (4a) and (4d) hold. Consequently, the Monge condition (3) is satisfied. By Lemma 2.1, we conclude the proof. □

## 3 OT on tree

In this section, we aim to derive the closed-form expression of OT on tree, which has been established in Le et al. [2019] using Kantorovich duality theory. Here, we propose a new proof using pure combinatorial approach by exploiting safe screening rule developed in Theorem 2.2.

In this section, we consider a rooted tree $\mathcal{T}$, where $v_1$ is a root node. Let $e_i$ and $\ell_i$ be the edge and its length of the edge connecting $v_i$ and its parent. Let $\mathcal{T}_i$ be the subtree rooted at $v_i$. For a weight vector $z$, define its cumulative distribution<fnref n="1" />, say $\hat{z} \in \mathbb{R}_+^n$, with $i$th element equal to the total mass of subtree $\mathcal{T}_i$, where $\mathcal{T}_i$ is the subtree rooted at $v_i$ containing all its descendants and itself, i.e.,

$$\hat{z}_i = \sum_{v_j \in \mathcal{T}_i} z_j, \qquad (6)$$

for all $i = 1, ..., n$. Note that $\hat{a}_1 = \hat{b}_1$ due to the balanced condition (1).

We now leverage the safe screening rule in Theorem 2.3 to derive a decomposition formula of OT on subtrees. This decomposition play an essential step in deriving the closed-form formula for OT on tree. We define the net flow of subtree $\mathcal{T}'$ as the difference between supply and demand on $\mathcal{T}'$,

$$f(\mathcal{T}') = \sum_{v_j \in \mathcal{T}'} (a_j - b_j). \qquad (7)$$

Specifically, let $f_i$ be the net flow of subtree $\mathcal{T}_i$, i.e.,

$$f_i = f(\mathcal{T}_i) = \hat{a}_i - \hat{b}_i. \qquad (8)$$

By Theorem 2.2, we know that if the total supply on $\mathcal{T}_i$ is strictly greater than its total demand, then one should only transport mass from $\mathcal{T}_i$ to its complement. In this case, the transported mass should be equal to $f_i$. Within $\mathcal{T}_i$, $v_i$ now has an extra demand $f_i$ and within $\mathcal{T} \setminus \mathcal{T}_i$, $v_j$ has an extra supply $f_j$, then

$$\mathrm{OT}_{\mathcal{T}}(a, b) = \mathrm{OT}_{\mathcal{T}_i}(a, b + f_i \delta_{v_i}) + \ell_i f_i + \mathrm{OT}_{\mathcal{T} \setminus \mathcal{T}_i}(a + f_i \delta_{v_j}, b).$$

Here, for $\mathcal{T}' \subset \mathcal{T}$, we should understand $\mathrm{OT}_{\mathcal{T}'}(a, b)$ as the OT between the restriction of weight vector $a$ and $b$ on $\mathcal{T}'$.

The general decomposition formula for signed value of $f_i$ is presented in the following lemma. Although the idea is simple, its proof is quite technical since one should separately consider cases $f_i > 0$, $f_i < 0$ and $f_i = 0$. The case $f_i = 0$ is quite intricate and, therefore, deferred to Appendix A.

<footnote n="1">¹referred to as “feature vector” in Le et al. [2019]</footnote>
**Lemma 3.1** (Decomposition of OT on tree). Let $f_i = f(T_i)$, then

$$ \mathrm{OT}_{\mathcal{T}}(a, b) = \mathrm{OT}_{\mathcal{T}_i}(a + f_i^{-} \delta_{v_i}, b + f_i^{+} \delta_{v_i}) + \ell_i |f_i| + \mathrm{OT}_{\mathcal{T} \setminus \mathcal{T}_i}(a + f_i^{+} \delta_{v_j}, b + f_i^{-} \delta_{v_j}). \quad (9) $$

where $f_i^+ = \max(f_i, 0)$ and $f_i^- = \max(-f_i, 0)$.

The next result shows that the optimal transport on tree can be computed in closed form.<fnref n="2" />

**Theorem 3.2** (Formula for OT on tree). For a tree $\mathcal{T}$ rooted at $v_1$, the optimal transport cost between $a$ and $b$ on $\mathcal{T}$ is $\ell$-weighted L1 norm between their cumulative distributions, i.e.,

$$ \mathrm{OT}_{\mathcal{T}}(a, b) = \sum_{i=2}^{n} \ell_i |\hat{a}_i - \hat{b}_i|. \quad (10) $$

Here $\ell_i$ is the length of the edge connecting $v_i$ and its parent.

*Proof.* Recall $f_i = f(T_i) = \hat{a}_i - \hat{b}_i$ be the net flow of $T_i$. Note that $f_1 = 0$ due to balanced condition (1) and $T_1 = \mathcal{T}$. The OT on tree can be rewritten as

$$ \mathrm{OT}_{\mathcal{T}}(a, b) = \mathrm{OT}_{\mathcal{T}_1}(a + f_1^{-} \delta_{v_1}, b + f_1^{+} \delta_{v_1}). $$

We denote the value of the right-hand-side by $z_1$. We now compute $z_1$ recursively. Fix a vertex $v_k$. Recursively applying Lemma 3.1 for each edges $(v_k, v_i)$ where $v_i$ is a child of $v_k$, we have

$$ z_k = \sum_{v_i \in N(v_k)} \ell_i |f_i| + \mathrm{OT}_{\mathcal{T}_i}(a + f_i^{-} \delta_{v_i}, b + f_i^{+} \delta_{v_i}) = \sum_{v_i \in N(v_k)} \ell_i |f_i| + z_k. $$

Here, $N(v_k)$ denotes the set of all children of $v_k$. If $v_k$ is a leaf, then $z_k = 0$. Repeat above recursive formula for $v_k$ from the root $v_1$ to the leaves, we obtain

$$ \mathrm{OT}_{\mathcal{T}}(a, b) = z_1 = \sum_{v_i \in \mathcal{T}: v_i \neq v_1} \ell_i |f_i| = \sum_{i=2}^{n} \ell_i |\hat{a}_i - \hat{b}_i|. $$

This completes the proof.

<figure><img src="image_5.png" /></figure>

Since the cumulative distributions $\hat{a}$ and $\hat{b}$ can be determined in $O(n)$ where $n$ is the number of vertices by depth-first-search from bottom-up. The OT on tree can be computed in $O(n)$.

<figure><img src="image_6.png" /></figure>

<table><caption>Figure 3: A tree (a) and its data (b)</caption><thead><tr><th>$v_i$</th><th>$v_1$</th><th>$v_2$</th><th>$v_3$</th><th>$v_4$</th><th>$v_5$</th><th>$v_6$</th><th>$v_7$</th></tr></thead><tbody><tr><td>$a_i$</td><td>8</td><td>6</td><td>2</td><td>2</td><td>7</td><td>4</td><td>7</td></tr><tr><td>$b_i$</td><td>9</td><td>6</td><td>3</td><td>1</td><td>6</td><td>6</td><td>5</td></tr><tr><td>$\hat{a}_i$</td><td>36</td><td>15</td><td>13</td><td>2</td><td>7</td><td>4</td><td>7</td></tr><tr><td>$\hat{b}_i$</td><td>36</td><td>13</td><td>14</td><td>1</td><td>6</td><td>6</td><td>5</td></tr><tr><td>$\hat{a}_i - \hat{b}_i$</td><td>0</td><td>2</td><td>-1</td><td>1</td><td>1</td><td>-2</td><td>2</td></tr></tbody></table>

**Example 3.3.** Let $\mathcal{T}$ be a tree, as shown in Figure 3a, with the corresponding supply $a$ and demand $b$ presented in Table 3b. Here, we assume the tree with unit edge length for simplicity. The Table 3b shows values of $\hat{a}$ and $\hat{b}$. By Theorem 3.2, we have $\mathrm{OT}_{\mathcal{T}}(a, b) = 9$.

<footnote n="2">²note that the corresponding optimal plan can be computed efficiently by backtracking, see e.g., [Sato et al., 2020].</footnote>
We conclude this section with a remark on the different and the complexity of computing OT on lines and paths.

**Remark 3.4 (OT on paths and lines).** OT on line (more precisely, discrete balanced 1D OT) can be considered as OT on path as soon as the points on line are sorted. Since path is a tree, OT on path can be computed in $O(n)$. The complexity of OT on line is dominated by the complexity of sorting's algorithm, which is $O(n \log n)$.

# 4 OT on cycle

In this section, we exploit the safe screening rule in Theorem 2.3 to show that the OT on cycle can be parameterized as an OT problems on path. The idea is based on a simple observation that, by removing any edge of a cycle, one obtains a path, which is a special type of tree. This leads to finding an optimal parameter which minimizes the objective function. Surprisingly, this univariate problem turns out to be a weighted median location on line, thus can be solved efficiently in linear time. This computational result is an exact solving method, which improves the approximation approach proposed by Delon et al. [2010].

Let $C$ be a cycle with $n$ vertices $v_1, ..., v_n$ ordered counter clockwise. For $i = 1, ..., n$, we denote by $e_i$ the edge connecting $v_{i-1}$ and $v_i$ ($v_0 \equiv v_n$). Each edge $e_i$ has a length $\ell_i$. Let $a$ and $b$ be the supply and demand on $C$. We are interested in efficient computing method for the optimal transport cost from $a$ to $b$ on $C$.

To begin, we first notice that by removing $e_1 = (v_n, v_1)$ from $C$, we obtain a path. By Theorem 2.3, we know that there is only one flow moving on $e_1$ either in direction from $v_n$ to $v_1$ or vice versa. Let us consider the case that the flow from $v_n$ to $v_1$ and denote amount of flow by $x > 0$. After removing $e_1$, one obtain a path and on this path $v_1$ has an extra amount of supply $x$ and $v_n$ has an extra amount of demand. This observation allow us reinterpret OT on cycle by an OT on path with parameter $x$.

In the following, we push this observation into a more rigorous formulation. Let $\hat{a}$ and $\hat{b}$ be the cumulative supply and demand of $a$ and $b$, respectively, associated with the path $C \setminus \{e_1\}$ obtained from $C$ after removing $e_1$. Let the path rooted at $v_1$, we have

$$ \hat{a}_i = \sum_{j=i}^{n} a_j, \qquad (11a) $$

$$ \hat{b}_i = \sum_{j=i}^{n} b_j. \qquad (11b) $$

Please refer to Figure 4 as an example of indexing vertices of cycle and the computation of $\hat{a}$ and $\hat{b}$.

The next result shows that solving OT on cycle is equivalent to finding a weighted median location on line. Here, recall that the weighted median on line is a point $x \in \mathbb{R}$ that minimizes the total weighted distance to other points located at $p_i \in \mathbb{R}$ with weights $\ell_i > 0$ for all $i = 1, ..., n$, i.e.,

$$ \min_{x \in \mathbb{R}} \sum_{i=1}^{n} \ell_i |x - p_i|. $$

**Theorem 4.1 (Formula for OT on cycle).** Let $a$ and $b$ be the supply and demand on $C$ with the corresponding cumulative distributions $\hat{a}$ and $\hat{b}$ defined in (11a) and (11a). The OT cost from $a$ to $b$ equals to the median value on line with locations $\hat{a}_i - \hat{b}_i$ and weights $\ell_i$ for $i = 1, ..., n$, where $\ell_i$ denotes the length of edge connecting $v_i$ and $v_{i-1}$.

$$ \mathrm{OT}_C(a, b) = \min_{x \in \mathbb{R}} \sum_{i=1}^{n} \ell_i |x - (\hat{a}_i - \hat{b}_i)|, \qquad (12) $$
Proof. Let $T^*$ be an optimal plan. To prove (12), we consider three cases. To simplify notation, let $p_i = \hat{a}_i - \hat{b}_i$ for all $i = 1, \dots, n$. We consider three cases.

**Case 1.** If the plan $T^*$ has no transportation over $e_1$. Then it is clear that all flows move within the path $C \setminus \{e_1\}$, thus

$$ \mathrm{OT}_C(a, b) = \mathrm{OT}_{C \setminus \{e_1\}}(a, b) = \sum_{i=2}^{n} \ell_i |p_i| = \sum_{i=1}^{n} \ell_i |p_i|. $$

Here, the second equality follows from (10) and the last equality holds true since $p_1 = 0$. In this case, $\mathrm{OT}_C(a, b)$ equals to the right-hand-side of (12) evaluated at $x = 0$.

**Case 2.** If $T^*$ has a positive transportation on $e_1$ with direction from $v_n$ to $v_1$. By Theorem 2.3, we know that there are no backward transportation. We let $x > 0$ the total flow passing through $e_1$ with the direction from $v_n$ to $v_1$. On the path $C \setminus e_1$, $v_1$ serves an extra supply $x$, while $v_n$ admits an extra demand $x$. Therefore,

$$ \begin{aligned} \mathrm{OT}_C(a, b) &= \mathrm{OT}_{C \setminus \{e_1\}}(a + x\delta_{v_1}, b + x\delta_{v_n}) + \ell_1 x \\ &= \sum_{i=2}^{n} \ell_i |\hat{a}_i - (\hat{b}_i + x)| + \ell_1 x \\ &= \sum_{i=2}^{n} \ell_i |p_i - x| + \ell_1 |x| \\ &= \sum_{i=1}^{n} \ell_i |x - p_i|. \end{aligned} $$

**Case 3.** Similar to Case 2, in this case we assume that $T^*$ has a positive flow on $e_1$ with direction from $v_1$ to $v_n$. Since there are no backward flow, we let $y > 0$ be the total flow passing through $e_1$ in the direction $v_1$ to $v_n$. In this case, we have

$$ \begin{aligned} \mathrm{OT}_C(a, b) &= \mathrm{OT}_{C \setminus \{e_1\}}(a + y\delta_{v_n}, b + y\delta_{v_1}) + \ell_1 y \\ &= \sum_{i=2}^{n} \ell_i |(\hat{a}_i + y) - \hat{b}_i| + \ell_1 y. \end{aligned} $$

Let $x = -y < 0$, we have

$$ \mathrm{OT}_C(a, b) = \sum_{i=2}^{n} \ell_i |p_i - x| + \ell_1 |x| = \sum_{i=1}^{n} \ell_i |x - p_i|. $$

Overall, in any cases, we can always represent $\mathrm{OT}(a, b)$ as $\sum_{i=1}^{n} \ell_i |x - p_i|$, where $x$ stands for the total flow passing through $e_1$ with sign depending on the direction of the flow. Since $\mathrm{OT}(a, b)$ minimizes the total transportation cost, it is equal to the minimum value of the function $\sum_{i=1}^{n} \ell_i |x - p_i|$.

□

**Example 4.2.** Consider a cycle graph $C$ as shown in Figure 4a with 4 vertices. Assume that all edges have unit length for simplicity. The supply $a$ and demand $b$ defined on $C$ given in Table 4c.

We aim to compute the optimal transport cost $\mathrm{OT}_C(a, b)$. We convert the cycle into a path rooted at $v_1$, by removing edge $e_1 = (v_4, v_1)$. Now, we compute the cumulative supply $\hat{a}$ and demand $\hat{b}$ according to (11a)-(11b), the results are presented the three last rows of Table 4c. By Theorem 4.1, the OT cost on the cycle is equivalent to the following minimum problem

$$ \mathrm{OT}_C(a, b) = \min_{x \in \mathbb{R}} |x - 0| + |x + 1| + |x + 2| + |x + 1| = 2, $$

Which attains the minimizer $x = -1$.
<figure><img src="image_7.png" /><figcaption>Figure 4: A cycle (top), a corresponding path (middle), and its data (bottom)</figcaption></figure>

# 5 OT on cactus

In this section, we investigate the OT on a subclass of cactus graphs in which any two cycles share no vertex in common. We refer to this class of cacti as *simple cactus*. Recall that a general cactus is a graph where any two cycles share at most one vertex in common. The rationale of our restriction of study on the simple cacti is as follows. Under the assumption that any two cycles are vertex-disjoint, if we delete all the bridge edges, we obtain connected components that are either single vertices or single cycles, for which OT can be computed efficiently as developed in Section 4. Otherwise, when the assumption does not hold, the resulting connected components may be bundle of cycles where efficient computing method for OT on such graphs has not been investigated and out of the scope of this paper. We therefore leave the analysis of OT on general cactus for future work.

Let $\mathcal{G}$ be a simple cactus. By deleting its bridge edges, we obtain $m$ components either a vertex or cycle, called *supernode* and denoted by $C_1, \dots, C_m$. The set of supernodes and bridge edges induce a *bridge tree*, denoted by $\mathcal{T}$. Note that a cactus graph with no cycle is simply a tree.

Now, we observe that the OT on simple cactus $\mathcal{G}$ can be decomposed into the transportation between supernodes and within supernodes. Note that the OT between supernodes can be computed using OT on bridge tree $\mathcal{T}$ by Theorem 3.2. In this process, the net flow on each edge of $\mathcal{T}$ can be identified. These flow is then used to update supply and demand on each supernode so that within each supernode, the total supply and total demand are balanced. As soon as the balanced condition holds on each supernode, one sees that the OT on each single node is zero while the OT on cycle can be computed by Theorem 4.1. In the remaining, we now detail how to perform the decomposition of the computation of OT on cactus into tree and cycles.

Let $A, B$ be the supply and demand on the bridge tree $\mathcal{T}$ with $j$th entry equal the total supply and
demand on supernode $C_j$, where $j = 1, ..., m$.

$$A_j = \sum_{v_i \in C_j} a_i, \qquad (13a)$$

$$B_j = \sum_{v_i \in C_j} b_i. \qquad (13b)$$

Note that $A = (A_1, ..., A_m)$ and $B = (B_1, ..., B_m)$ satisfy the balance condition (1).

Let the bridge tree rooted at $C_1$. Let $\mathcal{T}_i$ be the subtree of $\mathcal{T}$ rooted at $C_i$. Let $f_i$ be the net flow of $\mathcal{T}_i$, i.e.,

$$f_i = f(\mathcal{T}_i) = \hat{A}_i - \hat{B}_i. \qquad (14)$$

For a bridge edge $e_i$ connecting $C_i$ and its parent supernode $C_j$, $i = 2, ..., m$, we assume that

$$e_i = (v_h, v_k) \text{ with } v_h \in C_i \text{ and } v_k \in C_j. \qquad (15)$$

Let $\ell_i = \ell(e_i)$ for $i = 2, ..., m$ be the length of bridge edge $e_i$. Similar to (9), we have

$$\mathrm{OT}_{\mathcal{G}}(a, b) = \mathrm{OT}_{\mathcal{T}_i}(a + f_i^{-} \delta_{v_h}, b + f_i^{+} \delta_{v_h}) + \ell_i |f_i| + \mathrm{OT}_{\mathcal{T} \setminus \mathcal{T}_i}(a + f_i^{+} \delta_{v_k}, b + f_i^{-} \delta_{v_k}). \qquad (16)$$

Let $\tilde{a} := a$ and $\tilde{b} := b$. We define an update for $\tilde{a}$ and $\tilde{b}$ at indices $h$ and $k$ as follows

$$\begin{aligned}
\tilde{a}_k &:= \tilde{a}_k + f_i^-, \\
\tilde{b}_k &:= \tilde{b}_k + f_i^+, \\
\tilde{a}_h &:= \tilde{a}_h + f_i^+, \\
\tilde{b}_h &:= \tilde{a}_h + f_i^-.
\end{aligned} \qquad (17)$$

Applying the update (17), we can rewrite (16) as follows

$$\mathrm{OT}_{\mathcal{G}}(a, b) = \mathrm{OT}_{\mathcal{T}_i}(\tilde{a}, \tilde{b}) + \ell_i |f_i| + \mathrm{OT}_{\mathcal{T} \setminus \mathcal{T}_i}(\tilde{a}, \tilde{b}). \qquad (18)$$

Applying the decomposition (18) recursively for all bridge edges along with updating $\tilde{a}, \tilde{b}$ for each bridge edge, one obtains

$$\mathrm{OT}_{\mathcal{G}}(a, b) = \sum_{i=2}^{m} \ell_i |f_i| + \sum_{i=1}^{m} \mathrm{OT}_{C_i}(\tilde{a}, \tilde{b}), \qquad (19)$$

It is important to note that the update (17) is efficient in the sense that each entry of $\tilde{a}$ and $\tilde{b}$ are updated at most once. Furthermore, the restriction of $\tilde{a}$ and $\tilde{b}$ on each supernode satisfy the balanced condition. This ensures the validity of (19).

Observing that the first term (19) is the OT between $A$ and $B$ on the bridge tree, we therefore obtain

**Theorem 5.1 (Formula for OT on cactus).** Let $\mathcal{G}$ be a cactus such that any two cycles are vertex-disjoint. We have

$$\mathrm{OT}_{\mathcal{G}}(a, b) = \mathrm{OT}_{\mathcal{T}}(A, B) + \sum_{i=1}^{m} \mathrm{OT}_{C_i}(\tilde{a}, \tilde{b}), \qquad (20)$$

where $A, B$ are defined in (13) and $\tilde{a}, \tilde{b}$ are recursively updated according to (17).

Note that the bridge tree can be constructed in $O(n)$, where $n$ is the number of vertices of the considered graph. By the decomposition formula for OT on cactus in Theorem 5.1 together with OT on tree Theorem 3.2 and OT on cycle Theorem 4.1, we obtain the following computational result for OT.
**Algorithm 1** Fast computing method for optimal transport on cactus

**Require:** Simple cactus $\mathcal{G}$, supply $a$ and demand $b$ satisfying (1)

1: Construct the bridge tree $\mathcal{T}$ from $\mathcal{G}$. The tree $\mathcal{T}$ has $m$ supernodes $C_1, ..., C_m$ rooted at $C_1$ and $m-1$ bridge edges $e_2, ..., e_m$

2: Compute $A$ and $B$ using (13)

3: Compute $\text{OT}_{\mathcal{T}}(A, B)$ using (10)

4: Initialize $\tilde{a} := a$ and $\tilde{b} := b$

5: **for** $i = 2, ..., m$ **do**

6: Compute net flow $f_i$ from $A$ and $B$ using (14)

7: Identify data tuple $(C_i, C_j, v_h, v_k)$ corresponding bridge edge $e_i$ in (15)

8: Update $\tilde{a}$ and $\tilde{b}$ at indices $h$ and $k$ with $f_i$ using (17)

9: **end for**

10: **for** $i = 1, ..., m$ **do**

11: Compute $\text{OT}_{C_i}(\tilde{a}, \tilde{b})$ using (12)

12: **end for**

13: Compute $\text{OT}_{\mathcal{G}}(a, b)$ from $\text{OT}_{\mathcal{T}}(A, B)$ and $\text{OT}_{C_i}(\tilde{a}, \tilde{b})$ for $i = 1, ..., m$ using (20)

14: **return** $\text{OT}_{\mathcal{G}}(a, b)$

<table><caption>Table 1: Data of simple cactus in Figure 1a</caption><thead><tr><th>1</th><th>C<sub>j</sub></th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>C<sub>3</sub></th><th>C<sub>4</sub></th><th>C<sub>5</sub></th><th>C<sub>6</sub></th><th>C<sub>7</sub></th></tr></thead><tbody><tr><td>2</td><td>v<sub>i</sub></td><td>(v<sub>1</sub>, v<sub>2</sub>, v<sub>3</sub>, v<sub>4</sub>)</td><td>(v<sub>5</sub>, v<sub>6</sub>, v<sub>7</sub>)</td><td>v<sub>8</sub></td><td>v<sub>9</sub></td><td>(v<sub>10</sub>, v<sub>11</sub>, v<sub>12</sub>)</td><td>v<sub>13</sub></td><td>(v<sub>14</sub>, v<sub>15</sub>, v<sub>16</sub>)</td></tr><tr><td>3</td><td>a<sub>i</sub></td><td>(2,1,2,3)</td><td>(2,3,1)</td><td>2</td><td>2</td><td>(1,4,2)</td><td>4</td><td>(2,3,2)</td></tr><tr><td>4</td><td>b<sub>i</sub></td><td>(1,2,2,4)</td><td>(2,2,2)</td><td>3</td><td>1</td><td>(2,3,1)</td><td>6</td><td>(2,2,1)</td></tr><tr><td>5</td><td>A<sub>j</sub></td><td>8</td><td>6</td><td>2</td><td>2</td><td>7</td><td>4</td><td>7</td></tr><tr><td>6</td><td>B<sub>j</sub></td><td>9</td><td>6</td><td>3</td><td>1</td><td>6</td><td>6</td><td>5</td></tr><tr><td>7</td><td>f<sub>j</sub></td><td>0</td><td>2</td><td>-1</td><td>1</td><td>1</td><td>-2</td><td>2</td></tr><tr><td>9</td><td>\tilde{a}<sub>i</sub></td><td>(2,3,2,3)</td><td>(2,4,2)</td><td>3</td><td>2</td><td>(1,4,2)</td><td>6</td><td>(2,3,2)</td></tr><tr><td>10</td><td>\tilde{b}<sub>i</sub></td><td>(1,2,3,4)</td><td>(4,2,2)</td><td>3</td><td>2</td><td>(3,3,1)</td><td>6</td><td>(4,2,1)</td></tr><tr><td>11</td><td>\text{OT}_{C_j}(\tilde{a}, \tilde{b})</td><td>2</td><td>2</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td></tr></tbody></table>

**Theorem 5.2.** The OT on tree, cycle and simple cactus can be solved in $O(n)$, where $n$ is the number of vertices of the considered graph.

We end this section with an example demonstrating how to compute OT on simple cactus using Theorem 5.1.

**Example 5.3.** Consider a simple cactus $\mathcal{G}$ given in Figure 1a with bridge tree $\mathcal{T}$ given in Figure 1b. The supernodes of $\mathcal{T}$ together with their vertices are given in row 1 and row 2 of Table 1. The supply $a$ and demand $b$ are given in row 3 and 4 of Table 1, respectively. Note that the supply $a$ and demand $b$ are balanced with total mass equal 36. Here, we assume for simplicity that all edge lengths equal 1.

We now follow Algorithm 1, step by step to compute $\text{OT}_{\mathcal{G}}(a, b)$.

Line 1. The bridge tree has 7 supernodes $C_1, ..., C_7$ and 6 bridges edges.

Line 2. Note that the corresponding supply and demand at supernodes are $A = (8, 6, 2, 2, 7, 4, 7)$ and $B = (9, 6, 3, 1, 6, 6, 5)$ computed by (13a)-(13b) and given by row 5 and 6 in Table 1.

Line 3. Therefore, we have the cumulative supply $\hat{A} = (36, 15, 13, 2, 7, 4, 7)$ and cumulative demand $\hat{B} = (36, 13, 14, 1, 6, 6, 5)$. Now, the computing of OT on $\mathcal{T}$ has been illustrated by Example 3.3, we have

$$ \text{OT}_{\mathcal{T}}(A, B) = \sum_{j=2}^{7} |\hat{A}_{j} - \hat{B}_{j}| = 2 + 1 + 1 + 1 + 2 + 2 = 9. $$
Line 6 and 7. Compute net flow $f_i$

Line 8. Update $\tilde{a}, \tilde{b}$.

Line 10. Now, we calculate the OT cost in each supernode. For cycle $C_1$, the supply and demand is (2, 3, 2, 3) and (1, 2, 3, 4). Thus, the computing of OT on $C_1$ has been demonstrated in Example 4.2. Precisely,

$$ \mathrm{OT}_{C_1}(\tilde{a}, \tilde{b}) = \min_{x \in \mathbb{R}} (|x-0| + |x+1| + |x+2| + |x+1|) = 2. $$

Note that for the supernodes containing exactly single vertex, which are $C_3, C_4, C_6$, will have zero OT. For other cycles, we can compute analogously

$$ \mathrm{OT}_{C_2}(\tilde{a}, \tilde{b}) = \min_{x \in \mathbb{R}} (|x-0| + |x-2| + |x-0|) = 2, $$

$$ \mathrm{OT}_{C_5}(\tilde{a}, \tilde{b}) = \min_{x \in \mathbb{R}} (|x-0| + |x-2| + |x-1|) = 2, $$

$$ \mathrm{OT}_{C_7}(\tilde{a}, \tilde{b}) = \min_{x \in \mathbb{R}} (|x-0| + |x-2| + |x-1|) = 2. $$

Therefore, the OT cost on the simple cactus graph equals to

$$ \mathrm{OT}_G(a, b) = 9 + 2 \cdot 4 = 17. $$

# 6 Conclusion

This paper presents a novel safe screening rule for identifying zero entries in the optimal transport (OT) plan on graphs. Unlike prior methods based on KKT conditions and solver integration, our approach is derived directly from necessary optimality conditions, allowing us to reveal the structural sparsity of the OT plan. This structural insight enables significant problem simplification and leads to more efficient algorithms.

By applying this screening rule, we derive closed-form or linear-time solutions for discrete balanced OT on trees, cycles, and cactus graphs. Notably, we offer a new combinatorial proof for OT on trees, reduce OT on cycles to a weighted median problem, and establish a decomposition formula for OT on cactus graphs. These contributions significantly improve upon traditional network-flow-based methods with cubic complexity.

Future work may extend our framework in several directions: handling general cactus structures, continuous probability measures, and unbalanced OT problems; and exploring alternative cost functions such as quadratic metrics. These extensions would further enhance the theoretical depth and practical reach of our approach in graph-based OT and its applications.

# Acknowledgement

The authors would also like to thank Vincent Duval for his helpful comments and for pointing out relevant literature.

# References

Mokhtar Z Alaya, Maxime Berar, Gilles Gasso, and Alain Rakotomamonjy. Screening sinkhorn algorithm for regularized optimal transport. *Advances in Neural Information Processing Systems*, 32, 2019.

Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In *International conference on machine learning*, pages 214–223. PMLR, 2017.
Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. *ACM Transactions on Graphics (TOG)*, 38(4):1–13, 2019.

Antoine Bonnefoy, Valentin Emiya, Liva Ralaivola, and Rémi Gribonval. A dynamic screening principle for the lasso. In *2014 22nd European signal processing conference (EUSIPCO)*, pages 6–10. IEEE, 2014.

Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Scaling algorithms for unbalanced transport problems. *arXiv preprint arXiv:1607.05816*, 2016.

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. *Advances in neural information processing systems*, 26, 2013.

Julie Delon, Julien Salomon, and Andrei Sobolevski. Fast transport optimization for monge costs on the circle. *SIAM Journal on Applied Mathematics*, 70(7):2239–2258, 2010.

Clément Elvira and Cédric Herzet. Safe squeezing for antisparse coding. *IEEE Transactions on Signal Processing*, 68:3252–3265, 2020.

Montacer Essid and Justin Solomon. Quadratically regularized optimal transport on graphs. *SIAM Journal on Scientific Computing*, 40(4):A1961–A1986, 2018.

Jianqing Fan and Jinchi Lv. Sure independence screening. *Wiley StatsRef: Statistics Reference Online*, 2018.

Olivier Fercoq, Alexandre Gramfort, and Joseph Salmon. Mind the duality gap: safer rules for the lasso. In *International conference on machine learning*, pages 333–342. PMLR, 2015.

Laurent El Ghaoui, Vivian Viallon, and Tarek Rabbani. Safe feature elimination for the lasso and sparse supervised learning problems. *arXiv preprint arXiv:1009.4219*, 2010.

Théo Guyard, Cédric Herzet, and Clément Elvira. Screen & relax: accelerating the resolution of elastic-net by safe identification of the solution support. In *Icassp 2022-2022 ieee international conference on acoustics, speech and signal processing (icassp)*, pages 5443–5447. IEEE, 2022.

Piotr Indyk. Fast color image retrieval via embeddings. In *Workshop on Statistical and Computational Theories of Vision (at ICCV)*, 2003, 2003.

Tam Le and Truyen Nguyen. Entropy partial transport with tree metrics: Theory and practice. In *International Conference on Artificial Intelligence and Statistics*, pages 3835–3843. PMLR, 2021.

Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances. *Advances in neural information processing systems*, 32, 2019.

Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. In *International Conference on Artificial Intelligence and Statistics*, pages 9844–9868. PMLR, 2022.

Thu Le Tran. *Quelques contributions dans la conception de "régions sûres" et "tests d'élagages sûrs" en optimisation convexe*. PhD thesis, Université de Rennes, 2023.

Eugene Ndiaye. *Safe optimization algorithms for variable selection and hyperparameter tuning*. PhD thesis, Université Paris Saclay (COmUE), 2018.

Kien T Nguyen, Pham V Chien, Ly H Hai, and Huynh D Quoc. A simple linear time algorithm for computing a 1-median on cactus graphs. *Applications and Applied Mathematics: An International Journal (AAM)*, 12(1):5, 2017.
Kohei Ogawa, Yoshiki Suzuki, and Ichiro Takeuchi. Safe screening of non-support vectors in pathwise svm computation. In *International conference on machine learning*, pages 1382–1390. PMLR, 2013.

James Orlin. A faster strongly polynomial minimum cost flow algorithm. In *Proceedings of the Twentieth annual ACM symposium on Theory of Computing*, pages 377–387, 1988.

Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. *Foundations and Trends in Machine Learning*, 11(5-6):355–607, 2019.

Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The earth mover's distance as a metric for image retrieval. *International journal of computer vision*, 40:99–121, 2000.

Filippo Santambrogio. Optimal transport for applied mathematicians. *Birkhäuser, NY*, 55(58-63):94, 2015.

Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on a tree. *Advances in neural information processing systems*, 33:19039–19051, 2020.

Bernhard Schmitzer. A sparse multiscale algorithm for dense optimal transport. *Journal of Mathematical Imaging and Vision*, 56(2):238–259, 2016.

Thibault Séjourné, François-Xavier Vialard, and Gabriel Peyré. Faster unbalanced optimal transport: Translation invariant sinkhorn and 1-d frank-wolfe. In *International Conference on Artificial Intelligence and Statistics*, pages 4995–5021. PMLR, 2022.

Atsushi Shibagaki, Masayuki Karasuyama, Kohei Hatano, and Ichiro Takeuchi. Simultaneous safe screening of features and samples in doubly sparse modeling. In *International Conference on Machine Learning*, pages 1577–1586. PMLR, 2016.

Xun Su, Zhongxi Fang, and Hiroyuki Kasai. Safe screening for unbalanced optimal transport. *arXiv preprint arXiv:2307.00247*, 2023.

Robert Tibshirani, Jacob Bien, Jerome Friedman, Trevor Hastie, Noah Simon, Jonathan Taylor, and Ryan J Tibshirani. Strong rules for discarding predictors in lasso-type problems. *Journal of the Royal Statistical Society Series B: Statistical Methodology*, 74(2):245–266, 2012.

Thu-Le Tran, Clément Elvira, Hong-Phuong Dang, and Cédric Herzet. Beyond gap screening for lasso by exploiting new dual cutting half-spaces. In *2022 30th European Signal Processing Conference (EUSIPCO)*, pages 2056–2060. IEEE, 2022.

Thu-Le Tran, Clément Elvira, Hong-Phuong Dang, and Cédric Herzet. One to beat them all:" ryu"-a unifying framework for the construction of safe balls. *arXiv preprint arXiv:2312.00640*, 2023.

Cédric Villani. *Topics in optimal transportation*, volume 58. American Mathematical Soc., 2021.

Jie Wang, Jiayu Zhou, Peter Wonka, and Jieping Ye. Lasso screening rules via dual polytope projection. *Advances in neural information processing systems*, 26, 2013.

Zhen James Xiang and Peter J Ramadge. Fast lasso screening tests based on correlations. In *2012 IEEE international conference on acoustics, speech and signal processing (ICASSP)*, pages 2137–2140. IEEE, 2012.

Hiroaki Yamada and Makoto Yamada. Dynamic sasvi: Strong safe screening for norm-regularized least squares. *Advances in neural information processing systems*, 34:14645–14655, 2021.

Jingyi Zhang, Ping Ma, Wenxuan Zhong, and Cheng Meng. Projection-based techniques for high-dimensional optimal transport problems. *Wiley Interdisciplinary Reviews: Computational Statistics*, 15(2):e1587, 2023.
# A Proof of Lemma 3.1

In this section, we aim at proving Lemma 3.1. The proof contains two parts corresponding to $f > 0$ and $f = 0$. Note that we ignore the case $f < 0$ since it is similar to the cases $f > 0$. The proof associated with case $f > 0$ can be proved directly using Section 2, while proving the case $f = 0$, we need two lemmas as discussed below.

**Lemma A.1 (Existence of optimal plan with maximum diagonal).** There exists an optimal plan $T^*$ such that $T_{ii}^* = \min\{a_i, b_i\}$ for all $i = 1, ..., n$.

*Proof.* By (OT-2b) and (OT-2b), it is clear that $T_{ii}^* \le \min\{a_i, b_i\}$ for all $i = 1, ..., n$. Let $T^*$ be an optimal plan such that $T_{ii}^* < \min\{a_i, b_i\}$ for some index $i$. We now contruct a procedure to update $T^*$ to become a plan satisfying the lemma. Also by (OT-2b) and (OT-2b), there exist indices $h, k$ such that $T_{ih}^* > 0$ and $T_{kj}^* > 0$. Note that by triangle inequality, we have $D_{ii} + D_{hk} \le D_{ih} + D_{ki}$. Analogous to the update used in the proof of Lemma 2.1, we may construct new optimal plan, also denoted by $T^*$, in which $T_{ii}^*$ has new value strictly larger than the previous value.

Note that this construction does not decrease any value on the diagonal of $T^*$. Indeed, if $h \ne k$, this update does not change any value on the diagonal except increasing $T_{ii}^*$. Otherwise, this update only increases the values of $T_{ii}^*$ and $T_{hh}^*$ on the diagonal. Therefore, we may repeat this process until each entry on the diagonal reaches their maximum values, i.e., $T_{ii}^* = \min\{a_i, b_i\}$ for all $i = 1, ..., n$. □

Lemma A.1 leads to the following result.

**Lemma A.2.** We have $\text{OT}(a, b) = \text{OT}([a - b]_+, [b - a]_+)$.

*Proof.* Let $T^*$ be an optimal plan from $a$ to $b$ with maximum diagonal as in Lemma A.1. Consider $\hat{T} = T^* - \text{diag}(\min(a, b))$. Lemma A.1 ensures that $\hat{T}$ is nonnegative. Furthermore, it is a feasible plan for transporting from $[a - b]_+$ to $[b - a]_+$, thus $\text{OT}(a, b) = \langle D, T^* \rangle = \langle D, \hat{T} \rangle \ge \text{OT}([a - b]_+, [b - a]_+)$. Conversely, let $\hat{T}$ be any optimal plan from $[a - b]_+$ to $[b - a]_+$, then $T^* = \hat{T} + \text{diag}(\min(a, b))$ is a feasible plan from $a$ to $b$, thus $\text{OT}([a - b]_+, [b - a]_+) = \langle D, \hat{T} \rangle = \langle D, T^* \rangle \ge \text{OT}(a, b)$. Hence, $\text{OT}(a, b) = \text{OT}([a - b]_+, [b - a]_+)$. □

Now, we can prove Lemma 3.1.

*Proof of Lemma 3.1.* We consider two cases corresponding to the sign of $f$. Recall that $f$ is the difference between supply and demand on $T_+$. In this proof, we focus on the case that $f = 0$. Note that if $T_1$ and $T_2$ are optimal on $T_1$ and $T_2$, then we may construct a feasible plan for $T$, therefore

$$ \text{OT}_{\mathcal{T}}(a, b) \le \text{OT}_{\mathcal{T}_1}(a, b) + \text{OT}_{\mathcal{T}_2}(a, b). $$

We only need to prove that

$$ \text{OT}_{\mathcal{T}}(a, b) \ge \text{OT}_{\mathcal{T}_1}(a, b) + \text{OT}_{\mathcal{T}_2}(a, b). $$

Indeed, we have

$$ \begin{aligned} \text{OT}_{\mathcal{T}}(a, b) &= \text{OT}_{\mathcal{T}_1}(a + |f_i|\delta_{v_p}, b + |f_i|\delta_{v_p}) + \text{OT}_{\mathcal{T}_2}(a + |f_i|\delta_{v_q}, b + |f_i|\delta_{v_q}) + 2|f_i|\ell_e \\ &= \text{OT}_{\mathcal{T}_1}(a, b) + \text{OT}_{\mathcal{T}_2}(a, b) + 2|f_i|\ell_e. \end{aligned} $$

where the second equality follows from Lemma A.2. This completes the proof. □