5
$\begingroup$

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)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – András Salamon
    Apr 30, 2017 at 15:04
  • 1
    $\begingroup$ @AndrasSalamon nice catching point. Can LBFS implemented in logspace? $\endgroup$
    – Diamond
    May 1, 2017 at 2:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    May 1, 2017 at 5:00
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    May 1, 2017 at 10:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    May 2, 2017 at 12:40

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.