{"id":"arxiv/2605.29566","url":"https://arxiv.org/abs/2605.29566","tags":["cs.DS","math.PR"],"score":0,"title":"Sampling Directed Eulerian Tours in $\\widetilde O(m^{3/2})$ Time","domain":"cs.DS","source":"arxiv","authors":["Nima Anari"],"reviews":0,"subject":"cs.DS","summary":"We give a randomized algorithm that samples a nearly uniform Eulerian tour of a directed Eulerian multigraph with $m$ arcs in $\\widetilde O(m^{3/2})$ time. The guarantee is worst-case, applies to arbitrary directed Eulerian multigraphs, and breaks the $mn$-type arborescence-sampling barrier on sparse graphs. The core case is a $2$-in/$2$-out graph. We introduce a new local Markov chain, the flip--repair walk: one step locally splits a tour into two circuits and then chooses uniformly among the local flips that repair the state to one tour. We prove that this walk mixes in nearly linear many…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-28","reactions":{}}