Matroid паритеті проблемасы - Matroid parity problem - Wikipedia

Matroid паритетінің а графикалық матроид: түрлі-түсті жиектері бар график берілген, әр түске дәл екі шеті бар, қайтадан бір түске екі шеті болатын орманды мүмкіндігінше үлкен табыңыз.

Жылы комбинаторлық оңтайландыру, матроид паритетінің проблемасы а-дағы жұптасқан элементтердің ең үлкен тәуелсіз жиынтығын табу мәселесі матроид.^[1] Мәселе тұжырымдалған Лоулер (1976) жалпы жалпылау ретінде графикалық сәйкестік және матроид қиылысы.^[1][2] Ол сондай-ақ ретінде белгілі полиматроид сәйкес келеді немесе матоидты мәселе.^[3]

Matroid паритетін шешуге болады көпмүшелік уақыт үшін сызықтық матроидтер. Алайда, солай NP-hard ықшам ұсынылған матроидтар үшін, және қадамдардан полиномдық саннан көп талап етеді matroid oracle модель.^[1][4]

Матроидтық паритет алгоритмдерінің қосымшаларына табу жатады үлкен жоспарлы ішкі графиктер^[5] және табу графикалық ендірулер туралы максималды түр.^[6] Бұл алгоритмдерді табуға да қолдануға болады байланысты үстем жиындар және кері байланыс шыңдары жиынтығы максималды дәрежедегі графикте үш.^[7]

Қалыптастыру

A матроид а-дан анықтауға болады ақырлы жиынтық элементтер және келесі шектеулерді ескере отырып, элементтердің ішкі жиынтықтары тәуелсіз болуы нені білдіретіні туралы түсінік:

• Тәуелсіз жиынның кез-келген ішкі бөлігі тәуелсіз болуы керек.
• Егер ${ displaystyle S}$ және ${ displaystyle T}$ тәуелсіз жиындар болып табылады ${ displaystyle | T |> | S |}$, содан кейін элемент бар ${ displaystyle t in T}$ осындай ${ displaystyle S cup {t }}$ тәуелсіз.^[1]

Матроидтардың мысалдарына мыналар жатады сызықтық матроидтер (онда элементтер а-да векторлар болады векторлық кеңістік, бірге сызықтық тәуелсіздік ), графикалық матроидтер (онда элементтері шеттерінде орналасқан бағытталмаған граф, егер олар жоқ болса, тәуелсіз цикл ), және матроидтер бөлімі (онда элементтер отбасына жатады бөлінбеген жиынтықтар, және олар әр жинақтағы ең көп дегенде бір элементтен тұратын кезде тәуелсіз болады). Графикалық матроидтар және бөлу матроидтары - бұл сызықтық матроидтардың ерекше жағдайлары.^[1]

Матроидтық паритет проблемасында кіріс элементтері жұптастырумен бірге матроидтан тұрады, осылайша әр элемент бір жұпқа жатады. Мақсат - таңдалған ішкі жиында жұптардың бірігуі тәуелсіз болатындай етіп, жұптардың ішкі жиынын табу.^[1][2] Рұқсат етілген жұптар бір элементке бір жұп емес, график құрайтын тағы бір жалпы көрінетін вариация эквивалентті болып табылады: бірнеше жұпта пайда болатын элементті элементтердің бірнеше көшірмелерімен алмастыруға болады.^[8]

Алгоритмдер

Сызықтық матроидтар үшін матроидтық паритет мәселесін а арқылы шешуге болады рандомизацияланған алгоритм уақытында ${ displaystyle O (nr ^ { omega -1})}$, қайда ${ displaystyle n}$ матроид элементтерінің саны, ${ displaystyle r}$ оның дәреже (ең үлкен тәуелсіз жиынтықтың мөлшері), және ${ displaystyle omega}$ уақыт шектеріндегі көрсеткіш болып табылады матрицаны жылдам көбейту.^[1]Атап айтқанда, Le Gall матрицасын көбейту алгоритмін пайдаланып,^[9] оны уақытында шешуге болады ${ displaystyle O (nr ^ {1.3729})}$.Тез матрицалық көбейтуді қолданбай, сызықтық матроидтық паритет мәселесін уақытында шешуге болады ${ displaystyle O (nr ^ {2})}$.^[1]

Бұл алгоритмдер а сызықтық алгебра мәселені тұжырымдау Geelen & Iwata (2005). Мәселенің кірісі мынадан тұрады делік ${ displaystyle m}$ жұп ${ displaystyle r}$-өлшемді векторлар (ретке келтірілген баған векторлары ішінде матрица ${ displaystyle M}$ өлшемі ${ displaystyle r рет 2м}$). Сонда оңтайлы шешімдегі жұптардың саны

${ displaystyle { frac {1} {2}} operatorname {rank} { begin {pmatrix} 0 & M M ^ {T} & T end {pmatrix}} - m,}$

қайда ${ displaystyle T}$ Бұл қиғаш матрица оның блоктары ${ displaystyle 2 times 2}$ форманың субматрикалары

${ displaystyle { begin {pmatrix} 0 & t_ {i} - t_ {i} & 0 end {pmatrix}}}$

айнымалылар тізбегі үшін ${ displaystyle t_ {1}, нүктелер t_ {m}}$.^[10] The Шварц-Зиппель леммасы осы матрицаның толық дәрежеге ие екендігін немесе жоқтығын тексеру үшін қолдануға болады (яғни шешімнің мөлшері бар ма) ${ displaystyle r / 2}$ немесе жоқ), айнымалыларға кездейсоқ мәндер беру арқылы ${ displaystyle t_ {i}}$ және алынған матрицаның бар-жоғын тексеру анықтауыш нөл. Қолдану арқылы ашкөздік алгоритмі матрица толық дәрежеде болғанша, олардың анықталмағандықтарын нөлге теңестіру арқылы жұптарды бір-бірлеп алып тастайды (кері матрицаны Шерман-Моррисон формуласы әр алып тастағаннан кейін дәрежесін тексеру үшін), бұл тест оның бар екенін көрсеткен сайын шешім таба алады. Қосымша әдістер бұл алгоритмді матроидтық паритет мәселесінің оңтайлы шешімінен төмен болған жағдайда қолданады ${ displaystyle r / 2}$ жұп.^[1]

Графикалық матроидтар үшін жұмыс уақытының тиімді алгоритмдері белгілі ${ displaystyle O (mn log ^ {6} n)}$ графиктерінде ${ displaystyle m}$ шыңдар және ${ displaystyle n}$ шеттері.^[11]Үшін қарапайым графиктер, ${ displaystyle m}$ болып табылады ${ displaystyle O (n ^ {2})}$, бірақ үшін мультиграфтар, ол үлкенірек болуы мүмкін, сондықтан тәуелділігі аз немесе жоқ алгоритмдердің болуы да қызығушылық тудырады ${ displaystyle m}$ тәуелділік ${ displaystyle n}$. Бұл жағдайда матроидалық паритеттің графикалық есебін рандомизацияланған күтілетін уақытта шешуге болады ${ displaystyle O (n ^ {4})}$немесе уақытында ${ displaystyle O (n ^ {3})}$ жиектердің әр жұбы жол құрған кезде.^[1]

Матроидтық паритет проблемасы болғанымен NP-hard ерікті матроидтар үшін оны әлі де тиімді бағалауға болады. Қарапайым жергілікті іздеу алгоритмдері қамтамасыз ету көпмүшелік-уақытқа жуықтау схемасы осы мәселе үшін және шешім мөлшері оңтайлы шешімнің үлесі ретінде ерікті түрде жақын болатын шешімдерді табыңыз. Алгоритмі басталады бос жиын оның шешімі ретінде және ең көп дегенде тұрақты санды жою арқылы шешім мөлшерін бірнеше рет көбейтуге тырысады ${ displaystyle C}$ ерітіндіден жұптар және оларды басқа жиынтыққа тағы бір жұппен ауыстыру. Енді мұндай қозғалыстар мүмкін болмаса, алынған шешім оңтайлы шешімге жуықтау ретінде қайтарылады. Жуықтау коэффициентіне жету үшін ${ displaystyle 1- epsilon}$, таңдау жеткілікті ${ displaystyle C}$ шамамен болуы керек ${ displaystyle 5 ^ { lceil 1/2 epsilon rceil}}$.^[8]

Қолданбалар

Көптеген басқа оңтайландыру есептері матроидалық паритеттің сызықтық есептері ретінде тұжырымдалуы мүмкін және оларды полиномдық уақыт ішінде осы тұжырымдау көмегімен шешуге болады.

Графикалық сәйкестік

A максималды сәйкестік графикте шеттердің ішкі жиыны бар, екі нүкте де мүмкін емес, олар ең үлкен нүкте. Оны графоидтағы әр шыңның жиілігі үшін элементі бар бөлме матроидтегі матроидтық паритет мәселесі ретінде тұжырымдауға болады. Бұл матроидта екі элемент жұптасады, егер олар бір-бірімен бірдей жиектің екі инциденті болса. Элементтердің жиынтығы графиктің әр шыңы үшін ең көбі бір түсу болса тәуелсіз болады. Осы матроидке арналған матроидтық паритет мәселесін шешудің элементтеріндегі жұптар максималды сәйкестіктегі жиектер мен олардың соңғы нүктелері арасындағы индикциялар болып табылады.^[2]

