Максимално одсецање

Максимално одсецање

За граф, максимално одсецање је одсецање чија је величина барем једнака величини било ког другог одсецања. Проблем проналажења максималног одсецања у графу познат је као Проблем максималног одсецања.

Проблем се може представити на следећи начин. Желимо да пронађемо подскуп С скупа чворова графа, такав да је број ивица између чворова из С и комплементарног подскупа што већи могући.

Напреднија верзија овог проблема зове се тежинско максимално одсецање. У овој верзији свакој ивици придружен је број, тј. њена тежина, а циљ је постићи максималну тежину ивица између С и његовог комплемента, а не њихов максималан број. Овај проблем је често, али не увек, ограничен тако да су тежине ивица само позитивне вредности, зато што негативне вредности тежина могу променити приподу самог проблема.

Сложеност израчунавања

Проблем одлучивања, који следи, везан за максимална одсецања проучава се у оквиру теоријске информатике:

Дат је граф Г и природни број к, одредити да ли у Г постоји одсецање чија је величина барем к.

За овај проблем је познато да је НП-комплетан. Лако је видети да је проблем у НП: одговор да је лако доказати обезбеђивањем довољно великог одсецања. НП комплетност се може показати, на пример, трансформацијом из максимум 2-задовољивости ( који је рестрикција проблема максималне задовољивости). Верзија проблема одлучивања са тежинама била је један од Карпових 21 НП-комплетних проблема; Карп је показао НП-комплетност редукцијом са проблема партиционисања.

Канонска оптимизациона варијанта горе наведеног проблема одлучивања позната је као Проблем максималног одсецања или Максимално одецање и дефинисана је као:

Дат је граф Г, пронаћи максимално одсецање.

Алгоритми полиномијалног времена

Пошто је Проблем максималног одсецања НП-тежак, нису познати уопштени алгоритми полиномијалног времена за овај проблем.

Међутим, код планарних графова, Проблем максималног одсецања је дуал Проблему испитивања пута (проблем налажења најкраће путање, којом се свака ивица графа посећује барем једном), у смислу да су ивице које не припадају максималном одсецању графа Г дуали ивица које се понављају у оптималном испитивању пута дуалног графа графа Г. Оптимално испитивање пута формира самопресецајућу криву која дели раван на два подскупа, подскуп тачака за које је wиндинг број криве паран и подскуп за које је тај број непаран. Ова два подскупа формирају одсецање које укључује све ивице чији дуали имају непаран број појављивања у путу. Проблем испитивања пута се може решити у полиномијалном времену, а ова дуалност даје могућност да се код планарних графова и Проблем максималног одсецања такође може решити у полиномијалном времену.

Алгоритми апроксимизације

Проблем максималног одсецања је АПX-тежак, што значи да не постоји шема апроксимизације у полиномијалном времену, произвољно близу оптималном решењу, за њега, осим у случају П = НП. Стога, сваки алгоритам апроксимизације у полиномијалном времену има коефицијент апроксимизације стриктно мање од један.

Постоји једноставан насумични 0,5-алгоритам апроксимизације: за сваки чвор бацањем новчића утврдити којој га партицији треба доделити. Очекујемо да половина ивица буду ивице одсецања. Насумичност алгоритма се може избећи применом метода условних вероватноћа; дакле постоји и једноставан детерминистички 0.5-алгоритам апроксимизације полиномијалног времена. Један такав алгоритам почиње са произвољном партицијом чворова датог графа $G=(V,E)$ и помера чворове један по један, у више корака, са једне стране партиције на другу, побољшавајући решење сваким кораком, све док се могу направити побољшања овог типа. Број итерација је највише $|E|$ зато што алгоритам побољшава одсецање барем за једну ивицу сваким кораком. По завршетку алгоритма, најмање половина ивица везаних за све чворове припада одсецању, јер би иначе померање чворова побољшало одсецање. Стога одсецање укључује најмање $|E|/2$ ивица.

Апроксимизациони алгоритам полиномијалног времена са најбољим коефицијентом апроксимизације је метод Гоеманс-а и Wиллиамсон-а користећи семидефинитно програмирање и насумично заокруживање који даје коефицијент апроксимизације $\alpha \approx 0.878$, где је $\alpha ={\tfrac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\tfrac {\theta }{1-\cos \theta }}$. Ако је униqуе гамес претпоставка тачна, ово је најбољи могући коефицијент апроксимизације за максимално одсецање. Без таквих недоказаних претпоставки, доказано је да је НП-тешко апроксимизовати вредност максималног одсецања са коефицијентом апроксимизације бољим од ${\tfrac {16}{17}}\approx 0.941$.

Максимални бипартитивни подграф

Одсецање је бипартитивни граф. Проблем максималног одсецања је у суштини исти као проблем проналажења бипартитивног подграфа са највише ивица.

Нека је $G=(V,E)$ граф и нека је $H=(V,X)$ бипартитивни подграф од Г. Онда постоји партиција (С, Т) V таква да свака ивица у X има једну тачку у С а другу у Т. Другим речима, постоји одсецање у Х такво да скуп ивица одсецања садржи X. Дакле постоји одсецање у графу Г такво да је скуп ивица одсецања надскуп од X.

Обрнуто, нека је $G=(V,E)$ граф и нека је X скуп ивица одсецања. Онда је матх>Х=(V,X)</матх> бипартитивни подграф од Х.

