Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

7
  • 1
    $\begingroup$ And no one has separately found such an algorithm (or any other slower algorithm) for checking whether a graph $G$ is in $\mathcal{G}$? $\endgroup$ Commented yesterday
  • $\begingroup$ Kobayashi, Kawarabashi, and Reed improved the bound to $O(n^2)$, IIRC. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ Sorry, I mangled the name of one of the authors: it’s Kawarabayashi, Kobayashi & Reed. And as I learned on Wikipedia, there is an explicit linear time algorithm by Mohar for testing whether a graph embeds in a fixed surface, not relying on Robertson and Seymour. So I don’t actually know an example of an explicit minor-closed family for which no explicit poly-time algorithm is known. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @EmilJeřábek I think the question is, is there any fixed $\mathcal{G}$ for which no explicit verifier algorithm is known? Is there any good candidate for such a $\mathcal{G}$? (It seems plausible that we might be able to construct an explicit verifier even if we don't know what the set of forbidden minors is, so it's not enough to exhibit a $\mathcal{G}$ for which we don't know the set of forbidden minors, though that might be a good start.) $\endgroup$ Commented 20 hours ago
  • 1
    $\begingroup$ @D.W. Yes, that is the question. And it’s perfectly possible there are good examples of such $\mathcal G$ somewhere; I’m simply not familiar with literature on graph algorithms and graph theory. When I wrote that I don’t know such an example in the comment above, this should be literally taken as a statement of my ignorance, not about the state of affairs in the field. $\endgroup$ Commented 20 hours ago