{"id":"arxiv/2610.03808","url":"https://arxiv.org/abs/2610.03808","tags":["cs.DM","math.CO"],"score":0,"title":"Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard","domain":"cs.DM","source":"arxiv","authors":["Tilen Marc"],"reviews":0,"subject":"cs.DM","summary":"A reduced word of the longest permutation $w_0\\in S_m$, taken up to commutations, encodes a wiring diagram of $m$ pseudolines, and a braid move $σ_iσ_{i+1}σ_i\\leftrightarrowσ_{i+1}σ_iσ_{i+1}$ flips one of its triangles. We prove that deciding whether two wiring diagrams are within a given braid-move distance is NP-complete. Equivalently, deciding flip distance is NP-complete in the higher Bruhat order $B(m,2)$, for triangle flips of marked arrangements of pseudolines, and for rhombic tilings of a $2m$-gon; this answers an open question on flip graphs of pseudoline arrangements (SODA 2024).…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}