Матроид қиылысы

Матроидтың қиылысуының мысалы бір элементтер жиынтығында орналасқан екі матроидтан тұрады; мақсат - мүмкіндігінше үлкен және екі матроида да тәуелсіз элементтердің ішкі жиынын табу. Матроид паритетінің проблемасы ретінде матроид қиылысын тұжырымдау үшін элементтері берілген элементтердің екі көшірмесінің бөлшектелген бірігуі болып табылатын жаңа матроид құрыңыз. Жаңа матроидта ішкі жиын тәуелсіз болады, егер оның екі дананың әрқайсысына шектеуі сәйкесінше екі матроидтың әрқайсысында тәуелсіз болса. Жаңа матроид элементтерін әр элемент өзінің көшірмесімен жұптасатындай етіп жұптастырыңыз. Осы матроид үшін матроидтық паритет мәселесін шешудегі элементтердің жұптары матроидтың қиылысу мәселесінің шешіміндегі әрбір элементтің екі данасы болып табылады.^[2]

Үлкен жоспарлы субографиялар

Еркін графикте таңдалған үшбұрыштан басқа циклы жоқ, берілген графиктегі үшбұрыштардың ең үлкен жиынын табу мәселесін, элементтері графиктің шеттері болатын графикалық матроидтегі матроидалық паритет есебі ретінде тұжырымдауға болады. үшбұрыштағы шеттердің жұбы (егер олар бірнеше үшбұрышқа жататын болса, олардың шеттерін қайталау). Осы матроид үшін матроидтық паритет мәселесін шешудегі элементтердің жұптары - бұл үшбұрыштардың оңтайлы жиынтығының әр үшбұрышындағы екі шеті, сол есепті ең үлкенін табудың бірі ретінде де сипаттауға болады. Берге-ациклді 3-форманың ішкі гиперографиясы гиперграф. Есептің гиперграфиялық нұсқасында гипершектер берілген графиктің үшбұрыштары болып табылады.^[3]

A кактус графигі бұл әрбір екі циклде ең көп дегенде бір шыңы бар график. Ерекше жағдай ретінде, әр цикл үшбұрыш болатын графиктер міндетті түрде кактус графикасы болып табылады. Берілген графиктегі ең үлкен үшбұрышты кактус а-дан қосымша жиектер қосу арқылы табылады ағаш, жаңа циклдар жасамай-ақ, нәтижесінде алынған подграф бірдей болады қосылған компоненттер бастапқы график ретінде. Кактус графиктері автоматты түрде болады жазықтық графиктер, және үшбұрышты кактус графиктерін табу мәселесі ең танымалға негіз болады жуықтау алгоритмі берілген графиктің ең үлкен жазықтық субографиясын табу мәселесіне, маңызды қадам жоспарлау. Ең үлкен үшбұрышты кактус әрқашан кем дегенде 4/9 ең үлкен жазықтық субографияның жиектеріне ие, ерікті кеңейтілген ағашты пайдалану арқылы алынған 1/3 жуықтау коэффициентін жақсартады.^[5]

Комбинаторлық қаттылық

Ішіндегі қатты штангалардың қаңқасы Евклидтік жазықтық, икемді түйіспелерде олардың соңғы нүктелерінде жалғанған, оның кейбір буындарын жазықтықтың нүктелеріне бекіту арқылы жазықтықта бір қалыпта бекітілуі мүмкін. Жақтауды бекіту үшін түйреу қажет түйіспелердің минималды саны оның түйреуіш нөмірі деп аталады. Оны шешуден бастап, байланысты матроидтық паритет мәселесіне дейін есептеуге болады.^[3]

Максималды тұқымдық ендіру

A Сюонг ағашы

A ұялы ендіру берілген графиктің мүмкін болатын максималды бетіне түр а-дан алуға болады Сюонг ағашы график. Бұл ағашта емес жиектердің подграфында саны бар қасиеті бар ағаш қосылған компоненттер жиектері тақ санымен мүмкіндігінше аз.

