Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску

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

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

Для неориентированного графа G  = ( V ,  E ) с присвоением весов ребрам w :  E  →  N и целым числом k  ∈ {2, 3,…, | V |}, разбить V на k непересекающихся множеств F  = { C 1 ,  C 2 ,…,  C k }, минимизируя

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

Приближения

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

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

См. Также

Примечания

  1. ^ Гольдшмидт & Hochbaum 1988 .
  2. ^ Garey & Johnson 1979
  3. ^ [1] , в котором цитируется [2]
  4. ^ Saran & Вазирани 1991 .
  5. ^ Вазирани 2003 , стр. 40-44.
  6. ^ Manurangsi 2017
  7. ^ Guttmann-Бек и Хассин 1999 , стр. 198-207.
  8. ^ Фернандес де ла Вега, Карпински и Кеньон 2004

Ссылки

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