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

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

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

Дан неориентированный граф $G = (V, E)$ с присвоением весов ребрам $w : E \to N$ и целое число $k\in \{2,3,\ldots ,|V|\},$ разбить $V$ на $k$ непересекающиеся множества $F=\{C_{1},C_{2},\ldots ,C_{k}\}$ минимизируя при этом

\sum _{i=1}^{k-1}\ \sum _{j=i+1}^{k}\sum _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})

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

Приближения

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

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

Хотя задача о минимальном $k$ -разрезе является W[1]-трудной, параметризованной $k$ , ^[9] параметризованную схему аппроксимации . для этого параметра можно получить ^[10]

См. также

Примечания

^ Гольдшмидт и Хохбаум 1988 .
^ Гэри и Джонсон 1979
^ [1] , где цитируется [2]
^ Саран и Вазирани 1991 .
^ Вазирани 2003 , стр. 40–44.
^ Мануранси, 2017 г.
^ Гуттманн-Бек и Хассин 1999 , стр. 198–207.
^ Фернандес де ла Вега, Карпински и Кеньон, 2004 г.
^ Г. Дауни, Родни; Эстивилл-Кастро, Владимир; Ребята, Майкл; Прието, Елена ; Розамунд, Фрэнсис А. (1 апреля 2003 г.). «Разрезать сложно: параметризованная сложность k-разреза и связанные с ним проблемы» . Электронные заметки по теоретической информатике . CATS'03, Вычисление: Австралазийский теоретический симпозиум. 78 : 209–222. дои : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .
^ Локштанов Даниил; Саураб, Сакет; Сурианараян, Вайшали (25 апреля 2022 г.). «Схема параметризованной аппроксимации для минимального $k$-Cut» . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . дои : 10.1137/20M1383197 . ISSN 0097-5397 .

Ссылки

Гольдшмидт, О.; Хохбаум, Д.С. (1988), Proc. 29-я Энн. IEEE симп. по основам информатики. наук. , Компьютерное общество IEEE, стр. 444–451.
Гэри, MR; Джонсон, Д.С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1044-8
Саран, Х.; Вазирани, В. (1991), «Нахождение k -разрезов в пределах удвоенного оптимального» , Proc. 32-я Энн. IEEE симп. по основам информатики. Sci , Компьютерное общество IEEE, стр. 743–751.
Vazirani, Vijay V. (2003), Approximation Algorithms , Berlin: Springer, ISBN 978-3-540-65367-7
Гутманн-Бек, Н.; Хассин, Р. (1999), «Алгоритмы аппроксимации минимального k -разреза» (PDF) , Algorithmica , стр. 198–207
Комеллас, Франческ; Сапена, Эмили (2006), «Мультиагентный алгоритм разделения графа. Конспект лекций по информационным технологиям». , Algorithmica , 3907 (2): 279–285, CiteSeerX 10.1.1.55.5697 , doi : 10.1007/s004530010013 , ISSN 0302-9743 , S2CID 25721784 , заархивировано из оригинала 12 декабря 2009 г.
Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000), «Минимальный k-разрез», Сборник задач оптимизации NP
Фернандес де ла Вега, В.; Карпинский, М.; Кеньон, К. (2004). «Аппроксимационные схемы метрического деления пополам и разбиения» . Материалы пятнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 506–515.
Мануранси, П. (2017). «Неприближаемость максимальной краевой биклики, максимальной сбалансированной биклики и минимального k-разреза из гипотезы расширения малого множества». 44-й международный коллоквиум по автоматам, языкам и программированию, ICALP 2017 . стр. 79:1–79:14. doi : 10.4230/LIPIcs.ICALP.2017.79 .

[1] Гольдшмидт и Хохбаум 1988 .

[2] Гэри и Джонсон 1979

[3] [1] , где цитируется [2]

[4] Саран и Вазирани 1991 .

[5] Вазирани 2003 , стр. 40–44.

[6] Мануранси, 2017 г.

[7] Гуттманн-Бек и Хассин 1999 , стр. 198–207.

[8] Фернандес де ла Вега, Карпински и Кеньон, 2004 г.

[9] Г. Дауни, Родни; Эстивилл-Кастро, Владимир; Ребята, Майкл; Прието, Елена ; Розамунд, Фрэнсис А. (1 апреля 2003 г.). «Разрезать сложно: параметризованная сложность k-разреза и связанные с ним проблемы» . Электронные заметки по теоретической информатике . CATS'03, Вычисление: Австралазийский теоретический симпозиум. 78 : 209–222. дои : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .

[10] Локштанов Даниил; Саураб, Сакет; Сурианараян, Вайшали (25 апреля 2022 г.). «Схема параметризованной аппроксимации для минимального $k$-Cut» . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . дои : 10.1137/20M1383197 . ISSN 0097-5397 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]