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