Минимальный k-разрез - Minimum k-cut

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

Формальное определение

Учитывая неориентированный граф грамм = (V, E) с присвоением весов ребрам ш: E → N и целое число k ∈ {2, 3, …, |V|}, раздел V в k непересекающиеся множества F = {C1, C2, …, Ck} при минимизации

Для фиксированного k, проблема в полиномиальное время разрешимый в О(|V|k2).[1] Однако проблема в том, НП-полный если k является частью ввода.[2] Он также является NP-полным, если мы укажем вершины и попросите минимум -разрез, который разделяет эти вершины между каждым из множеств.[3]

Приближения

Несколько аппроксимационные алгоритмы существуют с приближением 2 - 2 /k. Простой жадный алгоритм который достигает этого коэффициента приближения, вычисляет минимальный разрез в каждом из подключенных компонентов и удаляет самый тяжелый. Для этого алгоритма требуется всего п − 1 максимальный поток вычисления. Другой алгоритм, обеспечивающий такую ​​же гарантию, использует Дерево Гомори – Ху представление минимальных сокращений. Для построения дерева Гомори – Ху требуется п - 1 расчет максимального расхода, но алгоритм требует общего О(кн) расчет максимального расхода. Однако коэффициент аппроксимации второго алгоритма легче анализировать.[4][5] Более того, согласно гипотезе о расширении малого множества (гипотеза, тесно связанная с Гипотеза уникальных игр ) задачу NP-трудно аппроксимировать с точностью коэффициент для каждой константы ,[6] это означает, что вышеупомянутые алгоритмы аппроксимации существенно трудны для больших .

Вариант задачи требует минимального веса k-cut, где выходные разделы имеют заранее заданные размеры. Этот вариант задачи аппроксимируется с точностью до 3 для любого фиксированного k если ограничить граф метрическим пространством, то есть полный график что удовлетворяет неравенство треугольника.[7] В последнее время, схемы полиномиальной аппроксимации (PTAS) были обнаружены для этих проблем.[8]

Смотрите также

Примечания

  1. ^ Гольдшмидт и Хохбаум, 1988 г..
  2. ^ Гэри и Джонсон 1979
  3. ^ [1], который цитирует [2]
  4. ^ Саран и Вазирани 1991.
  5. ^ Вазирани 2003 С. 40–44.
  6. ^ Manurangsi 2017
  7. ^ Гуттманн-Бек и Хассин, 1999 г. С. 198–207.
  8. ^ Фернандес де ла Вега, Карпински и Кеньон 2004

Рекомендации

  • Goldschmidt, O .; Хохбаум, Д.С. (1988), Proc. 29-я Ann. IEEE Symp. по основам вычисл. Sci., IEEE Computer Society, стр. 444–451.
  • Garey, M. R .; Джонсон, Д. С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN  978-0-7167-1044-8
  • Saran, H .; Вазирани, В. (1991), "Поиск k-резы в два раза выше оптимального », Proc. 32-я Энн. IEEE Symp. по основам вычисл. Наука, IEEE Computer Society, стр. 743–751.
  • Вазирани, Виджай В. (2003), Алгоритмы аппроксимации, Берлин: Springer, ISBN  978-3-540-65367-7
  • Guttmann-Beck, N .; Хассин, Р. (1999), «Алгоритмы аппроксимации минимума k-резать" (PDF), Алгоритмика, стр. 198–207
  • Comellas, Francesc; Сапена, Эмили (2006), "Мультиагентный алгоритм разбиения графа. Конспект лекций по вычислительным наукам"., Алгоритмика, 3907 (2): 279–285, CiteSeerX  10.1.1.55.5697, Дои:10.1007 / s004530010013, ISSN  0302-9743, заархивировано из оригинал на 2009-12-12
  • Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпинский, Марек; Woeginger, Герхард (2000), «Минимальный k-разрез», Сборник задач оптимизации NP
  • Fernandez de la Vega, W .; Карпинский, М .; Кеньон, К. (2004). «Аппроксимационные схемы для метрического деления пополам и разбиения». Материалы пятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. С. 506–515.CS1 maint: ref = harv (связь)
  • Манурангси, П. (2017). «Неприближаемость максимальной биклики края, максимальной сбалансированной биклики и минимального k-разреза из гипотезы расширения малого набора». 44-й Международный коллоквиум по автоматам, языкам и программированию, ICALP 2017. С. 79: 1–79: 14. Дои:10.4230 / LIPIcs.ICALP.2017.79.CS1 maint: ref = harv (связь)