Как найти 2-приближенное решение для максимально ациклического подграфа ориентированного графа?

Question

Как найти 2-приближенное решение для задачи определения максимального подграфа без циклов ориентированного графа? Подграф является «максимальным», если он содержит максимальное количество ребер среди других графов, имеющих такое же свойство.

2-приближенный означает, что мы можем построить в 2 раза меньший график, чем оптимальный. Это довольно значительное сокращение ограничений и должно привести к довольно глупому алгоритму, который - вау! - оказывается только вдвое хуже, чем точное решение.

[Это проблема из экзамена, который я недавно сдал. Больше не домашняя работа.]

Answer 1

Разделите множество узлов на два непустых множества, A и B. Рассмотрим множество ребер от A до B и множество ребер от B до A. Выкиньте ребра из меньшего множества и оставьте ребра из больший набор (разрывать связи произвольно). Рекурсировать на А и Б индивидуально.

Полученный граф является ациклическим, потому что каждый цикл будет разбит при первом разбиении узлов цикла между А и В. Общий набор ребер, которые мы выбрасываем, не больше, чем общий набор ребер, которые мы сохраняем, поэтому выкидывается не более половины ребер.

[примечание: я не думаю, что вы имеете в виду «максимальный» здесь, вы имеете в виду «максимальный». «Максимальный» график обычно означает тот, у которого нет надлежащего надмножества, отвечающего условию. Максимальный ациклический подграф легко построить без фактора аппроксимации, просто добавьте все ребра в новый граф по одному, только если они не добавляют цикл.]

Answer 2

В книге Виджая Вазирани об алгоритмах аппроксимации это рассматривается как первая задача упражнения, для которой он дает очень очевидный намек, который я перефразирую здесь.

1. Произвольное нумерация узлов от 1 до n;
2. Разделить ребра на два комплекта: вперед и назад (больше нет поперечных ребер);
3. Выберите больший набор между прямым набором и обратным набором.

Доказательства правильности и отношения аппроксимации тривиальны.

РЕДАКТИРОВАТЬ: На самом деле решение @Keith Рэндалл является просто вариантом этого, в котором он пронумеровал узлы в множестве A от 1 до | A | и узлы в B из | A | +1 к | A | + | B | и аналогично для рекурсивного случая.