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

25

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(n3)gH

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 apexk 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. :)

Timothy Sun
la source
Je suis très curieux d'en savoir plus à ce sujet.
Suresh Venkat
10
J'ai entendu dire que Bruce Reed et Ken-ichi Kawarabayashi ont un algorithme de temps , mais il n'a pas été écrit. Cette affirmation apparaît ici , par exemple. O(nbûchen)
Robin Kothari
2
Donc aucun d'eux n'a décidé de l'écrire après plus de trois ans?
Timothy Sun

Réponses:

13

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(nbûchen)

David Eppstein
la source
O(nbûchen)
6

Hh g2O(h)n+O(n2bûchen)nh

Bart Jansen
la source