# Is there an algorithm that finds the forbidden minors?

The Robertson–Seymour 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$$ or WRONG PROOF).

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|$$.

• 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. Nov 3, 2018 at 18:53
• @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. Nov 3, 2018 at 20:41
• @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|$. Nov 3, 2018 at 21:56
• Well, I interpret halting that if $M$ halts in $2$ steps, then we also say that it halts in $3$ steps. Nov 3, 2018 at 22:26
• @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. Nov 4, 2018 at 14:23

• 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? Nov 3, 2018 at 22:12