Уничтожить график за минимальное количество шагов

Question

Существует ориентированный ациклический граф с N вершинами и M ребрами.Цель состоит в том, чтобы уничтожить граф - удалив все его вершины за минимум количество шагов.

---

Правила удаления за один шаг:

1. Можно удалить не более 2 вершин.
2. Вершина может быть удалена, только если у нее нет ребра ни для одной не удаленной вершины.
3. Если две вершины удаляются за один шаг, необходимоне быть гранью между ними.

Ограничения : N, M <= 10 ^ 6, а граф не имеет собственных циклов и циклов. </p>

Answer 1

«Почти линейный алгоритм для двухпроцессорного планирования» ГАРОЛЬДА Н. ГАБОУ дает алгоритм для этого. pdf здесь .

Основная идея состоит в том, чтобы упорядочить вершины в минимальном количестве уровней (каждый уровень - это все вершины, которые могут быть удалены одновременно, если мы игнорируем ограничение 1), а затем сначала удалите вершины самого высокого уровня.

В статье дается больше деталей и доказательство оптимальности.

РЕДАКТИРОВАТЬ

Чтобы увидеть, как планирование связано с данной проблемойрассмотрите планирование набора рабочих мест.Каждое задание соответствует вершине.Зависимости задания соответствуют направленным ребрам.

Ограничение 2/3 соответствует тому, что задание может быть запланировано только после планирования всех зависимостей.

Ограничение 1 соответствует утверждению, что толькоможно запланировать две работы одновременно (т.е. двухпроцессорная система планирования).