9
$\begingroup$

The question (which was "banished" to Math.SE) asks if there is a better solution to APSP than running BFS from each node. That is equivalent to asking if there is an algorithm that runs in less than $O(mn + n^2)$ time. It is a major open problem to improve significantly on this running time: Chan got a $\log n$ speedup in SODA'06 (paper title: "All-pairs shortest paths for unweighted undirected graphs in o(mn) time") but no further progress has been made. In the undirected and unweighted case, one can solve the problem in matrix multiplication time ($n^{2.376}$) with some ingenious algorithms from the mid-90's (one is due to Seidel).

So this is a perfectly fine question for CSTheory. Why was it closed and migrated?

$\endgroup$
1
  • $\begingroup$ I voted to close simply because I assumed that the first Google hit for something like "all-pairs shortest paths" would at least mention the connection to fast matrix multiplication. It seems that this is not the case (yet). Apologies. $\endgroup$
    – Jukka Suomela
    Aug 18, 2011 at 19:18

2 Answers 2

Reset to default
4
$\begingroup$

Reading my question again gives me the feeling that it wasn't asked properly as a research level question, though that is what I'm looking for. Sorry for that.

I'm a CS student and I'm not too much involved in the world of research, so I find it hard to decide if my question belongs or not to cstheory.stack

But I think that MCH's comment was unfortunate, saying that "standard books in algorithms" cover my question feels a little bit agressive and not accurate, that's why my comment was "Can you cite any of the STANDARD algorithms books?".

$\endgroup$
3
  • $\begingroup$ Sorry aromero, I thought that you are sincerely asking for a standard textbook (something like CLRS). It would have helped if you stated that you are familiar with the standard material in the books. $\endgroup$
    – Kaveh
    Aug 18, 2011 at 16:28
  • $\begingroup$ I reopened the question. I would suggest that you edit the question to make it also look more like a research level question. Hopefully @Ryan will post a copy or a link to his answer on Math.SE. $\endgroup$
    – Kaveh
    Aug 18, 2011 at 16:36
  • $\begingroup$ @Kaveh: cstheory.stackexchange.com/questions/7809/… still redirects to math.stackexchange.com/questions/58198/…. (I cleared the browser cache.) This might be a bug of the system. $\endgroup$
    – Tsuyoshi Ito
    Aug 20, 2011 at 1:56
2
$\begingroup$

I think you are referring to this question.

What you are saying about the problem is interesting, but I am not sure that was the what the OP was asking, i.e. although there is a research-level answer to the question as you have explained above, the way the question was phrased by the OP didn't seem to be asking for a research level question, it seemed that the user was not aware of standard material on finding all sources shortest path (and honestly it still seems so to me, e.g. "I'm aware that the single source shortest path in a undirected and unweighted graph can be easily solved by BFS.", or the comment posted by OP as reply to MCH's comment), therefore it seemed to be about material covered in typical undergraduate algorithms courses, and thus off-topic for cstheory.

The question had a close vote and another upvoted comment that this is covered in standard textbooks in algorithms when I migrated it to math.SE. It had already one answer posted, since there was disagreement whether we should delete the answers for non-research level question and the preferred solution IIRC was migrating the answer and the question to Math.SE I migrated it to Math.SE in place of simply closing it.

This is the explanation for why it got migrated to Math.SE.

I would be happy to hear any suggestions on how I can improve my decision making when closing/imigrating questions (it might be better to open a new discussion).

Another issue is should we reopen it and erase the migration history or not. I personally lean towards reopening it because I think the research level answer that you have explained should be made available on the main site although IMO it is not what the OP was asking for. I think we can also edit the question to make it look research level.

$\endgroup$
7
  • $\begingroup$ Thanks for answering my question. I am not really interested in discussing it further. I do not want to declare a process to be "faulty", or suffer the consequences involved in doing so. But I do feel that some questions are rather eagerly closed. $\endgroup$
    – Ryan Williams
    Aug 18, 2011 at 6:54
  • $\begingroup$ @Ryan, I would hope that there are not consequences for suggesting improvements about the way question get closed since it would be better both for me and for others if I make less faulty decisions :), in any case, I will be more careful in migrating the question next time (I will wait until the question receives 4 close votes before making a decision about migrating it.) ps: I didn't use the word "faulty" in bad sense, I know I make many although I might not notice them, I would be happy to be notified about them so I will make less, I will edit my answer to avoid misunderstanding. $\endgroup$
    – Kaveh
    Aug 18, 2011 at 6:58
  • $\begingroup$ (1) I understand the reason why you migrated it, which is the same as the reason why I down-voted the question. $\endgroup$
    – Tsuyoshi Ito
    Aug 18, 2011 at 12:42
  • 3
    $\begingroup$ (2) As a separate matter, may I point out that you sometimes have a bad habit of writing a very, very long sentence? Your second sentence consists of more than 100 words and contains a long parenthesized clause, and it almost suffocated me. $\endgroup$
    – Tsuyoshi Ito
    Aug 18, 2011 at 12:42
  • 2
    $\begingroup$ @Kaveh: I think that part of theoretical research is "finding the interesting question inside the dumb question," and you tend to decide dumb questions are just dumb questions, while I tend to look for something interesting. Of course, I don't have to moderate. (Not that this particular question was "dumb," aromero, but it was judged to be not-research-level by multiple users.) $\endgroup$
    – Aaron Sterling
    Aug 18, 2011 at 14:24
  • 1
    $\begingroup$ @Tsuyoshi, will try to write shorter sentences. :) $\endgroup$
    – Kaveh
    Aug 18, 2011 at 16:29
  • $\begingroup$ @Aaron, you are also correct. I think part of the problem is that I migrated the question in place of only closing it. If in place of migrating I had just closed it, Ryan and other high rep users could easily reopen it. I mainly migrated it to avoid deleting the posted answer. I guess deleting the answer is probably less harmful in these cases. $\endgroup$
    – Kaveh
    Aug 18, 2011 at 16:32

You must log in to answer this question.

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