Closing the Complexity Gap for Wheeler Graph Recognition on -NFAs
In the authors' words
Wheeler graph recognition asks whether a directed graph whose arcs are labeled by symbols from a totally ordered alphabet admits a Wheeler order, a total order on its vertices compatible with the labels of arcs and the order of their tails. A -NFA is a nondeterministic finite automaton in which at most transitions with any given label leave each state. For Wheeler graph recognition on -NFAs, Alanko et al. gave a polynomial-time algorithm for , whereas Gibney and Thankachan proved NP-completeness for every fixed . The computational complexity for and remained open. We resolve both open cases by extending the reduction of Gibney and Thankachan with a new encoding of clauses of Not-All-Equal 3-SAT. Specifically, we prove that recognition is NP-complete even for directed acyclic graphs over an ordered binary alphabet with a unique source reaching every vertex and total out-degree at most three at every vertex. Consequently, Wheeler graph recognition on -NFAs is NP-complete for every fixed .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.