# Can Lexicographic BFS be implemented in logspace?

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)

• 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? Commented Apr 30, 2017 at 15:04
• @AndrasSalamon nice catching point. Can LBFS implemented in logspace? Commented 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. Commented 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. Commented 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. Commented May 2, 2017 at 12:40

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.