Wheeler Graphs and Wheeler Languages

We refer the reader to [52] for basics on automata theory.

Gagie, Manzini, and Sirén in [35] showed a natural way to extend the co-lexicographic order of strings to labeled graphs. The idea is simple: let us focus on the class of labeled graphs for which there exists a total order of the nodes that is propagated along pairs of equally-labeled transitions, further requiring that pairs of nodes whose incoming labels differ are sorted consistently with the underlying total order of $\mathrm{\Sigma }$. Due to the fact (as shown next) that these graphs generalize the celebrated Burrows-Wheeler transform [16] (BWT for short), the authors of [35] decided to call such a class Wheeler graphs. More formally:

In this manuscript it will be useful to adapt the above definition to finite automata, in order to study the class of regular languages recognized by automata whose transition relation is a Wheeler graph.

An example of a WDFA is presented in Figure 1 (left). In the same figure (right) we show a very insightful representation of Wheeler automata, called the bipartite representation: we duplicate states in two columns following any Wheeler order of the automaton, and we draw edges from left to right (in Figure 1, for clarity only edges labeled with $c$ are shown). In this representation, Wheeler Axiom W1 translates to the fact that nodes are sorted by increasing incoming letter, and Wheeler Axiom W2 to the fact that no same-letter edges cross. Most properties, algorithms, and data structures on Wheeler graphs can be easily understood by keeping in mind this representation.

Of particular interest for this survey is the class of Wheeler languages:

As a matter of fact, nondeterminism is not important in Definition 5. As proved in [3] (we will come back to this in Section 4), WDFA and WNFA have the same expressive power: both such classes of finite automata recognize precisely the class of Wheeler languages.

The following considerations hold both for Wheeler graph and Wheeler automata, so we state them only for the latter class of combinatorial objects.

First, we observe that the automata for which there exists a total order satisfying Axiom W2 correspond to the class of totally-sortable Ordered Automata, studied by Shyr and Thierrin in 1974 [53]. In that article, the authors showed that the languages recognized by such automata are star-free; in particular, it follows that all Wheeler languages are star-free. As discussed in this manuscript, by imposing the additional constraint on nodes with in-degree equal to zero and the additional Axiom W1, the work [35] unveiled a restricted class of Ordered Automata (the Wheeler automata) possessing a large number of extremely interesting properties.

