{"paper_id":"2504.15809","title":"A Line Graph-Based Framework for Identifying Optimal Routing Paths in Decentralized Exchanges","authors":["Yu Zhang","Yafei Li","Claudio Tessone"],"paper_date":"2025-04-22","paper_type":"methodological","paper_url":"https://arxiv.org/pdf/2504.15809v1","page_url":"https://thequant.space/flowcharts/a-line-graph-based-framework-for-identifying-optimal-routing/","scores":{"empirical_rigor":6,"math_complexity":7,"quadrant":"Holy Grail"},"proposes":{"status":"available","statement":"The paper proposes a novel line‑graph‑based algorithm (LG) for efficiently detecting optimal trading paths across DEXs.","quote":"This paper presents a novel line-graph-based algorithm (LG) designed to efficiently discover profitable trading routes within DEX environments.","summary":"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…","strategy":null},"assumptions":{"status":"available","items":[{"assumption":"Tokens are represented as nodes and each liquidity pool creates directed edges with stored reserve information.","type":"model","stated":"explicit","quote":"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)."},{"assumption":"The source token is designated as v1 and an extra source vertex (O, v1) is added to the line graph.","type":"model","stated":"explicit","quote":"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)..."},{"assumption":"No arbitrage loops are present when the algorithm terminates.","type":"market","stated":"explicit","quote":"If there is no arbitrage loop, then the line-graph-based algorithm is very similar to the Bellman‑Ford algorithm..."},{"assumption":"Gas fees are proportional to routing path length, so shorter paths imply lower fees.","type":"execution","stated":"explicit","quote":"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."}]},"datasets":{"status":"available","items":[{"name":"Uniswap V2 token graph","provider":"Uniswap","kind":"crypto-onchain","access":"public","period":"October 30, 2022 and October 30, 2023","universe":"around 100 tokens and 200 liquidity pools","quote":"testing on a token graph with around 100 tokens and 200 liquidity pools from Uniswap V2 on October 30, 2022 and 2023, respectively."}],"known":[],"sample":{"start":null,"end":null,"market":null,"asset_class":null,"frequency":null},"data_resolution":"daily"},"transaction_costs":{"status":"available","modeled":"no","headline_net_of_costs":null,"detail":null,"quote":"In the above statistical analysis, we didn’t take gas fees into consideration which is measured in Ether.","source":"evidence_card","rule":"R2","candidates":{"front_matter":"unclear","evidence_card":"no","evidence_card_quoted":true},"card_detail":null,"card_quote":"In the above statistical analysis, we didn’t take gas fees into consideration which is measured in Ether.","meaning":"a trading or execution result is reported without costs"},"results":{"status":"available","evaluation_type":"unclear","findings":[{"finding":"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%.","kind":"performance","quote":"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"},{"finding":"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.","kind":"performance","quote":"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."},{"finding":"LG and DFS have comparable gas‑fee costs because their routing path lengths are similar for cases where LG outperforms DFS.","kind":"performance","quote":"the two algorithms cost almost comparable gas fees in almost all token pairs where lg‑dfs/dfs > 0.001."},{"finding":"The average running time of LG is about 0.1 s for a 100‑token graph, much faster than convex‑optimization methods.","kind":"performance","quote":"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."},{"finding":"LG exhibits exponential runtime growth with graph size but remains viable for practical real‑world use cases.","kind":"theoretical","quote":"Although LG exhibits exponential runtime growth with respect to graph size in empirical tests, it remains viable for practical, real‑world use cases."}],"reported_performance":null,"out_of_sample":{"method":"unclear","headline_out_of_sample":null}},"independent_evidence":{"status":"none_found","supports":[],"contradicts":[],"qualifies":[],"compared_with":44,"citations":{"cited_by_in_corpus":1,"by_independent_authors":0,"how_cited":{"used_as_baseline":0,"uses_method_or_data":0,"extends":0,"discusses_findings":0,"mentions":0,"unclassified":1},"independent_papers":[],"scope":"Citations between papers in this corpus only; citations from outside it are not counted."}},"implementation":{"status":"available","public":false,"code_url":null,"note":"No repository presented by the authors as their own was found in the paper. Absence here is not proof that no code exists."},"replication":{"status":"none_found","card":null,"note":"No replication of this paper has been run by thequant.space yet."},"extraction":{"text_source":"fulltext","model":"openai/gpt-oss-120b","version":1,"extracted_at":"2026-11-14T17:40:22Z"},"provenance":{"claims":"Everything here is what the authors state in the paper. Nothing was re-run or reproduced by the platform.","quotes":"Assumptions, datasets, cost detail and findings were extracted by a language model. Every quote is verbatim paper text. Where an item has `support`, \"full\" means every figure in it appears in the quoted sentences and \"partial\" means a figure is stated elsewhere in the paper; items with a figure found nowhere in the paper were discarded.","datasets_known":"datasets.known lists well-known vendors and public datasets by a stable id, found by a dictionary over the full text where the sentence says the data is used; it is independent of the model and covers only names in the dictionary.","flags":"transaction_costs.modeled, results.evaluation_type and results.out_of_sample.method are platform classifications (structured-decision models); see https://thequant.space/score-guide/#penalty-flags","comparisons":"supports / contradicts / qualifies are a language model's reading of two papers' quoted findings, restricted to closely related papers that share no author. They are pointers to read, not verified replications, and coverage is partial.","implementation":"code_url is a repository the paper itself presents as its own (rule-scored, ambiguous cases judged by a model), checked for liveness when it was recorded."},"docs":"https://thequant.space/agents/"}