Для заданного графа в задаче сепаратора задается вопрос, существует ли вершина или множество ребер малой мощности (или веса), удаление которых разбивает на два непересекающихся графа приблизительно равных размеров. Это называется проблемой разделения вершин, когда удаленный набор является набором вершин, и проблемой разделения краев, когда это набор границ. Обе задачи являются NP-полными для общих невзвешенных графов. Какова наиболее известная твердость аппроксимирующего вершинного разделителя? PTAS исключен? Каковы наиболее известные результаты твердости в направленном урегулировании?
Исправление : Следующие ссылки и ответы не помогли мне, потому что я не правильно сформулировал свой вопрос. Мой вопрос связан со следующей теоремой Лейтон-Рао:
Теорема : существует алгоритм полиномиального времени, который, учитывая граф и множество , находит разделитель вершин из в размера , где представляет собой минимальный размер -vertex сепаратора в .
Учитывая граф и множество , я хочу найти разделитель -vertex (где является константой) размера , где минимального размера -vertex сепаратор в . Какова самая известная сложность этой проблемы? Приведенная выше теорема дает приближение для этой задачи.
Обратите внимание, что я разрешаю постоянное увеличение размера результирующих компонентов после удаления разделителя, но я хочу минимизировать размер самого разделителя. Ссылки, упомянутые в комментариях, указывают на минимальный разделитель b-вершин , в котором мы настаиваем на том, что размер результирующих компонентов не превышает .
источник
Ответы:
В настройке ребра проблема, о которой вы говорите, это проблема деления пополам, а размер такого минимального ребра называется шириной деления пополам. Существует множество исследований по этой проблеме, и самое известное приближение для этой проблемы - по Ракке .O ( журналн )
Хороший обзор известной работы по этой проблеме (которая связана с разреженным разрезом, метриками распространения и даже с гипотезой об уникальных играх) содержится в этой недавней статье об обобщении ширины деления пополам Краутгамером, Наором и Шварцем.
источник
источник