Аппроксимационные алгоритмы для максимально независимого множества на специальных классах графов

23

Мы знаем, что максимальный независимый набор (MIS) трудно аппроксимировать с коэффициентом для любого если P = NP. Какие существуют специальные классы графов, для которых известны лучшие алгоритмы аппроксимации? $n^{1-\epsilon}$ $\epsilon > 0$

Каковы графики, для которых известны алгоритмы полиномиального времени? Я знаю, что для совершенных графов это известно, но существуют ли другие интересные классы графов?

ds.algorithms graph-theory graph-algorithms approximation-algorithms Ариндам Пал
источник

1

Точная (не приблизительная) версия этого вопроса: cstheory.stackexchange.com/q/2503/109

Саламон,

19

Существует действительно потрясающий список всех известных классов графов, которые имеют некоторые нетривиальные алгоритмы для MIS: см. Эту запись на веб-сайте классов графов.

Суреш Венкат
источник

8

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

Исинь Цао

Спасибо Суреш. Список довольно полный. Спасибо также Яну за результаты аппроксимации.

Ариндам Пал

2

соответствующие ссылки: Бренда С. Бейкер: Алгоритмы аппроксимации для NP-полных задач на плоских графах. J. ACM 41 (1): 153-180 (1994); Дэвид Эппштейн: диаметр и ширина дерева в семействах минорных замкнутых графов. Algorithmica 27 (3): 275-291 (2000); Эрик Д. Демейн, Мохаммад Таги Хаджиагайи, Кен-ичи Каварабаяши: Алгоритмическая теория малых графов: декомпозиция, аппроксимация и раскраска. ФОКС 2005: 637-646. См. Также: courses.csail.mit.edu/6.889/fall11/lectures/L08.html и courses.csail.mit.edu/6.889/fall11/lectures/L09.html

Кристиан Соммер,

12

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

Если граф имеет вырождение то использование порядка вырождения даст аппроксимацию. следовательно, для графов вырождения мы имеем достаточно хорошее приближение. $d$ $d$ $n^{1-\epsilon}$

Есть несколько других техник для приближений, которые тоже работают, но я не знаю их хорошо. См. Http://en.wikipedia.org/wiki/Baker%27s_technique и http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf.

Для полиномиальных алгоритмов, решающих задачи точно, ссылка Суреша - лучшая. Трудно сказать, какие графические классы интереснее.

Один класс, который вы не найдете в этом списке, является дополнением вырожденных графов. Поскольку максимальная клика может быть решена в на графиках вырождения см. Http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm, особенно работу Эппштейна. Тогда Независимое множество является полиномиальным на G, если дополнение к G имеет вырождение . $k$ $O(2^k n)$ $k$ $O(\log n)$

Мартин Ватшелле
источник

Как сказал Мохаммад Аль-Туркистани в своем ответе, кубические плоские графы являются одним из тех несовершенных графов, где независимое множество может быть аппроксимировано. Все планарные графы имеют вырождение не более 5, а графы рода k имеют вырожденность O (k), и поэтому независимое множество может быть аппроксимировано.

Мартин Ватшелле

5

Для класса кубических плоских графов в настоящей статье Эларби Чухмане и Джона Франко Алгоритм аппроксимации для задачи о максимальном независимом множестве в кубических плоских графах дает алгоритм аппроксимации полиномиального времени. Коэффициент аппроксимации их алгоритма составляет 6/7.

Мухаммед Аль-Туркистани
источник

1

Это уже устарело по методике Бейкера (FOCS'83) в то время, когда она была опубликована в 1986 году

Дэвид Эппштейн

4

Я не проверял ответы выше, поэтому мои извинения, если есть совпадение. Вот особый случай, когда вы можете решить это точно за полиномиальное время. Если ваш граф G является линейным графом , то запустите алгоритм полиномиального времени , чтобы найти корневой граф H, а затем найдите максимальное совпадение в H.

Бабис Цуракакис
источник

Как линейные графы, так и дополнение линейных графов являются полиномиальными и охватываются списком, представленным Сурешем Венкатом.

Мартин Ватшелле

3

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

Эрель Сегал-Халеви
источник

Аппроксимационные алгоритмы для максимально независимого множества на специальных классах графов

Ответы: