# 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? – András Salamon Apr 30 '17 at 15:04
• @AndrasSalamon nice catching point. Can LBFS implemented in logspace? – Diamond May 1 '17 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. – Joshua Grochow May 1 '17 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. – Sasho Nikolov May 1 '17 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. – Ryan Williams May 2 '17 at 12:40