Xuong ағашын матроидалық паритет есебі ретінде табу мәселесін тұжырымдау үшін алдымен әр шетін бөліңіз ${ displaystyle e}$ берілген графиктің жолының ұзындығы басқа шеттердің санына тең болатын жолмен ${ displaystyle e}$. Содан кейін, бөлінген графиктің шеттерін жұптастырыңыз, сонда бастапқы графикадағы шеттердің әрбір жұбы бөлінген графикадағы шеттердің бір жұпымен ұсынылады, ал бөлінген графикадағы әрбір шеттер дәл бір рет жұптасады. Бөлінген графтың жұптасқан шеттерімен матроидалық паритеттің есебін оның когрографиялық матроидін қолданып шешіңіз (егер сызық матроид, егер оның сызбасы графиканы бөліп алмаса, оның жиектері тәуелсіз болады). Матроидтық паритет шешімінде қолданылатын шеттерден аулақ болатын түпнұсқа графиктің кез-келген ағаш ағашы міндетті түрде Сюонг ағашы болып табылады.^[6]

Байланысты үстемдік

A қосылған домин жиынтығы графикте шыңдар жиынтығы, оның индукцияланған субография барлық басқа төбелермен іргелес болып табылады, ерікті графиктердегі ең кіші жалғанған үстемдік жиынтығын табу NP қиын, бірақ максимум үштік графиктер үшін полиномдық уақытта табуға болады. текше график, әрбір шыңды оның үш соңғы нүктесінің ұштарымен байланыстырылған екі жиекті жолмен алмастыруға болады және кеңейтілген графиктің кографиялық матроидасын қолдана отырып, осылайша пайда болған шеттердің жұптарында матроидтық паритет есебін құруға болады. Шешімдерде жолдары қолданылмаған шыңдар минималды байланысқан домин жиынтығын құрайды. Ең жоғары дәрежедегі үш графикте кейбір қарапайым қосымша түрлендірулер есепті текше графикке дейін азайтады.^[7]

Кері байланыс шыңы орнатылды

A кері байланыс шыңы графикте барлық циклдарды қозғайтын шыңдар жиынтығы. Текше графиктерде төбелер санына қатысты сызықтық теңдеу бар, цикломатикалық сан, жалғанған компоненттердің саны, минималды жалғанған доминанттың жиынтығы және минималды кері байланыс шыңының жиынтығы.^[12] Бұдан шығатыны, біріккен үстемдік жиынтықтарды табуға арналған матроидтық паритет проблемасы максимум үштік графиктердегі кері байланыс шыңдары жиынтықтарын табу үшін де қолданыла алады.^[7]

Қаттылық

The клика проблемасы, табу а ${ displaystyle k}$-текс толық ішкі сызба берілген ${ displaystyle n}$-текс сызбасы ${ displaystyle G}$, матроидалық паритеттің данасына төмендегідей түрлендіруге болады матроидты төсеу қосулы ${ displaystyle 2n}$ шыңында бір жұп элемент болатындай етіп жұптастырылған элементтер. Ішкі жиынды анықтаңыз ${ displaystyle S}$ егер ол келесі үш шарттың біреуін қанағаттандырса, осы элементтердің тәуелсіздігі:

• ${ displaystyle S}$ қарағанда аз ${ displaystyle 2k}$ элементтер.
• ${ displaystyle S}$ дәл бар ${ displaystyle 2k}$ элементтері, бірақ бірігу емес ${ displaystyle k}$ элементтер жұбы.
• ${ displaystyle S}$ болып табылады ${ displaystyle k}$ ішіндегі кликті құрайтын жұп элементтер ${ displaystyle G}$.

Осыдан кейін өлшемі бойынша матроид паритеті мәселесін шешуге болады ${ displaystyle 2k}$, егер және егер болса ${ displaystyle G}$ өлшемі бар ${ displaystyle k}$. Берілген өлшемдегі кликтерді табу NP-ге толы болғандықтан, матрицалық паритеттің осы түрінің өлшемінің шешімі бар-жоғын анықтайды. ${ displaystyle 2k}$ сонымен қатар NP-аяқталған.^[13]

Бұл проблеманы түрлендіру кликалық есептің құрылымына терең тәуелді емес және өлшемді табудың кез-келген проблемасы үшін жұмыс істейді.${ displaystyle k}$ есептелетін сынақты қанағаттандыратын үлкен жиынтықтың ішкі жиындары. Мұны кездейсоқ пермутирленген графикке қолдану арқылы өлшемі дәл бір кликаны қолдана отырып ${ displaystyle k}$, тек матроидқа тәуелсіздік тестілері арқылы қол жеткізетін матроидтық паритеттің кез-келген детерминделген немесе рандомизацияланған алгоритмі экспоненциалды тесттер санын жасауы керек екенін көрсетуге болады.^[4]

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