Paper: arXiv 2504.15809

Authors: Yu Zhang, Yafei Li, Claudio Tessone

Abstract

Decentralized exchanges, such as those employing constant product market makers (CPMMs) like Uniswap V2, play a crucial role in the blockchain ecosystem by enabling peer-to-peer token swaps without intermediaries. Despite the increasing volume of transactions, there remains limited research on identifying optimal trading paths across multiple DEXs. This paper presents a novel line-graph-based algorithm (LG) designed to efficiently discover profitable trading routes within DEX environments. We benchmark LG against the widely adopted Depth-First Search (DFS) algorithm under a linear routing scenario, encompassing platforms such as Uniswap, SushiSwap, and PancakeSwap. Experimental results demonstrate that LG consistently identifies trading paths that are as profitable as, or more profitable than, those found by DFS, while incurring comparable gas costs. Evaluations on Uniswap V2 token graphs across two temporal snapshots further validate LG’s performance. Although LG exhibits exponential runtime growth with respect to graph size in empirical tests, it remains viable for practical, real-world use cases. Our findings underscore the potential of the LG algorithm for industrial adoption, offering tangible benefits to traders and market participants in the DeFi space.

Complexity vs Empirical Score

  • Math Complexity: 7.0/10
  • Empirical Rigor: 6.0/10
  • Quadrant: Holy Grail — high math complexity, high empirical rigor

Why this score: The paper presents a novel line-graph algorithm with a theoretical complexity analysis (O(|E| · (P di^2 - 2|E|))) and empirical validation on real DEX data (Uniswap V2, ~200 pools), comparing profitability and gas costs against DFS. It bridges theoretical graph algorithms with practical DeFi applications, demonstrating both advanced mathematics and data-driven results.

Research Flowchart

  flowchart TD
  A["Research Goal: Identify Optimal Routing Paths in DEXs"] --> B["Data Input: Uniswap V2<br>Token Graphs<br>(Two Temporal Snapshots)"]
  B --> C["Methodology: Line-Graph (LG)<br>vs. Baseline (DFS)"]
  C --> D["Computational Process:<br>Liquidity Routing &<br>Gas Cost Calculation"]
  D --> E["Outcome 1: LG finds paths<br>as profitable or more profitable<br>than DFS"]
  D --> F["Outcome 2: LG incurs<br>comparable gas costs"]
  E --> G["Conclusion: LG viable for<br>industrial adoption in DeFi"]
  F --> G

Evidence Card

What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card

Proposes

The paper proposes a novel line‑graph‑based algorithm (LG) for efficiently detecting optimal trading paths across DEXs.

Source sentence
This paper presents a novel line-graph-based algorithm (LG) designed to efficiently discover profitable trading routes within DEX environments.

Assumes 4

  • Tokens are represented as nodes and each liquidity pool creates directed edges with stored reserve information. model
    Source sentence
    In G(V, E, R), each edge eij stores the reserve information of token vi and vj in the directed liquidity pool (vi, vj) as a tuple (ri, rj).
  • The source token is designated as v1 and an extra source vertex (O, v1) is added to the line graph. model
    Source sentence
    We assume that v1 is the source token that we will consider and (v1, vn1), (v1, vn2), ..., (v1, vnk) are its neighbour link vertices in L(G). Now, we add an extra node called (O, v1) to L(G)...
  • No arbitrage loops are present when the algorithm terminates. market
    Source sentence
    If there is no arbitrage loop, then the line-graph-based algorithm is very similar to the Bellman‑Ford algorithm...
  • Gas fees are proportional to routing path length, so shorter paths imply lower fees. execution
    Source sentence
    However, we can still reflect the gas fee cost of the two algorithms by comparing the corresponding optimal routing path length because the shorter a routing path is, the less the gas fee.

Data

  • Uniswap V2 token graph · Uniswap crypto-onchain public
    October 30, 2022 and October 30, 2023 · around 100 tokens and 200 liquidity pools
    Source sentence
    testing on a token graph with around 100 tokens and 200 liquidity pools from Uniswap V2 on October 30, 2022 and 2023, respectively.

Costs

Not modeled A trading or execution result is reported without costs.

Source sentence
In the above statistical analysis, we didn’t take gas fees into consideration which is measured in Ether.

Finds 5

  • The line‑graph‑based algorithm outperforms DFS in profitability, beating DFS by more than 50% in about 40% of token pairs and matching it in the remaining 60%. performance
    Source sentence
    by selling tokens worth 10,000 dollars, our routing algorithm outperforms the DFS algorithm by more than 50% in around 40% cases, and both algorithms have the same performance in the remaining 60% cases
  • Across all 8,742 token pairs, the LG algorithm yields an equal or higher number of target tokens than DFS, with target tokens almost 5 times higher on average. performance
    Source sentence
    the line‑graph‑based algorithm obtains an equal or higher number of target tokens compared to the DFS algorithm when running them in all 8742 pairs. In all token pairs, the number of received target tokens by running the line‑graph‑based algorithm is almost 5 times higher than that by running the DFS algorithm.
  • LG and DFS have comparable gas‑fee costs because their routing path lengths are similar for cases where LG outperforms DFS. performance
    Source sentence
    the two algorithms cost almost comparable gas fees in almost all token pairs where lg‑dfs/dfs > 0.001.
  • The average running time of LG is about 0.1 s for a 100‑token graph, much faster than convex‑optimization methods. performance
    Source sentence
    For example, for a graph with 100 tokens, the average running time is about 0.1s. While the time is around 1.5s if we use the convex optimization method.
  • LG exhibits exponential runtime growth with graph size but remains viable for practical real‑world use cases. theoretical
    Source sentence
    Although LG exhibits exponential runtime growth with respect to graph size in empirical tests, it remains viable for practical, real‑world use cases.

Checked by others

No other paper in the archive has been found to support or contradict these findings (compared with 44 related papers). Coverage is partial, so this is neither replication nor refutation.

Cited by 1 paper in the archive

Code

No repository by the authors found in the paper.

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.