<p>It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) <span class="math-container">$u_1$</span> be <span class="math-container">$v_1$</span>, and the next elements <span class="math-container">$u_2$</span>, <span class="math-container">$u_3$</span>, etc., of the output, be the neighbors of <span class="math-container">$v_1$</span> <em>according to the input ordering</em>.</p>
<p>In a graph search, we iteratively build an output list (the <span class="math-container">$u$</span>'s) from the input list (the <span class="math-container">$v$</span>'s). At each step, the next element of the output list is chosen from the current output list's boundary. If the search is breadth-first, we select a boundary element with the <em>earliest possible</em> neighbor in the output list.</p>
<p>Of course, there could be ties. It looks like the OP is suggesting breaking ties by <strong>choosing the input-least element</strong>. This is different from Lex-BFS, which breaks ties by <strong>comparing the second-to-least neighbors in the output;</strong> if they are the same, comparing the 3rd neighbors, etc. In my opinion &quot;lexicographic BFS&quot; would be a reasonable name for the first algorithm, but it's already been taken by the second, hence the confusion.</p>
<p>But it actually doesn't matter which algorithm you pick, the answer is the same: <strong>no breadth-first traversal can be computed in logspace</strong> unless L equals NL. If we could, then we could solve directed reachability in logspace. The details are <a href="https://arxiv.org/abs/2006.07067" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2023-05-28T15:14:58.040Z
2023-05-28T15:14:58.040Z
Siddharth
<p>Input: Given graph <span class="math-container">$G=(V,E)$</span> with vertices labeled in some order</p>
<p>Output: Change the labeling of vertices such that the
labeling starts <span class="math-container">$v_1$</span> as <span class="math-container">$u_1$</span>. Next, label the neighbors of <span class="math-container">$v_1$</span> as <span class="math-container">$u_2,u_3,u_4,...$</span> according least index given in input. Next, label the neighbors of least index neighbor of <span class="math-container">$v_1$</span>.
I.e. <span class="math-container">$v_1=u_1$</span> and neighbors of <span class="math-container">$v_1$</span> as <span class="math-container">$u_2,u_3,...$</span>. so .. on</p>
<p>For example:
input: <span class="math-container">$G=(V,E)$</span> and <span class="math-container">$V=\{v_1,v_2,v_3,v_4,v_4,v_5,v_6\}, E=\{v_1v_3,v_1v_5,v_1v_6,v_2v_3,v_2v_4,v_2v_5,v_2v_6\}$</span></p>
<p>Output: <span class="math-container">$G'=(U,E')$</span> and <span class="math-container">$U=\{u_1,u_2,u_3,u_4,u_4,u_5,u_6\}, E'=\{u_1u_2,u_1u_3,u_1u_4,u_2u_5,u_3u_5,u_4u_5,u_5u_6\}$</span></p>
<p>Can there be a algorithm for above process in logspace?
I tried with BFS but not working in logspace. Can any one help me out.</p>
<p>See for definition of Lexicographic BFS(<a href="http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search" rel="nofollow noreferrer">en.wikipedia.org/wiki/Lexicographic_breadth-first_search</a>)</p>

CC BY-SA 3.0
2017-04-25T19:30:07.040Z
Is the graph directed or undirected? Also, what is the desired behavior when there exist vertices which cannot be reached from $v_1$ by any path?
Mikhail Rudoy
CC BY-SA 3.0
2017-04-26T00:50:15.887Z
Graph is undirected and just think about the connected graphs only.
Diamond
CC BY-SA 3.0
2017-04-30T15:04:06.350Z
I don't see how this differs from https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search ; are you asking whether LBFS can be implemented in logspace?
András Salamon
CC BY-SA 3.0
2017-05-01T02:43:41.487Z
@AndrasSalamon nice catching point.  Can LBFS  implemented in logspace?
Diamond
CC BY-SA 3.0
2017-05-01T05:00:41.680Z
I suggest you change the title to "Can Lexicographic BFS be implemented in logspace?", start the post with that question (using ">"), including a link to the wikipedia page, and then you could use the material from current post simply as the definition/example of LBFS.
Joshua Grochow
CC BY-SA 3.0
2017-05-01T10:01:03.207Z
The introduction to this paper https://eccc.weizmann.ac.il/report/2010/043/ suggests that no implementation of LexBFS in logspace is known: otherwise the authors could compute a perfect elimination ordering in logspace, which they explicitly say they avoid.
Sasho Nikolov
CC BY-SA 3.0
2017-05-02T12:40:51.630Z
I'm pretty sure that computing the ordering is hard for $P$, by a reduction from (monotone) Circuit Evaluation. You construct a graph corresponding to the gates s.t. computing the lex first bfs ordering evaluates the gates of the circuit. Can't recall the reference at the moment, though.
Ryan Williams
<cc.complexity-theory><graph-theory><graph-algorithms><logspace>
Can Lexicographic BFS be implemented in logspace?
Diamond
# Can Lexicographic BFS be implemented in logspace?

