Покривач чворова

У области математике - теорија графова, покривач чворова за дати граф је такав скуп чворова да су све гране тог графа инцидентне макар једном чвору тог скупа. Проблем налажења минималног покривача чворова је типичан оптимизациони проблем у рачунарству и стандардан је пример НП-тешког оптимизационог проблема који се решава апроксимационим алгоритмом. Одговарајући проблем одлучивања, постојање покривача чворова, је један од Карпових 21 НП-комплетних проблема и самим тиме један од основних НП-комплетних проблема у теорији комплексности.

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

Дефиниција

Формално, покривач чворова неусмереног графа $G=(V,E)$ је подскуп V′ од V такав да ако грана (u, v) припада графу G, онда u припада V′ или v припада V′ или оба чвора припадају V′. Скуп V′ "покрива" гране графа G. Следеће две фигуре приакзују примере покривача чворова два графа (чворови скупа V' су означени црвеном бојом).

Минимални покривач чворова је најмањи такав скуп. Грчким словом $\tau$ означавамо величину минималног скупа покривача чворова. Следеће две фигуре показују минимални скуп покривача чворова.

Примери

• Скуп свих чворова је покривач чворова.
• Чворови било којег скупа независних грана чине покривач чворова.
• За потпуни бипартитивни граф $K_{m,n}$ постоји минимални покривач чворова величине $\tau (K_{m,n})=\min(m,n)$.

Особине

• Скуп чворова V' је покривач чворова ако његов комплемент у односу на скуп свих чворова чини скуп несуседних чворова.
• Број чворова графа је једнак укупном броју чворова минималног покривача грана и максималног скупа несуседних чворова.

Проблем израчунљивости

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

УЛАЗ: Граф $G$

ИЗЛАЗ: Најмање $k$ такво да граф $G$ има покривач чворова величине $k$.

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

УЛАЗ: Граф $G$ природни број $k$.

УПИТ: Да ли граф $G$ поседује покривач чворова величине највише $k$?

Проблем одлучивости покривача чворова је НП-комплетан проблем: је један од Карпових 21 НП-комплетних проблема. Најчешће је коришћен при теорији комплексности при конструкцији доказа НП-тешких проблема.

ЦЛП формулација

Придружимо сваком чвору функцију цене $c(v)\geq 0$. Проблем тежина минималног покривача чворова се дефинише следећим целобројним линеарним програмом (ЦЛП).

minimize	$\sum _{v\in V}c(v)x_{v}$			(минимизује укупну цену)
subject to	$x_{u}+x_{v}\geq 1$	for all $\{u,v\}\in E$		(покрива сваку грану графа)
	$x_{v}\in \{0,1\}$	for all $v\in V$.		(сваки чвор или припада покривачу или не припада)

Овако дефинисан ЦЛП припада општој класи ЦЛП проблема покривача.

Тачно израчунавање

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

Код бипартитивних графова, једнакост проблема покривача чворова и проблема максималног упаривања описаног Кониговом теоремом омогућава решавање проблема покривача грана бипартитивног графа у полиномијалном времену.

Код стабала, похлепни алгоритам налази минимални покривач чворова у полиномијалном времену.

Израчунавање апроксимацијом

Могуће је пронаћи другостепену апроксимацију константним додавањем оба чвора изабране гране у покривач чворова, а затим уклањати их са графа. Дакле, проналазимо максимално упаривање М похлепним алгоритмом и конструишемо покривач чворова C који садржи ова краја свих грана из M. На следећој фигури је максимално упраривање M означено црвеном бојом, а покривач чворова C плавом.

Скуп C, конструисан на овај начин, је покривач чворова: претпоставимо да грана e није покривена скупом C; тада је M ∪ {e} упаривање и e ∉ M, што је контрадикторно претпоставци да је M маскимално упаривање. Даље, ако e = {u, v} ∈ M, тада покривач чворова, укључујући и оптимални покривач, мора садржати u или v (или оба) јер у супротном грана e не би била покривена. Дакле, Оптимални покривач чворова садржи макар један чвор сваке гране из M и укупно, скуп C је највише два пута већи од оптималног покривача чворова.

Овај алгоритам су независно осмислили Фаниша Гаврил и Михалис Јанакакис.

Напредније технике показују да постоји апроксимациони алгоритам са нешто бољим степеном оптимизације. Познат је апроксимизациони алгоритам са степеном апроксимације $2-\Theta \left(1/{\sqrt {\log |V|}}\right)$.

Неапроксимабилност

Није познат алгоритам са бољим костантним степеном апроксимације од горепоменутог. Проблем минималног покривача чворова је АПИкс-комплетан, што значи да се не може произвољно добро осим ако је П = НП. Користећи технике ПЦБ теореме, 2005. године су Динур и Сафра изнели доказ да се минимални покривач чворова не може апроксимизовати степеном мањим од 1.3606 за довољно велики степен чворова осим ако је П = НП.

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

Псеудо кôд

АПРОКСИМАЦИЈА_ПОКРИВАЧА_ЧВОРОВА(G)
C=∅
E'= G.E
докле год је E'≠ ∅

нека је (u,v) произвољна грана из E'

C = C ∪ {u,v}

избаци из E' сваку грану која је инцидентна или са u или са v

врати C

Покривач чворова код хиперграфова

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

Формално, нека је H = (V, E) хиперграф са скупом чворова V и скупом хиперграна E. Тада се скуп S ⊆ V назива ударнички скуп за H ако за све гране e ∈ E важи S ∩ e ≠ ∅. Проблеми теорије израчунљивости минимални ударнички скуп и ударнички скуп дафинисани су исто као у случају графова. Проблем покривача чворова обичног графа је специјалан случај проблема покривача чворова хиперграфа чије су гране степена 2.

Ако ограничимо проблем величином d, проблем налажења минималног d-ударничког скупа се решава d-апроксимационим алгоритмом. Ако претпоставимо предлог јединствених игара, онда је ово најбољи апроксимациони алгоритам констатног степена јер би иначе постојала могућност побољшања апроксимације на d − 1.

Ударнички скуп и покривач чворова

Проблем ударничког скупа је еквивалентат проблему покривача чворова: Инстанца проблема покривача чворова се може посматрати кроз произвољни бипартитивни граф, са скуповима представљеним чворовима лево, елементима универзума представљеним чворовима десно, при чему гране представљају припадност елемената тим скуповима. Задатак је пронаћи подскуп левих чворова минималне кардиналности који покривају све десне чворове. У проблему ударничког скупа, задатак је покрити све леве чворове користећи минимални подскуп десних чворова. Свођење једног проблема на други се постиже заменом једног скупа чворова другим.

Примене

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

Литература

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2013). Introduction to Algorithms. Delhi: PHI Learning Pvt. Ltd. стр. 1109.