Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard
Abstract
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 w0∈ Sm that reverses 1,…,m, unique up to commutations, and a braid move σiσi+1σi↔σ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|+2VC(G), where 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≥4, 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≥2.
Related
- Embracing exchange sequences and oriented matroid polyhedron diameter
- On Cayley Graphs of Skew Braces and Their Distances
- Smooth Isotropic Covariance Functions on Metric Graphs via Polyharmonic Resistance Distances
- Distances in the collinearity graphs of geometries related to simplex codes
- Oriented point-cloud varifolds for estimating the perimeter and computing its Wasserstein gradient flow
BibTeX
@misc{marc2026computing,
title = {{Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard}},
author = {Tilen Marc},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03808},
eprint = {2610.03808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03808},
}
RIS
TY - UNPB
TI - Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard
AU - Tilen Marc
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.03808
UR - https://arxiv.org/abs/2610.03808
AB - 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∈ S_m that reverses 1,…,m, unique up to commutations, and a braid move σ_iσ_i+1σ_i↔σ_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|+2VC(G), where 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≥4, 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≥2.
ER -