9
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Commented Nov 3, 2018 at 18:53
  • $\begingroup$ @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. $\endgroup$
    – Marzio De Biasi
    Commented Nov 3, 2018 at 20:41
  • $\begingroup$ @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|$. $\endgroup$
    – domotorp
    Commented Nov 3, 2018 at 21:56
  • 1
    $\begingroup$ Well, I interpret halting that if $M$ halts in $2$ steps, then we also say that it halts in $3$ steps. $\endgroup$
    – domotorp
    Commented Nov 3, 2018 at 22:26
  • $\begingroup$ @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. $\endgroup$
    – Thomas Klimpel
    Commented Nov 4, 2018 at 14:23

1 Answer 1

Reset to default
12
$\begingroup$

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (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 (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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – domotorp
    Commented Nov 3, 2018 at 22:12
  • $\begingroup$ @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. $\endgroup$
    – Thomas Klimpel
    Commented Nov 4, 2018 at 14:45
  • $\begingroup$ I see - well, I'm not desperate to know the answer, just I got surprised and became curious... $\endgroup$
    – domotorp
    Commented Nov 4, 2018 at 19:43
  • 1
    $\begingroup$ @domotorp The minimal set of excluded minors for the union has been shown to be computable in 2008: logic.las.tu-berlin.de/Members/Kreutzer/Publications/… $\endgroup$
    – Thomas Klimpel
    Commented Nov 5, 2018 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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