9

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.

Michal
  • 91
  • 2

1 Answers1

-1

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

Saeed
  • 3,440
  • 1
  • 22
  • 39
  • 4
    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. – Emil Jeřábek May 17 '20 at 10:14
  • 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. – Saeed May 17 '20 at 11:24
  • 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. – Saeed May 19 '20 at 13:32
  • 2
    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. – Emil Jeřábek May 19 '20 at 13:46
  • @EmilJeřábek, Since the abstract of paper basically has nothing related to the question, I intentionally provided link to pdf. I'm not agree with your strong claim "You should never link directly to PDF", this very much depends on whether you want ease the way and if you want to cite open access papers. This pdf file is not heavy to cause extra problem for loading. arXiv links are permanent as far as I know, so bibliographic information is pointless (unless we argue arXiv is not reliable). Anyways, the entire thing might be matter of taste (your downvote and my choice of referencing). – Saeed May 19 '20 at 13:56
  • 2
    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. – Emil Jeřábek May 19 '20 at 14:03
  • Keep in mind that we don't write formal papers here, and by citing or referencing we don't mean the \cite command in latex. This is a perfect referencing for an online forum, nobody could miss anything (unless claiming that arXiv is unreliable, then many journal papers also fail in their referencing). Anyways, if you think this is not a correct way to cite, you might go through numerous posts in this site with a similar referencing spirit and downvote all of them. file size < 2 meg, I have provided the link, and I, like many others here, know that it is not good to link heavy pdf files. – Saeed May 19 '20 at 14:13