<p>The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a <a href="https://cstheory.stackexchange.com/questions/39399/conclusions-from-reverse-mathematical-strength-of-graph-minor-theorem">similar question</a> cites <a href="http://www.jucs.org/jucs_3_11/a_note_on_the/Courcelle_B.pdf" rel="noreferrer">A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals</a> (1997) by B. Courcelle, R. Downey, and M. Fellows for a non-computability result (for <strong>MSOL-definable</strong> graph classes, i.e. classes defined by a Monadic Second order formula) and <a href="http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub" rel="noreferrer">The obstructions of a minor-closed set of graphs defined by a context-free grammar</a> (1998) by B. Courcelle and G. Sénizergues for a computability result (for <strong>HR-definable</strong> graph classes, i.e. classes defined by a Hyperedge Replacement grammar).</p>

<p>The crucial difference between the computable and the non-computable case is that (minor-closed) HR-definable graph classes have bounded treewidth, while (minor-closed) MSOL-definable graph classes need not have bounded treewidth. In fact, if a (minor-closed) MSOL-definable graph class has bounded treewidth, then it is also HR-definable.</p>

<p>The treewidth seems to be really the crucial part for separating the computable from the non-computable cases. Another known result (by M. Fellows and M. Langston) basically says that if a bound for the maximum treewidth (or pathwidth) of the finite set of excluded minors is known, then the (finite) minimal set of excluded minors becomes computable.</p>

<p>It is not even known whether the (finite) minimal set of excluded minors for the union (which is trivially minor-closed) of two minor-closed graph classes each given by their respective finite set of excluded minors can be computed, if no information about treewidth (or pathwidth) is available. Or maybe it has even been proved in the meantime that it is non-computable in general.</p>

CC BY-SA 4.0
2018-11-03T22:12:47.960Z
This last part is quite interesting. If understand well, this implies the following. For a graph family $\mathcal G$, denote by $m(\mathcal G)$ the size of the largest forbidden minimal minor. Let $f(n)=\max \{m(\mathcal G_1 \cup \mathcal G_2)\mid m(\mathcal G_1),m(\mathcal G_2)\le n\}$. Then there is no known recursive upper bound for $f(n)$. Do you know some examples that show that $f(n)$ grows very fast?
domotorp
CC BY-SA 4.0
2018-11-04T14:45:46.337Z
@domotorp I agree, good point. I do have some ideas for such examples, but I have the impression that the growth rate of all my examples (which basically try to play with "grid" dimension) will stay within ELEMENTARY. However, I believe that if I wanted to invest time into those questions, then I should first do a literature study about what happened in the years 2000-2018, perhaps by looking at papers that quote the papers that I know about, or by looking at later publications of the authors which worked on those questions.
Thomas Klimpel
CC BY-SA 4.0
2018-11-04T19:43:22.407Z
I see - well, I'm not desperate to know the answer, just I got surprised and became curious...
domotorp
CC BY-SA 4.0
2018-11-05T01:13:37.757Z
@domotorp The minimal set of excluded minors for the union has been shown to be computable in 2008: http://logic.las.tu-berlin.de/Members/Kreutzer/Publications/08-soda.pdf
Thomas Klimpel
CC BY-SA 4.0
2018-11-03T16:58:55.853Z
2018-11-03T16:58:55.853Z
Thomas Klimpel
<p>The <a href="https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow noreferrer">Robertson–Seymour theorem</a> says that any minor-closed family <span class="math-container">$\mathcal G$</span> of graphs can be characterized by finitely many forbidden minors.</p>

<blockquote>
  <p>Is there an algorithm that for an input <span class="math-container">$\mathcal G$</span> outputs the forbidden minors or is this undecidable?</p>
</blockquote>

