Твердость вершинных сепараторов

11

Для заданного графа в задаче сепаратора задается вопрос, существует ли вершина или множество ребер малой мощности (или веса), удаление которых разбивает на два непересекающихся графа приблизительно равных размеров. Это называется проблемой разделения вершин, когда удаленный набор является набором вершин, и проблемой разделения краев, когда это набор границ. Обе задачи являются NP-полными для общих невзвешенных графов. Какова наиболее известная твердость аппроксимирующего вершинного разделителя? PTAS исключен? Каковы наиболее известные результаты твердости в направленном урегулировании?граммграмм

Исправление : Следующие ссылки и ответы не помогли мне, потому что я не правильно сформулировал свой вопрос. Мой вопрос связан со следующей теоремой Лейтон-Рао:

Теорема : существует алгоритм полиномиального времени, который, учитывая граф и множество , находит разделитель вершин из в размера , где представляет собой минимальный размер -vertex сепаратора в .грамм(В,Е)WВ23SВWграммО(вес,журналN)вес12Wграмм

Учитывая граф и множество , я хочу найти разделитель -vertex (где является константой) размера , где минимального размера -vertex сепаратор в . Какова самая известная сложность этой проблемы? Приведенная выше теорема дает приближение для этой задачи.грамм(В,Е)WВδ12δ1весвес12WграммО(журналN)

Обратите внимание, что я разрешаю постоянное увеличение размера результирующих компонентов после удаления разделителя, но я хочу минимизировать размер самого разделителя. Ссылки, упомянутые в комментариях, указывают на минимальный разделитель b-вершин , в котором мы настаиваем на том, что размер результирующих компонентов не превышает .|В|/2

Шива Кинтали
источник
1
Я понял, что мои предыдущие комментарии были излишне резкими. Я удалил их. Я оставляю только ссылки в этих комментариях: вершинную версию и граничную версию в Компендиуме задач оптимизации NP.
Цуёси Ито
Меня тоже интересует этот вопрос, вы нашли что-нибудь с тех пор?
Ярослав Булатов
@ Ярослав: Нет. К сожалению, я не смог найти никаких результатов твердости для этой конкретной проблемы.
Шива Кинтали

Ответы:

9

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

Хороший обзор известной работы по этой проблеме (которая связана с разреженным разрезом, метриками распространения и даже с гипотезой об уникальных играх) содержится в этой недавней статье об обобщении ширины деления пополам Краутгамером, Наором и Шварцем.

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

О(журналN)О(журналN)Лейтон и Рао; они сделали это для крайнего случая. Агравал-Чарикар-Макарычев-Макарычев использовал результат, чтобы получить аналогичную оценку для направленного разреженного разреза (если кто-то интересуется разрезами по вершинам с разделением на две части). Feige-Hajiaghayi-Lee в то же время снова получил аналогичную оценку через ARV для разделителей вершин (и также указал, что ширина дерева может быть аппроксимирована в пределах одного и того же фактора). Следует отметить, что существует другое понятие разреженного разреза в ориентированных графах, для которого Чужой-Ханна показал результаты твердости в неоднородном случае, но я не уверен насчет равномерного случая. Я думаю, что сверхпостоянные результаты твердости известны для (равномерного) разреженного разреза под UGC, но я не уверен.

Чандра Чекури
источник