Решение задачи о k-пути в неориентированных графах за 2^{3k/4}

Решение задачи о k-пути в неориентированных графах за 2^{3k/4}

Date:

Monday, October 6, 2014 - 18:00

Abstract:

Будет рассказан недавний алгоритм Бьорклунда, Хусфельда, Каски, Коивисто решения задачи нахождения просто пути длины k в неориентированном графе за время O^*(2^{3k/4}). Из этого, в частности, следует, что найти гамильтонов путь в неориентированном графе можно быстрее 2^n. Алгоритм основан на построении специального многочлена, в котором каждому простому k-пути соответствует уникальный моном, а самопересекающиеся k-пути разбиваются на пары с одинаковыми мономами. Таким образом, данный многочлен тождественно равен нулю в поле характеристики два (достаточно большого размера) тогда и только тогда, когда в графе есть простой k-путь.