Условные нижние оценки для задачи о гомоморфизме графов

Условные нижние оценки для задачи о гомоморфизме графов

Speaker:

Иван Михайлин

Date:

Tuesday, August 4, 2015 - 13:00

Abstract:

В задаче о гомоморфизме графов на вход подается два графа и требуется узнать, существует ли отображение вершин одного в вершины другого, которое переводит ребра в ребра. Задача о гомоморфизме графов обобщают задачу о раскраске графа, для которой не так давно был придуман относительно быстрый алгоритм со сложностью O*(2^n). За последние годы было предпринято несколько попыток адаптировать этот алгоритм (или придумать другой) для задачи о гомоморфизме, однако удовлетворительные результаты были получены только для частных случаев. В докладе будет показано, почему создание эффективного алгоритма для этой задачи противоречит ETH - популярной гипотезе о том, что для 3-SAT не существует алгоритма с субэкспоненциальным временем работы.