<p>Obviously, the answer might depend on how <span class="math-container">$\mathcal G$</span> is described in the input.
For example, if <span class="math-container">$\mathcal G$</span> is given by an <span class="math-container">$M_\mathcal G$</span> that can decide membership, we cannot even decide whether <span class="math-container">$M_\mathcal G$</span> ever rejects anything.
If <span class="math-container">$\mathcal G$</span> is given by finitely many forbidden minors - well, that's what we're looking for.
I would be curious to know the answer if <span class="math-container">$M_\mathcal G$</span> is guaranteed to stop on any <span class="math-container">$G$</span> in some fixed amount of time in <span class="math-container">$|G|$</span>.
I'm also interested in any related results, where <span class="math-container">$\mathcal G$</span> is proved to be minor-closed with some other certificate (like in case of <a href="https://en.wikipedia.org/wiki/TFNP" rel="nofollow noreferrer"><span class="math-container">$TFNP$</span></a> or <a href="https://eccc.weizmann.ac.il/report/2017/056/" rel="nofollow noreferrer"><em>WRONG PROOF</em></a>).</p>

<p>Update: The first version of my question turned out to be quite easy, based on the ideas of Marzio and Kimpel, consider the following construction.
<span class="math-container">$M_\mathcal G$</span>  accepts a graph on <span class="math-container">$n$</span> vertices if and only if <span class="math-container">$M$</span> does not halt in <span class="math-container">$n$</span> steps. This is minor closed and the running time depends only on <span class="math-container">$|G|$</span>.</p>

