A complexidade de determinar se um gráfico fixo é menor que outro

O resultado por Robertson e Seymour demonstra um algoritmo para testar se um gráfico fixo é um menor de . Eu tenho duas perguntas e meia sobre este tópico:G $O(n^3)$$G$$H$

1) Parece que houve melhorias nesse algoritmo desde então. Qual é o algoritmo mais conhecido atualmente?

2a) O que as pessoas imaginam ser o limite ideal?

O algoritmo de Mohar para incorporar em uma superfície fixa e o algoritmo de Kawarabayashi para reconhecer gráficos apex$k$ decidem a associação de gráficos caracterizáveis ​​por menores proibidos em tempo linear, motivando a última pergunta:

2b) Existe alguma razão para suspeitar que podemos fazer isso em tempo linear?

Obviamente, se alguém já criou um algoritmo de tempo linear, as duas últimas perguntas são tolas. :)

Há uma pré-impressão de Ken-ichi Kawarabayashi, Yusuke Kobayashi e Bruce Reed que afirma um algoritmo de tempo quadrático: " O problema de caminhos disjuntos no tempo quadrático ". Ele é formatado como uma apresentação da conferência e não como um jornal, portanto, não tenho certeza de que é possível verificar os detalhes (eu realmente não tentei).

Uma pesquisa muito recente de Kawarabayashi cita isso como o resultado mais conhecido para o problema de caminhos disjuntos estreitamente relacionados: Ken-ichi Kawarabayashi (2011), "O problema dos caminhos disjuntos: algoritmo e estrutura", 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$