Сложность определения, является ли фиксированный граф второстепенным для другого

Результат по Robertson и Seymour демонстрирует алгоритм для проверки , является ли фиксированной граф является минор . У меня есть два с половиной вопроса на эту тему:G $O(n^3)$$G$$H$

1) Похоже, что с тех пор были улучшены этот алгоритм. Какой алгоритм является самым известным в настоящее время?

2a) Что люди предполагают, чтобы быть оптимальной границей?

Алгоритм Мохара для вложения на фиксированную поверхность и алгоритм Каварабаяши для распознавания графов -apex$k$ определяют принадлежность графов, характеризуемых запрещенными минорами в линейном времени, мотивируя последний вопрос:

2б) Есть ли основания подозревать, что мы можем сделать это за линейное время?

Конечно, если кто-то уже придумал алгоритм линейного времени, последние два вопроса глупы. :)

Кентичи Каварабаяши, Юсуке Кобаяши и Брюс Рид подготовили препринт, в котором утверждается алгоритм квадратичного времени: « Проблема непересекающихся путей в квадратичном времени ». Он отформатирован в формате конференции, а не в журнальной статье, поэтому я не уверен, что можно проверить подробности (сам я на самом деле не пробовал).

В недавнем обзоре Каварабаяши это наиболее известный результат для тесно связанной проблемы непересекающихся путей: Ken-ichi Kawarabayashi (2011), «Проблема непересекающихся путей: алгоритм и структура», WALCOM: алгоритмы и вычисления, LNCS 6552, стр. 2–7, дои: 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$