(Asked by: username_0 on 2017-04-24)

Input: Given graph $G=(V,E)$ with vertices labeled in some order

Output: Change the labeling of vertices such that the
labeling starts $v\_1$ as $u\_1$. Next, label the neighbors of $v\_1$ as $u\_2,u\_3,u\_4,...$ according least index given in input. Next, label the neighbors of least index neighbor of $v\_1$.
I.e. $v\_1=u\_1$ and neighbors of $v\_1$ as $u\_2,u\_3,...$. so .. on

For example:
input: $G=(V,E)$ and $V=\{v\_1,v\_2,v\_3,v\_4,v\_4,v\_5,v\_6\}, E=\{v\_1v\_3,v\_1v\_5,v\_1v\_6,v\_2v\_3,v\_2v\_4,v\_2v\_5,v\_2v\_6\}$

Output: $G'=(U,E')$ and $U=\{u\_1,u\_2,u\_3,u\_4,u\_4,u\_5,u\_6\}, E'=\{u\_1u\_2,u\_1u\_3,u\_1u\_4,u\_2u\_5,u\_3u\_5,u\_4u\_5,u\_5u\_6\}$

Can there be a algorithm for above process in logspace?
I tried with BFS but not working in logspace. Can any one help me out.

See for definition of Lexicographic BFS([en.wikipedia.org/wiki/Lexicographic\_breadth-first\_search](http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search))

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, logspace
> **Comments:**
> **username_1**: Is the graph directed or undirected? Also, what is the desired behavior when there exist vertices which cannot be reached from $v_1$ by any path?  
> **username_0**: Graph is undirected and just think about the connected graphs only.  
> **username_2**: I don't see how this differs from https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search ; are you asking whether LBFS can be implemented in logspace?  
> **username_0**: @AndrasSalamon nice catching point.  Can LBFS  implemented in logspace?  
> **username_3**: I suggest you change the title to "Can Lexicographic BFS be implemented in logspace?", start the post with that question (using ">"), including a link to the wikipedia page, and then you could use the material from current post simply as the definition/example of LBFS.  
> **username_4**: The introduction to this paper https://eccc.weizmann.ac.il/report/2010/043/ suggests that no implementation of LexBFS in logspace is known: otherwise the authors could compute a perfect elimination ordering in logspace, which they explicitly say they avoid.  
> **username_5**: I'm pretty sure that computing the ordering is hard for $P$, by a reduction from (monotone) Circuit Evaluation. You construct a graph corresponding to the gates s.t. computing the lex first bfs ordering evaluates the gates of the circuit. Can't recall the reference at the moment, though.  

---

## 1 answers

### Answer by username_6 on 2023-05-28. Score: 3

It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) $u\_1$ be $v\_1$, and the next elements $u\_2$, $u\_3$, etc., of the output, be the neighbors of $v\_1$ *according to the input ordering*.

In a graph search, we iteratively build an output list (the $u$'s) from the input list (the $v$'s). At each step, the next element of the output list is chosen from the current output list's boundary. If the search is breadth-first, we select a boundary element with the *earliest possible* neighbor in the output list.

Of course, there could be ties. It looks like the OP is suggesting breaking ties by **choosing the input-least element**. This is different from Lex-BFS, which breaks ties by **comparing the second-to-least neighbors in the output;** if they are the same, comparing the 3rd neighbors, etc. In my opinion "lexicographic BFS" would be a reasonable name for the first algorithm, but it's already been taken by the second, hence the confusion.

But it actually doesn't matter which algorithm you pick, the answer is the same: **no breadth-first traversal can be computed in logspace** unless L equals NL. If we could, then we could solve directed reachability in logspace. The details are [here](https://arxiv.org/abs/2006.07067).


---

