← All papers
First page of Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard

Tilen Marc

cs.DM Oct 1, 2026 · v2 math.CO
The main distance formulas, excess amplification and VC-equivalences are formally verified in core Lean 4, with a public repository and no unproved steps.
A wiring diagram is an arrangement of $m$ pseudolines, every two of which cross exactly once. Reading its crossings from left to right encodes it as a reduced word of the permutation $w_0\in S_m$ that reverses $1,\dots,m$, unique up to commutations, 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). The reduction is from Vertex Cover: for every graph $G$ we construct two wiring diagrams at braid-move distance $|D|+2\operatorname{VC}(G)$, where $\operatorname{VC}(G)$ is the vertex cover number of $G$ and the Hamming distance $|D|$ is the number of triples of wires whose triangles are oriented differently. The construction glues copies of a seven-wire gadget whose braid-move distance exceeds its Hamming distance by $2$. Adding a line at infinity transfers the construction to rank-$3$ uniform oriented matroids, where two oriented matroids are adjacent in the mutation graph if their chirotopes differ in one basis; so deciding distance in the mutation graph is NP-complete in rank $3$. An iterate of Rambau's expansion of signotopes amplifies the excess and gives NP-hardness in every fixed rank $r\ge4$, and by duality in every fixed corank at least $3$. The same instances show that flip distance in the higher Bruhat orders $B(n,k)$ is NP-complete for every fixed $k\ge2$.

Whether flip distance in the flip graph of pseudoline arrangements (braid-move distance between wiring diagrams) is NP-hard was an open question from SODA 2024. The same question arises for higher Bruhat orders, rhombic tilings, and mutation graphs of uniform oriented matroids.

The reduction is from Vertex Cover. A seven-wire gadget, whose braid-move distance exceeds its Hamming distance by 2, is glued along vertex blocks. This yields two wiring diagrams at distance |D|+2VC(G). Adding a line at infinity transfers the construction to rank-3 chirotopes, and an iterated lift based on Rambau's expansion amplifies the excess to higher ranks. The main distance formulas and equivalences are machine-checked in core Lean 4.

Braid-move distance and flip distance in B(m,2) are NP-complete. Mutation-graph distance is NP-complete in rank 3 and NP-hard in every fixed rank r≥4 and every fixed corank ≥3. Flip distance in B(n,k) is NP-complete for every fixed k≥2.