9
$\begingroup$

A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained from the famous result of Roberson and Seymour.

This result, as well as other algorithms for minor testing, is always cited with $f$ being some implicit computable function. I wonder what are the best known upper bounds on $f$, e.g., is it elementary?

In this discussion, user @Saeed mentions that $f$ is at most quadruple-exponential but provides no reference for this claim.

$\endgroup$
  • $\begingroup$ In this paper, $f$ is described as "recursive" and with an "immense exponential growth". Some references in the paper may help. $\endgroup$ – Michele Amoretti May 17 at 6:59
-1
$\begingroup$

My answer was based on the explanation in paper of Adler et al for disjoint paths problem. That running time is not exactly what is in the Robertson and Seymour paper but it is the improved one by Kawarabayashi and Wollan. It’s been a long time ago and I am not sure if this is restricted to specific graph class. You may have a look at the corresponding reference.

https://arxiv.org/pdf/1310.2378.pdf

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Where in the paper is the bound stated? All I can see is a $2^{2^{2^{2^{\Omega(k)}}}}$ lower bound, but no upper bounds. $\endgroup$ – Emil Jeřábek May 17 at 10:14
  • $\begingroup$ Yes, that is stated as lowerbound. I do not remember if it is also an upperbound or closely related and I do not have access to the main paper at the moment and even if I had access I wouldn’t go to verify it. Here I tried to give corresponding references that one can dig further. For instance checking those papers or writing email to authors. $\endgroup$ – Saeed May 17 at 11:24
  • $\begingroup$ I see I got downvote for this answer. There is nothing wrong in this answer, I did not claim anything about the previous answer to be correct (I also don't say anything is wrong there, since I don't remember completely the entire topic to be sure about anything). This answer as I explained earlier is just to provide further references for the OP. I know there are many cranks here and in general everywhere so this explanation might seem useless by this knowledge, but I have to do my job and explain that you are wrong with your evaluation/thought/spite. $\endgroup$ – Saeed May 19 at 13:32
  • 2
    $\begingroup$ The -1 is from me, because bare links to PDFs are very annoying and unhelpful. To begin with, readers on mobile phones or on slow connections are either unable to open PDFs at all, or it may be burdensome for them. But even those who do not suffer such difficulties often prefer to have an idea what kind of paper is behind the link (title, author, length, ideally abstract) before deciding whether to download the PDF. You should never link directly to PDF, but to metadata such as the arXiv abstract page. You should also include basic bibliographic information (author, title) in the post itself. $\endgroup$ – Emil Jeřábek May 19 at 13:46
  • 2
    $\begingroup$ A bare link is not in any way a “cite” or “reference”. A reference includes the name of the author, the title of the paper, and an unambiguous description of the media where it was published (which may be a journal issue, or an open access repository, whatever). And “ease the way” = not link just to a PDF. It is not for you to decide what is heavy for someone else, and anyway, the reader has no way of knowing whether it is heavy or not beforehand if it’s just a link. $\endgroup$ – Emil Jeřábek May 19 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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