# Can Lexicographic BFS be implemented in logspace?

Input: Given graph $G=(V,E)$ vertex labeling in some order

Output: Change the labeling of vertices's such that labeling start $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 labeling 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 trying with BFS but not working in logspace. Can any one help me out.

See for defination of Lexicographic BFS(en.wikipedia.org/wiki/Lexicographic_breadth-first_search)

• I don't see how this differs from en.wikipedia.org/wiki/Lexicographic_breadth-first_search ; are you asking whether LBFS can be implemented in logspace? Apr 30, 2017 at 15:04
• @AndrasSalamon nice catching point. Can LBFS implemented in logspace? May 1, 2017 at 2:43
• 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. May 1, 2017 at 5:00
• The introduction to this paper 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. May 1, 2017 at 10:01
• 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. May 2, 2017 at 12:40