7
$\begingroup$

I was in the process of typing an answer to the following question: Reachability queries on a tree in O(1) time with O(n+m) time preprocessing, when it was deleted by the author.

The question looked reasonable to me. I spent some time thinking about it, and I thought I had a reasonable answer to the question (an algorithm that met the author's requirements), but the question was deleted while I was typing out a detailed answer. On the one hand, once a question is asked, there is arguably some community ownership in the question. (For example, if I'd gotten my answer in and someone had upvoted it, the author would not have been able to delete the question.) On the other hand, I do respect the author's decision to delete the question, for whatever reason.

Do we want the question back? Should I re-ask the question myself? Should we ask the moderators to undelete it? Do we think it will ever be useful to anyone else beyond the original author?

Here was the text of the question, for those who can no longer see it:

I am given an undirected tree T in the usual graph theoretic sense. Given a vertex v and an edge (v,u) incident to v, I need to answer queries of the form return any leaf of T that is reachable from v with a path including (u,v), and no other edges incident to v? More informally, the restriction is that when the edge is given, we can only proceed in to that direction.

I can simply perform a DFS and return a leaf found. I think this would take O(d) time, where d is the diameter of T. However, I'd like to answer a query in O(1) time. Moreover, I'd only like to allow linear preprocessing time. My idea for achieving this was to use a DFS, label leaves, and then label edges when the search backtracks. This idea might work with some additional effort, but I'm really unsure about the details.

"Graph reachability" turned up some results, but maybe they are dealing with more complex problems. I'm happy with any method that uses O(n+m) preprocessing time and answers the queries in O(1) time.

$\endgroup$
7
$\begingroup$

The rules for deleting own's question unilaterally are a compromise between allowing the asker to have second thoughts, and not letting the asker delete the work of others. The rules are: you may delete your own question if it has no answer, or a single answer with no upvote. This is how the threshold for “community ownership” is implemented.

Obviously a simple algorithm can't get it right all the time. Since the asker has decided to delete his question, I'm reluctant to undelete it. If the question interests you, I encourage you to repost it (I can supply the markdown source if needed) and post your answer at the same time. If the asker decides to undelete his question after all we can merge the two questions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .