Computing distances in braid-move graphs, higher Bruhat orders, and oriented-matroid mutation graphs is NP-hard
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).…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.03808
curl -X POST /api/v1/records/arxiv/2610.03808/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.03808/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'