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