Тығыз субография - Dense subgraph

Графиктің мысалы ${ displaystyle G}$ тығыздықпен ${ displaystyle d_ {G} = 1.375}$ және оның шыңдары тудырған тығыз тығыздығы ${ displaystyle b, c, d, e}$ және ${ displaystyle h}$ тығыздығы бар қызылмен ${ displaystyle 1.4}$

Жылы Информатика бір-бірімен тығыз байланысты субографиялар туралы түсінік жиі пайда болады. Бұл ұғымды келесідей формалдауға болады. Келіңіздер ${ displaystyle G = (E, V)}$ болуы бағытталмаған граф және рұқсат етіңіз ${ displaystyle S = (E_ {S}, V_ {S})}$ болуы а подограф туралы ${ displaystyle G}$. Содан кейін тығыздық туралы ${ displaystyle S}$ деп анықталды ${ displaystyle d (S) = {| E_ {S} | over | V_ {S} |}}$.

Ең тығыз графикалық проблема - бұл максималды тығыздықтың подографиясын табу. 1984 жылы, Эндрю В.Голдберг а-ны пайдаланып максималды тығыздықты субографияны табуға арналған полиномдық уақыт алгоритмін жасады максималды ағын техника.

Ең тығыз к подограф

Тығыз графикалық проблемада көптеген вариациялар бар. Олардың бірі - ең тығыз ${ displaystyle k}$ субографиялық проблема, мұнда максималды тығыздықты дәл табу керек ${ displaystyle k}$ төбелер. Бұл проблема жалпыландырады клика проблемасы және осылайша NP-hard жалпы графиктерде. Ең тығызға жуықтайтын полиномдық алгоритм бар ${ displaystyle k}$ қатынасы шегінде ішкі сызба ${ displaystyle n ^ {1/4 + epsilon}}$ әрқайсысы үшін ${ displaystyle epsilon> 0}$,^[1] ол мойындамайды, ал ${ displaystyle n ^ {1 / {{ text {polyloglog}} n}}}$- егер болмаса, көпмүшелік уақыттағы жуықтау экспоненциалды уақыт гипотезасы жалған^[2] Әлсіз болжам бойынша ${ displaystyle NP nsubseteq bigcap _ { epsilon> 0} BPTIME (2 ^ {n ^ { epsilon}})}$, жоқ PTAS проблема үшін бар.^[3]

Мәселе NP қиын болып қалады екі жақты графиктер және аккордтық графиктер бірақ үшін көпмүше болады ағаштар және бөлінген графиктер.^[4] Мәселе NP-қатты немесе көпмүшелік болса да ашық (дұрыс) аралық графиктер және жазықтық графиктер; дегенмен, подографты қосу қажет болатын проблеманың вариациясы жазықтық графикада NP-қиын.^[5]

Ең көп тығыз к подограф

Мақсаты ең тығыз ${ displaystyle k}$ Мәселе - максималды тығыздықтағы максимумды табу ${ displaystyle k}$ төбелер. Андерсон мен Челлапилла егер бар болса, бар екенін көрсетті ${ displaystyle alpha}$ Бұл проблеманың жуықтауы сонда болады ${ displaystyle Theta ( альфа ^ {2})}$ ең тығызға жуықтау ${ displaystyle k}$ субографиялық проблема.

Ең болмағанда тығыз к подограф

Тым тығыз ${ displaystyle k}$ мәселе ең тығызға ұқсас анықталады ${ displaystyle k}$ субографиялық проблема. Мәселе NP-мен аяқталды,^[6] бірақ көпмүшелік уақыттағы 2-жуықтауды қабылдайды.^[7] Сонымен қатар, бұл жуықтау алгоритмінің ең жақсы мүмкін екендігінің кейбір дәлелдері бар: кішігірім жиынтықты кеңейту гипотезасын (болжаммен тығыз байланысты есептеу қиындығының жорамалын) болжау. Бірегей ойындар гипотезасы ), содан кейін проблеманы іштей анықтау NP қиын ${ displaystyle (2- epsilon)}$ әр тұрақтыға арналған фактор ${ displaystyle epsilon> 0}$.^[8]

Қ-қысық тығыз графа

Charalampos Tsourakakis таныстырды ${ displaystyle k}$-кликаның тығыздығы төмен графикалық проблема. Тығыз графикалық проблеманың бұл вариациясы индуцирленген орташа санын максималды етуге бағытталған ${ displaystyle k}$ клиптер ${ displaystyle d_ {k} (S) = {| C_ {k} (S) | over | V_ {S} |}}$, қайда ${ displaystyle C_ {k} (S)}$ жиынтығы ${ displaystyle k}$-байланысты ${ displaystyle S}$. Подтографтың ең тығыз мәселесі арнайы жағдай ретінде алынғанына назар аударыңыз ${ displaystyle k = 2}$. Бұл жалпылау кең ауқымды шынайы желілерден үлкен кликтерді бөліп алуға арналған көп уақытты эмпирикалық сәтті тәсілді ұсынады.

Жергіліктік ең тығыз субография

Цин және басқалар. графикке әрқайсысы өзінің жергілікті аймағында ең жоғары тығыздыққа жететін графикке ең тығыз субографияны табу мәселесін енгізді: ол тығыздығы бірдей немесе одан үлкен суперграфта жоқ, сонымен қатар тығыздығы бар ішкі графиктерді де қамтымайды. жергілікті тығыздағыштың қалған бөлігімен тығыз байланысты. Ең тығыз субографиялық проблема арнайы жағдай ретінде алынғанын ескеріңіз ${ displaystyle k = 1}$. Жергілікті тығыз графиктердің жиынтығын графиктік уақыт бойынша есептеуге болады.

Әдебиеттер тізімі

Әрі қарай оқу