В докладе будет рассмотрен класс задач разбиения множества на подмножества удовлетворяющие какому-то полиномиально проверяемому свойству. Известен алгоритм, который решает задачу такого вида за 2^n. Так же, известно, что если ограничиться, вместо множеств, графами ограниченной степени, то решение может быть найдено за (2-eps)^n (где eps зависит только от максимальной степени графа). Не так давно был поставлен вопрос, можно ли получить аналогичные оценки для графов ограниченной средней степени.
В докладе будет дан утвердительный ответ для некоторых частных случаев. Будет рассказан метод, позволяющий получить ускорение, в случаи если задача допускает локальные ограничения определенного вида. Будет показано, как с помощью этого метода получить оценки вида (2-eps)^n для задачи коммивояжера и нахождения хроматического числа графа и задачи о поиске кратчайшей надстроки.