CC BY-SA 4.0
2018-11-03T18:53:53.070Z
If $\mathcal G$ is represented by an always halting TM $M_\mathcal G$, you can reduce the halting problem to it: given $M$ build $M_\mathcal G( G_x )$ that outputs yes if and only if $M$ halts exactly in $x$ steps ($(G_1,G_2,...$ is a standard graph enumeration).  $M_\mathcal G( G_x )$ accepts at most one forbidden minor, so $\mathcal G$ is a minor-closed family; hence the problem is undecidable.
Marzio De Biasi
CC BY-SA 4.0
2018-11-03T20:41:39.520Z
@ThomasKlimpel: Ops, I misanderstood the question. Perhaps a fix is: $M_\mathcal G( G_x )$ search the first $G_i, i \leq x$ such that $M$ halts exactly in $i$ steps then accept if $G_i$ is not a minor of $G_x$; reject otherwise.
Marzio De Biasi
CC BY-SA 4.0
2018-11-03T21:56:50.967Z
@Marzio Yes, to simplify: $M_\mathcal G$ accepts a graph on $n$ vertices if and only if $M$ does not halt in $n$ steps. This is minor closed and the running time depends only on $|G|$.
domotorp
CC BY-SA 4.0
2018-11-03T22:26:17.970Z
Well, I interpret halting that if $M$ halts in $2$ steps, then we also say that it halts in $3$ steps.
domotorp
CC BY-SA 4.0
2018-11-04T14:23:41.870Z
@domotorp Since your construction works (if I am not mistaken), and answers one of your questions (and since Marzio De Biasi and me tried to come up with such a simple construction without success), I think you should turn your construction into a proper answer. You can make it a community wiki, if you feel uneasy about answering your own question. Alternatively, you can edit your question and add the answer there.
Thomas Klimpel
<graph-theory><decidability><graph-minor>
Is there an algorithm that finds the forbidden minors?
domotorp
# Is there an algorithm that finds the forbidden minors?

(Asked by: username_0 on 2018-11-02)

The [Robertson–Seymour theorem](https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem) says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors.

> Is there an algorithm that for an input $\mathcal G$ outputs the forbidden minors or is this undecidable?

Obviously, the answer might depend on how $\mathcal G$ is described in the input.
For example, if $\mathcal G$ is given by an $M\_\mathcal G$ that can decide membership, we cannot even decide whether $M\_\mathcal G$ ever rejects anything.
If $\mathcal G$ is given by finitely many forbidden minors - well, that's what we're looking for.
I would be curious to know the answer if $M\_\mathcal G$ is guaranteed to stop on any $G$ in some fixed amount of time in $|G|$.
I'm also interested in any related results, where $\mathcal G$ is proved to be minor-closed with some other certificate (like in case of [$TFNP$](https://en.wikipedia.org/wiki/TFNP) or [*WRONG PROOF*](https://eccc.weizmann.ac.il/report/2017/056/)).

Update: The first version of my question turned out to be quite easy, based on the ideas of Marzio and Kimpel, consider the following construction.
$M\_\mathcal G$ accepts a graph on $n$ vertices if and only if $M$ does not halt in $n$ steps. This is minor closed and the running time depends only on $|G|$.

**Tags:** graph-theory, decidability, graph-minor

> **Comments:**
> **username_1**: If $\mathcal G$ is represented by an always halting TM $M_\mathcal G$, you can reduce the halting problem to it: given $M$ build $M_\mathcal G( G_x )$ that outputs yes if and only if $M$ halts exactly in $x$ steps ($(G_1,G_2,...$ is a standard graph enumeration).  $M_\mathcal G( G_x )$ accepts at most one forbidden minor, so $\mathcal G$ is a minor-closed family; hence the problem is undecidable.  
> **username_1**: @ThomasKlimpel: Ops, I misanderstood the question. Perhaps a fix is: $M_\mathcal G( G_x )$ search the first $G_i, i \leq x$ such that $M$ halts exactly in $i$ steps then accept if $G_i$ is not a minor of $G_x$; reject otherwise.  
> **username_0**: @Marzio Yes, to simplify: $M_\mathcal G$ accepts a graph on $n$ vertices if and only if $M$ does not halt in $n$ steps. This is minor closed and the running time depends only on $|G|$.  
> **username_0**: Well, I interpret halting that if $M$ halts in $2$ steps, then we also say that it halts in $3$ steps.  
> **username_2**: @username_0 Since your construction works (if I am not mistaken), and answers one of your questions (and since username_1 and me tried to come up with such a simple construction without success), I think you should turn your construction into a proper answer. You can make it a community wiki, if you feel uneasy about answering your own question. Alternatively, you can edit your question and add the answer there.  

---

## 1 answers

### Answer by username_2 on 2018-11-03. Score: 12 | Accepted answer

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a [similar question](https://cstheory.stackexchange.com/questions/39399/conclusions-from-reverse-mathematical-strength-of-graph-minor-theorem) cites [A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals](http://www.jucs.org/jucs_3_11/a_note_on_the/Courcelle_B.pdf) (1997) by B. Courcelle, R. Downey, and M. Fellows for a non-computability result (for **MSOL-definable** graph classes, i.e. classes defined by a Monadic Second order formula) and [The obstructions of a minor-closed set of graphs defined by a context-free grammar](http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub) (1998) by B. Courcelle and G. Sénizergues for a computability result (for **HR-definable** graph classes, i.e. classes defined by a Hyperedge Replacement grammar).

The crucial difference between the computable and the non-computable case is that (minor-closed) HR-definable graph classes have bounded treewidth, while (minor-closed) MSOL-definable graph classes need not have bounded treewidth. In fact, if a (minor-closed) MSOL-definable graph class has bounded treewidth, then it is also HR-definable.

The treewidth seems to be really the crucial part for separating the computable from the non-computable cases. Another known result (by M. Fellows and M. Langston) basically says that if a bound for the maximum treewidth (or pathwidth) of the finite set of excluded minors is known, then the (finite) minimal set of excluded minors becomes computable.

It is not even known whether the (finite) minimal set of excluded minors for the union (which is trivially minor-closed) of two minor-closed graph classes each given by their respective finite set of excluded minors can be computed, if no information about treewidth (or pathwidth) is available. Or maybe it has even been proved in the meantime that it is non-computable in general.

> **Comments:**
> **username_0**: This last part is quite interesting. If understand well, this implies the following. For a graph family $\mathcal G$, denote by $m(\mathcal G)$ the size of the largest forbidden minimal minor. Let $f(n)=\max \{m(\mathcal G_1 \cup \mathcal G_2)\mid m(\mathcal G_1),m(\mathcal G_2)\le n\}$. Then there is no known recursive upper bound for $f(n)$. Do you know some examples that show that $f(n)$ grows very fast?  
> **username_2**: @username_0 I agree, good point. I do have some ideas for such examples, but I have the impression that the growth rate of all my examples (which basically try to play with "grid" dimension) will stay within ELEMENTARY. However, I believe that if I wanted to invest time into those questions, then I should first do a literature study about what happened in the years 2000-2018, perhaps by looking at papers that quote the papers that I know about, or by looking at later publications of the authors which worked on those questions.  
> **username_0**: I see - well, I'm not desperate to know the answer, just I got surprised and became curious...  
> **username_2**: @username_0 The minimal set of excluded minors for the union has been shown to be computable in 2008: http://logic.las.tu-berlin.de/Members/Kreutzer/Publications/08-soda.pdf  

---

