Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.