Здравствуйте! Я не знаю доказательство этого алгоритма(( Если кто-то знает, можете пожалуйста написать доказательство в комментариях.
Алгоритм:
1) Первым шагом строим Транзитивное замыкание графа (если из A был путь в B, то в этом графе будет ребро из A в B).
2) "Копируем граф". Теперь у каждой вершины будет копия. Если в графе (в том, который мы получили после предыдущего шага) было ребро из A в B, то теперь есть ребро из вершины A, которая находится в левой доле в вершину B, которая находится в правой доле. (По сути теперь у вершины A есть две вершины: AL и AR)
3) В получившемся графе ищем максимальное независимое множество.
4) Теперь если и VR, и VL лежат в независимом множестве, то мы берем V в антицепь.