La complexité de déterminer si un graphique fixe est mineur d'un autre

Le résultat par Robertson et Seymour démontre un algorithme pour tester si un graphique fixe G est un mineur de . J'ai deux questions et demie sur ce sujet:$O(n^3)$$G$$H$

1) Il semble que cet algorithme ait été amélioré depuis. Quel est actuellement l'algorithme le plus connu?

2a) Qu'est-ce que les gens supposent être la limite optimale?

L'algorithme de Mohar pour l'intégration sur une surface fixe et l'algorithme de Kawarabayashi pour reconnaître les graphes apex$k$ décident de l'appartenance des graphes caractérisables par les mineurs interdits en temps linéaire, motivant la dernière question:

2b) Y a-t-il une raison de soupçonner que nous pouvons le faire en temps linéaire?

Bien sûr, si quelqu'un a déjà proposé un algorithme de temps linéaire, les deux dernières questions sont stupides. :)

Il y a une préimpression de Ken-ichi Kawarabayashi, Yusuke Kobayashi et Bruce Reed qui revendique un algorithme de temps quadratique: " Le problème des chemins disjoints en temps quadratique ". Il est formaté comme une soumission à la conférence plutôt qu'un article de journal, donc je ne suis pas sûr qu'il soit possible de vérifier les détails, cependant (je n'ai pas vraiment essayé moi-même).

Une étude très récente de Kawarabayashi le cite comme le résultat le plus connu pour le problème des chemins disjoints étroitement liés: Ken-ichi Kawarabayashi (2011), «The Disjoint Paths Problem: Algorithm and Structure», WALCOM: Algorithms and Computation, LNCS 6552, pp .2–7, doi: 10.1007 / 978-3-642-19094-0_2 .

$O(n\log n)$

$H$$h$ $G$$2^{O(h)} n + O(n^2 \log n)$$n$$h$