<p>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.</p>

<p><a href="https://arxiv.org/pdf/1310.2378.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1310.2378.pdf</a></p>

CC BY-SA 4.0
2020-05-17T10:14:45.630Z
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
CC BY-SA 4.0
2020-05-17T11:24:25.017Z
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
CC BY-SA 4.0
2020-05-19T13:32:21.777Z
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
CC BY-SA 4.0
2020-05-19T13:46:01.733Z
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
CC BY-SA 4.0
2020-05-19T13:56:11.230Z
@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
CC BY-SA 4.0
2020-05-19T14:03:07.540Z
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
CC BY-SA 4.0
2020-05-19T14:13:52.090Z
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
CC BY-SA 4.0
2020-05-17T10:01:19.600Z
2020-05-19T08:20:40.333Z
2020-05-19T08:20:40.333Z
Saeed
<p>A cornerstone of the graph minor theory is an algorithm that, given undirected graphs <span class="math-container">$G, H$</span>, runs in time <span class="math-container">$f(|H|)poly(|G|)$</span>, and determines whether <span class="math-container">$H$</span> is a minor of <span class="math-container">$G$</span> or not. It has been obtained from the famous <a href="https://www.sciencedirect.com/science/article/pii/S0095895685710064" rel="noreferrer">result of Roberson and Seymour</a>.</p>

<p>This result, as well as other algorithms for minor testing, is always cited with <span class="math-container">$f$</span> being some implicit computable function. I wonder what are the best known upper bounds on <span class="math-container">$f$</span>, e.g., is it elementary?</p>

<p>In <a href="https://cstheory.stackexchange.com/questions/21973/for-which-values-of-k-is-the-k-disjoint-paths-problem-in-mathcalp/21976#21976">this</a> discussion, user @Saeed mentions that <span class="math-container">$f$</span> is at most quadruple-exponential but provides no reference for this claim.</p>

CC BY-SA 4.0
2020-05-17T06:59:47.330Z
In [this paper](http://www.lirmm.fr/~sau/Pubs/Minor-planar.pdf), $f$ is described as "recursive" and with an "immense exponential growth". Some references in the paper may help.
Michele Amoretti
<fixed-parameter-tractable><graph-minor><disjoint-paths>
What is the best upper bound on the running time of the graph minor algorithm?
Michal
# What is the best upper bound on the running time of the graph minor algorithm?

(Asked by: username_0 on 2020-05-16)

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](https://www.sciencedirect.com/science/article/pii/S0095895685710064).

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](https://cstheory.stackexchange.com/questions/21973/for-which-values-of-k-is-the-k-disjoint-paths-problem-in-mathcalp/21976#21976) discussion, user @Saeed mentions that $f$ is at most quadruple-exponential but provides no reference for this claim.

**Tags:** fixed-parameter-tractable, graph-minor, disjoint-paths
> **Comments:**
> **username_1**: In [this paper](http://www.lirmm.fr/~sau/Pubs/Minor-planar.pdf), $f$ is described as "recursive" and with an "immense exponential growth". Some references in the paper may help.  

---

## 1 answers

### Answer by username_2 on 2020-05-17. Score: -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>

> **Comments:**
> **username_3**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_2**: @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).  
> **username_3**: 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.  
> **username_2**: 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.  

---