Укратко, ако постоји бипартитивни граф са к ивица, постоји одсецање са барем к ивица одсецања, и ако постоји одсецање са к ивица, постоји и бипартитивни граф са к ивица.

Стога је проблем проналажења максималног бипартитивног подграфа суштински исти као проблем проналажења максималног одсецања.

Литература

• Аусиелло, Гиоргио; Цресцензи, Пиерлуиги; Гамбоси, Гиоргио; Канн, Вигго; Марцхетти-Спаццамела, Алберто; Протаси, Марцо (2003), Цомплеxитy анд Аппроxиматион: Цомбинаториал Оптимизатион Проблемс анд Тхеир Аппроxимабилитy Пропертиес, Спрингер .

Маxимум цут (оптимисатион версион) ис тхе проблем НД14 ин Аппендиx Б (пп. 399).

• Гареy, Мицхаел Р.; Јохнсон, Давид С. (1979), Цомпутерс анд Интрацтабилитy: А Гуиде то тхе Тхеорy оф НП-Цомплетенесс, W.Х. Фрееман, ИСБН 978-0-7167-1045-5 .

Маxимум цут (децисион версион) ис тхе проблем НД16 ин Аппендиx А2.2.

Маxимум бипартите субграпх (децисион версион) ис тхе проблем ГТ25 ин Аппендиx А1.2.

• Гаур, Даyа Рам; Крисхнамурти, Рамесх (2007), „ЛП роундинг анд еxтенсионс”, Ур.: Гонзалез, Теофило Ф., Хандбоок оф Аппроxиматион Алгоритхмс анд Метахеуристицс, Цхапман & Халл/ЦРЦ .
• Гоеманс, Мицхел X.; Wиллиамсон, Давид П. (1995), „Импровед аппроxиматион алгоритхмс фор маxимум цут анд сатисфиабилитy проблемс усинг семидефините программинг”, Јоурнал оф тхе АЦМ, 42 (6): 1115—1145, дои:10.1145/227683.227684 .
• Хадлоцк, Ф. (1975), „Финдинг а Маxимум Цут оф а Планар Грапх ин Полyномиал Тиме”, СИАМ Ј. Цомпут., 4 (3): 221—225, дои:10.1137/0204019 .
• Хåстад, Јохан (2001), „Соме оптимал инаппроxимабилитy ресултс”, Јоурнал оф тхе АЦМ, 48 (4): 798—859, дои:10.1145/502090.502098 .
• Јансен, Клаус; Карпински, Марек; Лингас, Андрзеј; Сеидел, Еике (2005), „Полyномиал Тиме Аппроxиматион Сцхемес фор МАX-БИСЕЦТИОН он Планар анд Геометриц Грапхс”, СИАМ Јоурнал он Цомпутинг, 35 (1), дои:10.1137/с009753970139567x .
• Карп, Рицхард M. (1972), „Редуцибилитy амонг цомбинаториал проблемс”, Ур.: Миллер, Р. Е.; Тхацхер, Ј. W., Цомплеxитy оф Цомпутер Цомпутатион, Пленум Пресс, стр. 85—103 .
• Кхот, Субхасх; Киндлер, Гуy; Моссел, Елцханан; О'Доннелл, Рyан (2007), „Оптимал инаппроxимабилитy ресултс фор МАX-ЦУТ анд отхер 2-вариабле ЦСПс?”, СИАМ Јоурнал он Цомпутинг, 37 (1): 319—357, дои:10.1137/С0097539705447372 .
• Кхуллер, Самир; Рагхавацхари, Балаји; Yоунг, Неал Е. (2007), „Греедy метходс”, Ур.: Гонзалез, Теофило Ф., Хандбоок оф Аппроxиматион Алгоритхмс анд Метахеуристицс, Цхапман & Халл/ЦРЦ .
• Митзенмацхер, Мицхаел; Упфал, Ели (2005), Пробабилитy анд Цомпутинг: Рандомизед Алгоритхмс анд Пробабилистиц Аналyсис, Цамбридге .
• Мотwани, Рајеев; Рагхаван, Прабхакар (1995), Рандомизед Алгоритхмс, Цамбридге .
• Неwман, Алантха (2008), „Маx цут”, Ур.: Као, Минг-Yанг, Енцyцлопедиа оф Алгоритхмс, Спрингер, стр. 1, ИСБН 978-0-387-30770-1, дои:10.1007/978-0-387-30162-4_219 .
• Пападимитриоу, Цхристос Х.; Yаннакакис, Михалис (1991), „Оптимизатион, аппроxиматион, анд цомплеxитy цлассес”, Јоурнал оф Цомпутер анд Сyстем Сциенцес, 43 (3): 425—440, дои:10.1016/0022-0000(91)90023-X .
• Тревисан, Луца; Соркин, Грегорy; Судан, Мадху; Wиллиамсон, Давид (2000), „Гадгетс, Аппроxиматион, анд Линеар Программинг”, Процеедингс оф тхе 37тх ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце: 617—626 .

Спољашње везе

• Пиерлуиги Цресцензи, Вигго Канн, Магнúс Халлдóрссон, Марек Карпински, Герхард Wоегингер (2000), "Маxимум Цут", ин "А цомпендиум оф НП оптимизатион проблемс".
• Андреа Цасини, Ницола Ребаглиати (2012), "А Пyтхон либрарy фор солвинг Маx Цут"