Решение задачи о гамильтоновом пути с помощью базиса совершенных паросочетаний

Speaker: 
Павел Кунявский
Date: 
Monday, October 27, 2014 - 18:00
Place: 
ПОМИ, аудитория 106
Abstract: 

В докладе будет рассказано вероятностное решение задачи о гамильтоновом цикле за время O*(1.888^n) в неориентированном графе, в ориентированном двудольном из статьи Цыгана, Кратча и Недерлофа [STOC 2013]. Алгоритм основан на разложении гамильтонова пути на два полных паросочетания, и проверки на тождественное равенство нулю
специального многочлена над достаточно большим полем характертистики 2. Построение базиса паросочетаний позволяет сгруппировать части многочлена и вычислить их быстрее. Если останется время, будет также рассказан вероятностный FPT-алгоритм, параметризованный путевой шириной, со временем работы O*((2 + \sqrt(2))^pw), использующий тот же базис.