Как известно, вычисление постоянной Чигера для графика , также известного как изопериметрическая постоянная (поскольку это, по сути, минимальное отношение площади / объема), является NP-полным. Вообще это приблизительно. Мне интересно узнать, известны ли точные полиномиальные алгоритмы для специальных классов графов. Например, все еще NP-полный для регулярных графов ? Для дистанционно регулярных графиков ? (Я не изучал существующие доказательства NP-полноты, чтобы проверить их предположения.) Литературные указатели оценили - спасибо!
ds.algorithms
reference-request
graph-algorithms
Джозеф О'Рурк
источник
источник
Ответы:
Обратите внимание, что аппроксимация разреженного разреза с точностью до дает приближение 2 α для постоянной Чигера, как определено. Вот некоторые статьи, которые дают алгоритмы с постоянной аппроксимацией для разреженного разреза в ограниченных графах:α 2 α
Ограниченный род: http://dl.acm.org/citation.cfm?id=1873619
Ограниченная ширина дерева: http://arxiv.org/abs/1006.3970
Кроме того, http://arxiv.org/abs/1006.3970v2 доказывает, что разреженный разрез является NP-сложным для графов с шириной пути 2 и имеет еще несколько ссылок на аппроксимацию разреженного разреза в ограниченных случаях.
Я предположил бы, что для всех классов графов, упомянутых в статье, точные алгоритмы не известны (поскольку они интересуются приближениями). В частности, если разреженный разрез является NP-сложным для графиков с шириной пути 2, то он также является NP-сложным для графиков с шириной дерева 2 и шириной вырезания 2. Я полагаю, что это не дает достаточно много места ... может быть, есть еще лучший вариант параметризация для разреженного разреза.
Я почти уверен, что на регулярных графиках разреженный срез является NP-сложным, но не могу найти ссылку.
Пер заметил, что я не был осторожен, когда посмотрел на бумаги выше. Результат твердости для неоднородного разреженного разреза. Вычислить равномерный разреженный срез или постоянную Чигера на деревьях легко (WLOG - оптимальный срез разделяет поддерево). Немного больше работы, которая дает алгоритм динамического программирования для вычисления константы Чигера на ограниченных графах длины дерева.
Таблица 1 в статье 2 выше также упоминает результат, который дает постоянную аппроксимацию для графов с исключенным несовершеннолетним.
источник
Точное решение на плоских графиках см. В Park and Phillips, STOC 93 . Это по существу для разреженных требований с равномерным распределением, с незначительным отличием в том, что их знаменатель равен | S | вместо | S | * | VS |. Как указывает Пер, случай неоднородных требований отличается.
источник