View source for Lexicographic breadth-first search

In [[computer science]], '''lexicographic breadth-first search''' or Lex-BFS is a [[linear time]] algorithm for ordering the [[Vertex (graph theory)|vertices]] of a [[Graph theory|graph]]. The algorithm is different from a [[breadth-first search]], but it produces an ordering that is consistent with breadth-first search.

The lexicographic breadth-first search algorithm is based on the idea of [[partition refinement]] and was first developed by {{harvs|first1=Donald J.|last1=Rose|first2=Robert E.|last2=Tarjan|author2-link=Robert Tarjan|first3=George S.|last3=Lueker|year=1976|txt}}. A more detailed survey of the topic is presented by {{harvtxt|Corneil|2004}}.
It has been used as a subroutine in other graph algorithms including the recognition of [[chordal graph]]s, and optimal [[graph coloring|coloring]] of [[distance-hereditary graph]]s.

==Background==
The [[breadth-first search]] algorithm is commonly defined by the following process:
*Initialize a [[Queue (abstract data type)|queue]] of graph vertices, with the starting vertex of the graph as the queue's only element.
*While the queue is non-empty, remove (dequeue) a vertex {{mvar|v}} from the queue, and add to the queue (enqueue) all the other vertices that can be reached by an edge from {{mvar|v}} that have not already been added in earlier steps.
However, rather than defining the vertex to choose at each step in an [[imperative programming|imperative]] way as the one produced by the dequeue operation of a queue, one can define the same sequence of vertices declaratively by the properties of these vertices. That is, a standard breadth-first search is just the result of repeatedly applying this rule:
*Repeatedly output a vertex {{mvar|v}}, choosing at each step a vertex {{mvar|v}} that has not already been chosen and that has a predecessor (a vertex that has an edge to {{mvar|v}}) as early in the output as possible.
In some cases, this ordering of vertices by the output positions of their predecessors may have ties — two different vertices have the same earliest predecessor. In this case, the order in which those two vertices are chosen may be arbitrary. The output of lexicographic breadth-first search differs from a standard breadth-first search in having a consistent rule for breaking such ties. In lexicographic breadth-first search, the output ordering is the order that would be produced by the rule:
*Repeatedly output a vertex {{mvar|v}}, choosing at each step a vertex {{mvar|v}} that has not already been chosen and whose entire set of already-output predecessors is as small as possible in [[lexicographic order]].
So, when two vertices {{mvar|v}} and {{mvar|w}} have the same earliest predecessor, earlier than any other unchosen vertices,
the standard breadth-first search algorithm will order them arbitrarily. Instead, in this case, the LexBFS algorithm would choose between {{mvar|v}} and {{mvar|w}} by the output ordering of their second-earliest predecessors.
If only one of them has a second-earliest predecessor that has already been output, that one is chosen.
If both {{mvar|v}} and {{mvar|w}} have the same second-earliest predecessor, then the tie is broken by considering their third-earliest predecessors, and so on.

Applying this rule directly by comparing vertices according to this rule would lead to an inefficient algorithm. Instead, the lexicographic breadth-first search uses a set partitioning data structure in order to produce the same ordering more efficiently, just as a standard breadth-first search uses a queue data structure to produce its ordering efficiently.

==Algorithm==
The lexicographic breadth-first search algorithm replaces the [[Queue (data structure)|queue]] of vertices of a standard breadth-first search with an ordered sequence of sets of vertices. The sets in the sequence form a [[partition (set theory)|partition]] of the remaining vertices. At each step, a vertex ''v'' from the first set in the sequence is removed from that set, and if that removal causes the set to become empty then the set is removed from the sequence. Then, each set in the sequence is replaced by two subsets: the neighbors of ''v'' and the non-neighbors of ''v''. The subset of neighbors is placed earlier in the sequence than the subset of non-neighbors. In [[pseudocode]], the algorithm can be expressed as follows:

*Initialize a sequence Σ of sets, to contain a single set containing all vertices.
*Initialize the output sequence of vertices to be empty.
*While Σ is non-empty:
**Find and remove a vertex ''v'' from the first set in Σ
**If the first set in Σ is now empty, remove it from Σ
**Add ''v'' to the end of the output sequence.
**For each edge ''v-w'' such that ''w'' still belongs to a set ''S'' in Σ:
***If the set ''S'' containing ''w'' has not yet been replaced while processing ''v'', create a new empty replacement set ''T'' and place it prior to ''S'' in the sequence; otherwise, let ''T'' be the set prior to ''S''.
***Move ''w'' from ''S'' to ''T'', and if this causes ''S'' to become empty remove ''S'' from Σ.

Each vertex is processed once, each edge is examined only when its two endpoints are processed, and (with an appropriate representation for the sets in Σ that allows items to be moved from one set to another in constant time) each iteration of the inner loop takes only constant time. Therefore, like simpler graph search algorithms such as breadth-first search and [[depth-first search]], this algorithm takes linear time.

The algorithm is called lexicographic breadth-first search because the order it produces is an ordering that could also have been produced by a breadth-first search, and because if the ordering is used to index the rows and columns of an [[adjacency matrix]] of a graph then the algorithm [[sorting algorithm|sorts]] the rows and columns into [[lexicographical order]].

==Applications==
===Chordal graphs===
A graph ''G'' is defined to be [[Chordal graph|chordal]] if its vertices have a ''perfect elimination ordering'', an ordering such that for any vertex ''v'' the neighbors that occur later in the ordering form a clique. In a chordal graph, the reverse of a lexicographic ordering is always a perfect elimination ordering. Therefore, one can test whether a graph is chordal in linear time by the following algorithm:
*Use lexicographic breadth-first search to find a lexicographic ordering of ''G''
*For each vertex ''v'':
**Let ''w'' be the neighbor of ''v'' occurring prior to ''v'', as close to ''v'' in the sequence as possible
***(Continue to the next vertex ''v'' if there is no such ''w'')
**If the set of earlier neighbors of ''v'' (excluding ''w'' itself) is not a subset of the set of earlier neighbors of ''w'', the graph is not chordal
*If the loop terminates without showing that the graph is not chordal, then it is chordal.

This application was the original motivation that led {{harvtxt|Rose|Tarjan|Lueker|1976}} to develop the lexicographic breadth first search algorithm.{{sfnp|Corneil|2004}}

===Graph coloring===
A graph ''G'' is said to be ''perfectly orderable'' if there is a sequence of its vertices with the property that, for any [[induced subgraph]] of ''G'', a [[greedy coloring]] algorithm that colors the vertices in the induced sequence ordering is guaranteed to produce an optimal coloring.

For a chordal graph, a perfect elimination ordering is a perfect ordering: the number of the color used for any vertex is the size of the clique formed by it and its earlier neighbors, so the maximum number of colors used is equal to the size of the largest clique in the graph, and no coloring can use fewer colors. An induced subgraph of a chordal graph is chordal and the induced subsequence of its perfect elimination ordering is a perfect elimination ordering on the subgraph, so chordal graphs are perfectly orderable, and lexicographic breadth-first search can be used to optimally color them.

The same property is true for a larger class of graphs, the [[distance-hereditary graph]]s: distance-hereditary graphs are perfectly orderable, with a perfect ordering given by the reverse of a lexicographic ordering, so lexicographic breadth-first search can be used in conjunction with greedy coloring algorithms to color them optimally in linear time.<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 5.2.4, p. 71.</ref>

===Other applications===
{{harvtxt|Bretscher|Corneil|Habib|Paul|2008}} describe an extension of lexicographic breadth-first search that breaks any additional ties using the [[complement graph]] of the input graph. As they show, this can be used to recognize [[cograph]]s in linear time. {{harvtxt|Habib|McConnell|Paul|Viennot|2000}} describe additional applications of lexicographic breadth-first search including the recognition of [[comparability graph]]s and [[interval graph]]s.

==LexBFS ordering==
An enumeration of the vertices of a graph is said to be a LexBFS ordering if it is the possible output of the application of LexBFS to this graph.

Let <math>G=(V,E)</math> be a graph  with <math>n</math> vertices.  Recall that <math>N(v)</math> is the set of neighbors of <math>v</math>.
Let <math>\sigma=(v_1,\dots,v_n)</math> be an enumeration of the vertices of <math>V</math>.
The enumeration <math>\sigma</math> is a LexBFS ordering (with source <math>v_1</math>) if, for all <math>1\le i<j<k\le n</math> with <math>v_i\in N(v_k)\setminus N(v_j)</math>, there exists <math>m<i</math> such that  <math>v_m\in N(v_j)\setminus N(v_k)</math>.

==Notes==
{{reflist}}

==References==
*{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 0-89871-432-X
 | url-access = registration
 | url = https://archive.org/details/graphclassessurv0000bran
 }}.
*{{citation|first1=Anna|last1=Bretscher|first2=Derek|last2=Corneil|author2-link=Derek Corneil|first3=Michel|last3=Habib|first4=Christophe|last4=Paul|title=A simple linear time LexBFS cograph recognition algorithm|journal=[[SIAM Journal on Discrete Mathematics]]|volume=22|issue=4|year=2008|pages=1277–1296|doi=10.1137/060664690|url=http://www.liafa.jussieu.fr/~habib/Documents/cograph.ps|citeseerx=10.1.1.188.5016}}.
*{{citation|first=Derek G.|last=Corneil|authorlink=Derek Corneil|contribution=Lexicographic breadth first search – a survey|title=Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=3353|year=2004|pages=1–19|doi=10.1007/978-3-540-30559-0_1|isbn=978-3-540-24132-4 }}.
*{{citation|first1=Michel|last1=Habib|first2=Ross|last2=McConnell|first3=Christophe|last3=Paul|first4=Laurent|last4=Viennot|title=Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing|journal=Theoretical Computer Science|volume=234|year=2000|pages=59–84|issue=1–2|doi=10.1016/S0304-3975(97)00241-7|doi-access=free}}.
*{{citation|first1=D. J.|last1=Rose|first2=R. E.|last2=Tarjan|author2-link=Robert Tarjan|first3=G. S.|last3=Lueker|year=1976|title=Algorithmic aspects of vertex elimination on graphs|journal=[[SIAM Journal on Computing]]|volume=5|pages=266–283|issue=2|doi=10.1137/0205021}}.

{{Graph traversal algorithms}}

[[Category:Graph algorithms]]
[[Category:Search algorithms]]