Also observe that a consequence of Wheeler Axiom (W1) is that $𝒜$ is input-consistent, that is all transitions entering a given state $q^{\prime }\in Q$ must have the same label: if $q^{\prime }\in \delta (q,a)$ and $q^{\prime }\in \delta (p,b)$, then $a=b$. Therefore a function $\lambda :Q\to \mathrm{\Sigma }$ that labels each state with the unique label of its incoming edges, can be introduced. For the initial state $s$, the only one without incoming edges, we set $\lambda (s)=\mathrm{\#}\notin \mathrm{\Sigma }$, stipulating that $\mathrm{\#}\prec a$, for all $a\in \mathrm{\Sigma }$. Observe that this simplifies the definition of Wheeler automata in that, by replacing $a$ and $b$ with $\lambda (p^{\prime })$ and $\lambda (q^{\prime })$ in Definition 4, we no longer need to require that states with in-degree equal to zero are smaller than states with in-degree strictly larger than zero. We decided to adopt the formulation of Definitions 3 and 4 since it is closer to the one originally defined in [35].

For a fixed-sized (constant) alphabet, requiring an automaton to be input-consistent is not computationally demanding. In fact, given an NFA $𝒜=(Q,s,\delta ,F)$ we can build an equivalent, input-consistent one just by creating, for each state $q\in Q$, at most $|\mathrm{\Sigma }|$ copies of $q$, that is, one for each different incoming label of $q$. This operation can be performed in $O\left(|Q|\cdot |\mathrm{\Sigma }|\right)$ time.

Wheeler graphs extend the suffix array [45], the Burrows-Wheeler Transform [16] and Ferragina and Manzini’s FM-index [34] from strings to graphs. Following [35], we now show how to encode Wheeler graphs using a small number of bits. Consider the automaton in Figure 1. We store the following strings:

• $\mathrm{■}$

  The string $\mathrm{𝙻𝙰𝙱}=adcccfcf$ is obtained by concatenating the labels of all edges leaving $s$, the labels of all edges leaving $q_1$, the labels of all edges leaving $q_2$, and so on. If a node has multiple outgoing edges, the corresponding labels are sorted in alphabetic order.

• $\mathrm{■}$

  The string $\mathrm{𝙾𝚄𝚃}=10010101001001$ is obtained by storing in unary the outdegree of $s$, the outdegree of $q_1$, the outdegree of $q_2$, and so on. The outdegrees are $2$, $1$, $1$, $2$, $2$, $0$.

• $\mathrm{■}$

  The string $\mathrm{𝙸𝙽}=11010010010100$ is obtained by storing in unary the indegree of $s$, the indegree of $q_1$, the indegree of $q_2$, and so on. The indegrees are $0$, $1$, $2$, $2$, $1$, $2$.

• $\mathrm{■}$

  The bit array $\mathrm{𝙵𝙸𝙽}=011001$ remembers which states are final: $s$ is not final, $q_1$ is final, $q_2$ is final, and so on.

Let $e=|\delta |$ be the number of transitions in the NFA, $n=|Q|$ be the number of nodes and $\sigma =|\mathrm{\Sigma }|$ be the size of the alphabet. We can store $\mathrm{𝙻𝙰𝙱}$ in $e\log \sigma$ bits, $\mathrm{𝙾𝚄𝚃}$ in $e+n$ bits, $\mathrm{𝙸𝙽}$ in $e+n$ bits and $\mathrm{𝙵𝙸𝙽}$ in $n$ bits. It turns out that these sequences provide a compact encoding of the Wheeler graphs that extends the Burrows-Wheeler transform from strings to Wheeler automata. Let us show how we can use these sequences to retrieve the automaton. By using $\mathrm{𝙻𝙰𝙱}$ and $\mathrm{𝙾𝚄𝚃}$, we infer that $s$ has two outgoing edges labeled $a$ and $d$, $q_1$ has an outgoing edge labeled $c$, $q_2$ has an outgoing edge labeled $c$ , $q_3$ has two outgoing edges labeled $c$ and $f$, $q_4$ has two outgoing edges labeled $c$ and $f$, and $q_5$ has no outgoing edges. Now we sort the character in $\mathrm{𝙻𝙰𝙱}$, obtaining $accccdff$. From Wheeler property (W1) and $\mathrm{𝙸𝙽}$ we infer that $s$ has no incoming edges, $q_1$ has an incoming edge labeled $a$, $q_2$ has two incoming edges both labeled $c$, $q_3$ has two incoming edges both labeled $c$, $q_4$ has an incoming edge labeled $d$, and $q_5$ has two incoming edges labeled $f$. By using the bipartite representation of Figure 1, we can retrieve the whole set of edges. For example, consider character $c$. We know that there are outgoing edges labeled $c$ from $q_1$, $q_2$, $q_3$, $q_4$, and we know that there are incoming edges labeled $c$ from $q_2$ (two edges) and $q_3$ (two edges), so since same-letter edges cannot cross we conclude that the edges labeled $c$ are $(q_1,q_2,c)$, $(q_2,q_2,c)$, $(q_3,q_3,c)$, $(q_4,q_3,c)$. Lastly, we retrieve the set of all final states by using $\mathrm{𝙵𝙸𝙽}$.

Not only Wheeler graphs can be encoded in a small number of bits as described above, but they also support efficient pattern matching queries on the automaton’s paths (equivalently, on the language recognized by the automaton). Consider the following pattern matching problems (where we assume, without loss of generality, that every state can reach a final state):

1. 1.

   Given $\alpha \in {\mathrm{\Sigma }}^{\ast }$, decide whether $\alpha$ is accepted by the automaton $𝒜$ (that is, decide, whether $\alpha \in ℒ(𝒜)$).

2. 2.

   Given $\alpha \in {\mathrm{\Sigma }}^{\ast }$, decide whether $\alpha$ occurs on the paths of the automaton $𝒜$ (that is, decide whether there exist ${\gamma }_1,{\gamma }_2\in {\mathrm{\Sigma }}^{\ast }$ such that ${\gamma }_1\alpha {\gamma }_2\in ℒ(𝒜)$).

For example, in Figure 1, the string $\alpha =cccf$ is not accepted by the automaton, but it occurs in the automaton (there is a path from $q_4$ to $q_5$ labeled with $\alpha$).

The compressed representation of a Wheeler graph allow solving both problems efficiently. First, as observed in [35], from the bipartite representation of a graph we can deduce path-coherence: if we start from an interval of consecutive nodes in Wheeler order, we consider a character $c$, and we follow all edges labeled with $c$ from those nodes, we end up in another (possibly empty) interval of consecutive nodes. For example, if we start from $\{q_1,q_2,q_3,q_4\}$ and we follow all edges labeled $c$, we end up in $\{q_2,q_3\}$.

This property implies that we can solve both pattern matching queries above listed in a linear number of steps. For the first problem, we start from the interval of states $\{s\}$, and for the second problem we start from the whole set of states $Q$. To update an interval by following the edges labeled with $c$, we augment the compressed representation of a Wheeler automaton with compressed data structures that support efficient rank/select queries, thus extending the FM-index from strings to Wheeler automata. This leads to the following result:

Wheeler graphs are therefore a very convenient class of graphs, because they support pattern matching in linear time (for constant alphabets) within compressed space, while on arbitrary graphs pattern matching cannot be solved in subquadratic time (assuming that the orthogonal vector hypothesis is true) [32]. At the same time, the class of Wheeler graphs subsumes all previous extensions of the Burrows-Wheeler transform and the FM-index, including labeled trees [33], circular strings [46, 40] and de Bruijn graphs [14]. Wheeler graphs also inherit compressibility properties of the Burrows-Wheeler transform. For example, tunneling, a method for identifying blocks that capture some redundancy of the BWT [8], can be extended to Wheeler graphs [4].

Some more complicated pattern matching problems require more advanced data structures. A typical example is the problem of computing matching statistics: given an automaton $𝒜$, and a string $\alpha$, determine for every $1\le i\le |\alpha |$ the longest suffix ${\alpha }_i$ of $\alpha [1,i]$ that occurs in $𝒜$. For example, in Figure 1, if $\alpha =accfdf$, we have ${\alpha }_1=a$, ${\alpha }_2=ac$, ${\alpha }_3=acc$, ${\alpha }_4=ccf$, ${\alpha }_5=d$, ${\alpha }_6=df$. On strings, this problem can be solved by exploiting the FM-index and the longest common prefix array [49]. In [19], the notion of longest common prefix array was extended to Wheeler DFA. The idea is to consider the smallest and the largest string reaching each state. For example, in Figure 1, the smallest string reaching $q_2$ is $ac$ and the largest string reaching $q_2$ is $\mathrm{\dots }ccccc$ (these strings can be read by starting from $q_2$, following edges in a backward fashion until either reaching the source $s$ or a loop, and finally reversing the obtained string). More generally, we proceed as follows. Let $𝒜$ be a Wheeler DFA with $n$ nodes, in which the $i$-th state in the Wheeler order is $q_i$. We define $2n$ strings: ${\gamma }_1$ is the smallest string reaching $q_1$, ${\gamma }_2$ is the largest string reaching $q_1$, ${\gamma }_3$ is the smallest string reaching $q_2$, ${\gamma }_4$ is the largest string reaching $q_2$, and so on. We define the array $\mathrm{𝖫𝖢𝖲}[2,2n]$ such that $\mathrm{𝖫𝖢𝖲}[i]$ is the length of the longest common suffix between ${\gamma }_{i-1}$ and ${\gamma }_i$. Then, it can be shown that, for every $2\le i\le 2n$, either $\mathrm{𝖫𝖢𝖲}[i]$ is infinite or its value is less than $2n$ [19, 5]. This implies that $\mathrm{𝖫𝖢𝖲}$ can be stored using at most $O(n\log n)$ bits.

The LCS array of a Wheeler DFA supports computing matching statistics efficiently:

Storing a Wheeler DFA requires only $e\log \sigma (1+o(1))+O(e)$ bits (Theorem 6), so storing the LCS array using $O(n\log n)$ bits may require significantly more space than storing the automaton itself, if the alphabet and the numbers of edges are small. Similarly to the string case, it is possible to design a sampling mechanism for the LCS array that allows better space-time trade-offs. The key idea is to store a range minimum query data structure on the LCS array (which only requires $O(n)$ bits) and sample $O(n/\log n)$ entries of the LCS array in such a way that, by solving range minimum queries, it is possible to retrieve each entry of the LCS array in $O(\log n)$ steps. This leads to the following result.

Given the interesting properties of Wheeler automata discussed in the previous section, a natural language-theoretic question is: which languages are recognized by Wheeler DFA (WDFA for brevity) and Wheeler NFA (WNFA for brevity)? In this section we consider the class of Wheeler Languages, that is the class of languages recognized by a WNFA or, equivalently as we shall see in Theorem 10, by a WDFA.

A first observation is that the Wheeler local conditions of Definition 4 are equivalent, on DFA, to a more global condition expressed in terms of the sets $I_q$ of words reaching a state $q$. If $𝒟$ is a DFA and $\prec$ is a (strict) order of the alphabet, we can define a (strict) partial order on its states by stipulating, for $q\ne q^{\prime }$, that

The (in general) partial order indicates whether $𝒟$ is Wheeler in the following sense:

Using the previous lemma we easily see that we can enlarge the class of WDFA to non input-consistent automata, without changing the class of recognized languages, by defining a WDFA as a DFA in which the initial state $s$ has no in-going edges and the order $𝒟$ is total. In the following we will freely use the new enlarged class of WDFA.

Notice that if is total, then we can decide whether by simply checking the relative co-lexicographical order of any two strings $\alpha \in I_q$ and $\beta \in I_{q^{\prime }}$. An easy consequence of this is that, if $𝒟$ is a WDFA and ${({\alpha }_n)}_{n\in \omega }$ is a co-lexicographically (strictly) monotone sequence of words in $\text{Pref}(ℒ(𝒟))$, then for some state $q$ of $𝒟$, ${({\alpha }_n)}_{n\in \omega }$ will eventually belong to $I_q$. This fact helps us to locate Wheeler languages among sub-regular languages by testing it against a very well-known class: the star-free languages. Languages in this class can be described by regular expressions constructed from the letters of the alphabet, the empty word, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. We can indeed prove that a Wheeler language is always star-free. To see this we recall that a characterization of the star-free languages says that a language $ℒ$ is star-free if and only if there exists $n$ such that for all $\alpha ,\beta ,\gamma \in {\mathrm{\Sigma }}^{\ast }$ it holds:

Suppose now that a language $ℒ$ is Wheeler, that is, there exists a WDFA $𝒟$ recognizing $ℒ$. Consider a sequence of words of the form ${(\alpha {\beta }^k)}_{k\in \omega }$: this sequence is always monotone (increasing or decreasing depending on whether $\alpha ⪯\alpha \beta$ or $\alpha ⪰\alpha \beta$). Hence, by the Wheelerness of $𝒟$, there must exist a $𝒟$-state $q$ and $n\in \mathbb{N}$ such that, for all $m\ge n$, $\alpha {\beta }^m$ belongs to $I_q$. Condition (2) easily follows.

As a natural next step we present below a characterization of the class of Wheeler languages, both from the language as well as from the accepting-automata view points.

The former can be given by making an appeal to the celebrated Myhill-Nerode equivalence ${\equiv }_{ℒ}$. To this end we say that an equivalence relation $\equiv$ over an ordered set $(A,\le )$ is convex if whenever $a\le b\le c$ and $a\equiv c$, we also have $b\equiv a$. Consider the following “convex refinement” ${\equiv }_{ℒ}^c$ of ${\equiv }_{ℒ}$. For all $\alpha ,\beta \in \text{Pref}(ℒ)$ we say that $\alpha {\equiv }_{ℒ}^c\beta$ if and only if

where $end(\alpha )$ is the final character of $\alpha$ when $\alpha \ne ϵ$, and $ϵ$ otherwise.

The following theorem shows that the convex equivalence ${\equiv }_{ℒ}^c$ plays exactly the role of the Myhill-Nerode equivalence when referred to Wheeler Languages.

As a consequence of Theorem 10 we get an elegant further characterization of Wheeler languages by considering, again, monotone sequences. The condition expresses the fact that they turn out being eventually trapped in a single state, this time of the minimum DFA for the language:

Proof Sketch: to see that the condition is sufficient we use Theorem 10 and suppose, by contraposition, ${\equiv }_{ℒ}^c$ has an infinite number of classes. Then, there is a single ${\equiv }_{ℒ}$-class which is partitioned into an infinite number of ${\equiv }_{ℒ}^c$-classes and we can single out a monotone sequence ${({\beta }_i)}_{i\in \omega }$ (say, increasing) whose elements are pairwise non ${\equiv }_{ℒ}^c$-equivalent words. By discarding at most a finite number of them, we may suppose that all ${\beta }_i$ are not only ${\equiv }_{ℒ}$-equivalent, but also end with the same letter. For any $i\in \omega$, since ${\beta }_i{\not\equiv }_{ℒ}^c{\beta }_{i+1}$, by definition of ${\equiv }_{ℒ}^c$, there must exists ${\eta }_i$ with ${\beta }_i\prec {\eta }_i\prec {\beta }_{i+1}$ and ${\eta }_i{\not\equiv }_{ℒ}{\beta }_i$. But then the monotone sequence

is never trapped in a single ${\equiv }_{ℒ}$ class.

The condition is also necessary, since a monotone sequence gets trapped in any WDFA recognizing $ℒ$, it gets a fortiori trapped in the minimum DFA ${𝒟}_{ℒ}$ recognizing the language (even if ${𝒟}_{ℒ}$ is not Wheeler).

Using Corollary 11 one can show that Wheeler languages are closed under a few classical operations while other (even very simple) compositions of Wheeler languages do not maintain Wheelerness.

We now consider the problem of characterizing Wheeler languages using automata. For star-free languages we know that a combinatorial property of the minimum DFA – i.e. being counter-free – characterizes membership in that class and we can give a similar result also for the Wheeler class. However, let us first first notice that being Wheeler for a language $ℒ$ does not necessarily imply Wheelerness for its minimum DFA ${𝒟}_{ℒ}$. Consider the DFA $𝒟$ depicted in Figure 2. If $⪯$ is the alphabetical order on $\mathrm{\Sigma }$, since $a\prec ab\prec ac$ and since $a,ac\in I_{q_1},ab\in I_{q_2}$, it follows that states $q_1,q_2$ are -incomparable. Hence $𝒟$ is not Wheeler, even though $ℒ(𝒟)$ is Wheeler. To see this just consider the DFA ${𝒟}^{\prime }$ obtained from $𝒟$ by duplicating state $q_1$ into $q_{1,a}$ and $q_{1,c}$ and by defining $\delta (s,a)=q_{1,a}$, $\delta (s,c)=q_{1,c}$, and $\delta (q_{1,a},b)=\delta (q_{1,c},b)=q_2$. In ${𝒟}^{\prime }$ the order is total so that ${𝒟}^{\prime }$ is a WDFA recognizing $ℒ(𝒟)$.

Hence, in order to decide whether a language $ℒ$ is Wheeler we cannot simply rely on the Wheelerness of its minimum DFA $D_{ℒ}$. Yet, a simple combinatorial property of characterizes Wheelerness. Even though there are Wheeler languages in which is not total, in such cases -incomparability must be limited to special kind of pairs. To illustrate this consider again the minimum DFA in Figure 2, this time with respect to the following order on the alphabet: $a\prec c\prec b\prec d\prec e$. The following theorem tells us that the language recognized is not Wheeler, because the two nodes $q_3,q_4$ are not only -incomparable but are also infinitely entangled, since they are the starting point of two equally labeled cycles – this was not so using the alphabetical order since in that case.

Intuitively speaking, $ℒ$ is not Wheeler if and only if there is no finite splitting of the states of ${𝒟}_{ℒ}$ that can possibly make ${𝒟}_{ℒ}$ Wheeler.

As an easy corollary of the previous theorem we see at once that if the minimum trimmed DFA $D_{ℒ}$ accepting a regular language $ℒ$ contains three equally labeled cycles starting from three different states $q_1,q_2,q_3$, then $ℒ$ cannot be Wheeler. Indeed, suppose w.l.o.g. that the cycles are labeled by the word $\gamma$ and ${\alpha }_1\prec {\alpha }_2\prec {\alpha }_3$ are non empty words, different from $\gamma$, reaching $q_1,q_2,q_3$, respectively. Then two out of the three among ${\alpha }_1,{\alpha }_2,{\alpha }_3$ must lie on the same side of $\gamma$, say ${\alpha }_1\prec {\alpha }_2\prec \gamma$. Then ${\alpha }_1\gamma \prec {\alpha }_2\gamma \prec {\alpha }_1{\gamma }^2$ with ${\alpha }_1\gamma ,{\alpha }_1{\gamma }^2\in I_{q_1}$ and ${\alpha }_2\gamma \in I_{q_2}$, showing that $q_1,q_2$ are -incomparable and $ℒ$ is not Wheeler by Theorem 13.

A similar combinatorial condition on the minimum DFA will be used in the following to find efficient algorithms for analyzing the “level of Wheelerness” of regular languages.

Finally, we consider the problem of constructing the minimum WDFA for a Wheeler language. Consider, for any $n\in \mathbb{N}$, the language whose minimum (input-consistent) DFA $D_n$ is depicted in Figure 3. This language is finite, hence it is Wheeler – in fact, for any order of the alphabet. However, if we consider the standard alphabetical order, $D_n$ is not Wheeler, because states $q_1,q_2$ cannot be ordered by since $acac\prec bc\prec bcbc$ with $acac,bcbc\in I_{q_2}$, $bc\in I_{q_1}$. However, Theorem 10 says that every Wheeler language has a unique state-minimum WDFA, whose set of states is the set of equivalence classes of ${\equiv }_{ℒ}^c$, while initial and final states are defined as in the regular case. For the language in Figure 3 it can be proved that the state-minimum WDFA has a number of states which is exponential in the number $n$ of states in the minimum (input-consistent) DFA $D_n$ (see [47] for further consideration on the relative size of minimum DFA and WDFA for the same language). We will discuss algorithmic solutions to the problem of computing such minimum WDFA in Section 7.4.

We now move to algorithmic problems on Wheeler graphs. We first discuss the computational complexity of the natural problem of determining if a given edge labeled graph is a Wheeler graph. The following hardness result by Gibney and Thankachan implies the computational intractability of this problem.

We describe a simple reduction that requires a source vertex with a large degree, but demonstrates many of the same techniques used to prove the full statement of Theorem 21. We first introduce the Betweenness Problem, proven NP-complete by Opatrný [50].

We call the set of triples $X$ betweenness constraints. For example, an instance of the Betweenness problem is $(n=6,X=\{(3,2,5),(1,5,2),(4,5,6),(2,6,4)\})$. The permutation resulting in the ordering $1,4,5,6,2,3$ would satisfy every triple in $X$. The permutation resulting in the ordering $1,2,3,4,5,6$ would violate the triples $(3,2,5)$, $(1,5,2)$ and $(2,6,4)$.

Given an instance $(n,X)$ of the Betweenness Problem we construct a labeled graph $G=(Q,\mathrm{\Sigma },E)$ as follows:

• $\mathrm{■}$

  We create a single source vertex $s$.

• $\mathrm{■}$

  We next create a set of $n$ vertices, denoted $v_i^1$ for $i\in [1,n]$ and the labeled edges $(s,v_i^1,a)$ for $i\in [1,n]$.

• $\mathrm{■}$

  Next, for $j\in [2,|X|]$, $i\in [1,n]$, we create the vertex set $v_i^j$ and the labeled edges $(v_i^{j-1},v_i^j,a)$.

Observe that in the definition of a total vertex order for a Wheeler graph, the vertex $s$ must be ordered first, followed by some ordering of $v_1^1$, $v_2^1$, $\mathrm{\dots }$, $v_n^1$, immediately followed by the same order applied to $v_1^2$, $v_2^2$, $\mathrm{\dots }$, $v_n^2$. In fact, the vertices described above must have an ordering of the form

for some permutation $\pi$. Otherwise, there would exist some $i^{\prime }$ and $i$ such that but , contradicting Wheeler graph axiom W2.

Next, we add the following betweenness constraint gadgets. We order $X$ arbitrarily. Iterating through $X$, consider $(a,b,c)$ as the $j^{th}$ betweenness constraint. We add the new vertices $w_1^j$, $w_2^j$, and $w_3^j$ and the labeled edges $(v_a^j,w_1^j,b)$, $(v_a^j,w_2^j,b)$, $(v_b^j,w_2^j,b)$, $(v_c^j,w_2^j,b)$, and $(v_c^j,w_3^j,b)$. See Figure 6 for an example with $n=6$ and three betweenness constraint gadgets.

The key property enforced by the betweenness constraint gadget is as follows. If the $j^{th}$ constraint is $(a,b,c)$, then, for the total order on the vertices to satisfy Wheeler Axiom W2, the vertex $v_b^j$ must be ordered between $v_a^j$ and $v_c^j$. For non-example, if we must have have due to the edges $(v_b^j,w_2^j,b)$, $(v_a^j,w_1^j,b)$, and $(v_c^j,w_3^j,b)$. However, we also have the edges $(v_a^j,w_1^j,b)$ and $(v_c^j,w_2^j,b)$ where and , violating Wheeler axiom W2. A similar argument holds in all cases where $v_b^j$ is not ordered between $v_a^j$ and $v_c^j$. Taking the bipartite view of the graph from Section 2, this is equivalent to the only ordering of the vertices allowing for non-crossing dashed edges labeled $2$ being one where the $v_b^j$ is positioned between $v_a^j$ and $v_c^j$. See Figure 7. By drawing similar figures, one can confirm that the only possible orderings for the vertices in which blue dashed lines do not cross are , and , .

We note here that if the single source restriction is lifted, then by making each $v_i^1$ for $i\in [1,n]$ a source vertex, the reduction implies NP-completeness for the case where the total degree of each vertex is at most three.

We next discuss how the complete statement of Theorem 21 is obtained in the single source case. An examination of Opatrný’s NP-completeness proof of the Betweenness Problem shows that not all permutations of $\{1,2,\mathrm{\dots },n\}$ have to be under consideration for NP-hardness of the Betweenness problem to hold. Only a subset of permutations allowing for pivoting of elements around some central value $X$, along with some potential placement of some additional elements have to be under consideration for the problem to be NP-hard. This observation guides a reduction from Not-All-Equal SAT (NAESAT) that utilizes a tree structure rather than a single source with degree $n$, which previously had allowed for all permutations of $v_1^1$, $\mathrm{\dots }$, $v_n^1$. An example of this tree structure is shown in Figure 8.

In more detail, in the Not-All-Equal Boolean Satisfiability (NAESAT) Problem, one needs to find a satisfying Boolean assignment in which each clause has both a true literal and a false literal. Like in Opatrný’s reduction from NAESAT to the Betweenness Problem, in the reduction from NAESAT to Wheeler graph recognition, each variable $x_i$ is represented by two elements (or vertices) $x_i$ and $\overline{x_i}$. Betweenness constraints force these to be in one of two orderings or corresponding to either a true or false assignment to $x_i$. Each clause requires one element (represented with a vertex) and two additional betweenness constraints. After constructing the tree structure, all betweenness constraints can be enforced in the same manner as in the reduction from the Betweenness Problem to Wheeler graph recognition. We refer the readers to [36] for details.

A natural question is whether the brute force $\mathrm{\Omega }(|V|!)$ approach of testing all permutations of vertices is necessary. A more efficient exponential time algorithm arises from combining that a Wheeler graph can be represented using $2(|E|+|V|)+|E|+|\mathrm{\Sigma }|\log |E|+o(|V|+|E|\log |\mathrm{\Sigma }|)$ bits (while supporting efficient graph transversal) [35] and that graph isomorphism can be checked in $2^{\sqrt{|V|}+O(1)}$ time [7]. Hence, we can enumerate all potential Wheeler graphs for a given $|V|$, $|E|$, and $\mathrm{\Sigma }$ and check whether the resulting graph is isomorphic to the input graph. This approach yields a $2^{|E|\log |\mathrm{\Sigma }|+O(|V|+|E|)}$ time algorithm. Subsequent work by Chao et al. on the Wheeler graph recognition provides an alternative approach based on a Satisfiability Modulo Theory (SMT) solver, which experimentally outperforms the above proposed exponential time solution [18].

Gibney and Thankachan [36] also demonstrate that the following optimization variant is APX-hard: given a graph $G=(Q,\mathrm{\Sigma },E)$ find a minimum cardinality subset of edges $E^{\prime }\subseteq E$ such that $(Q,\mathrm{\Sigma },E\setminus E^{\prime })$ is a Wheeler graph. Here, the objective value is taken as $|E^{\prime }|$. This problem is called Wheeler Graph Violation (WGV). The APX-hardness result implies that there does not exist a polynomial-time approximation scheme (PTAS) for this problem under the assumption that P $\ne$ NP. The proof is through a reduction from the Feedback Arc Set Problem, that is, given a directed graph $G=(V,E)$, determine a minimum cardinality subset of edges $E^{\prime }\subset E$ such that $(V,E\setminus E^{\prime })$ is a directed acyclic graph. This same reduction implies that, under the Unique Games Conjecture, it is NP-hard to find a solution to WGV that is within a constant factor of optimal for any constant $C>0$ [37].

Further hardness results in this vein include work by D’Agostino et al. [30] that proves that deciding whether a language of an NFA is a Wheeler language is PSPACE-complete. The same authors demonstrate that the problem of determining whether there exists an alphabet order that causes a DFA to become Wheeler is NP-complete [29]. As a fine-grained complexity result, a quadratic lower bound condition on the Strong Exponential Time Hypothesis (SETH) for the problem of determining if a DFA recognizes a Wheeler language is provided by Becker et al. [11], along with an algorithm having a time complexity matching this lower bound. Section 7.3 provides more details on this last result.

As discussed in Section 5, the problems of (i) deciding whether a given NFA is a WNFA and (ii) finding a Wheeler order for a given WNFA are NP-complete. Subsequent research, however, has shown that this is not the end of the story: as we show next, problems (i) and (ii) can still be solved in polynomial time for a strict superclass of the DFA, and can actually be solved in polynomial time for all NFA by slightly changing the Wheeler order definition (i.e. moving to preorders, a solution which preserves the ability to index the WNFA).