Farvekodning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. april 2022; checks kræver 8 redigeringer .

Farvekodning er en algoritmisk teknik , der er nyttig til at detektere strukturelle motiver . For eksempel kan det bruges til at finde en simpel vej med længden k i en given graf . Den traditionelle farvekodningsalgoritme er probabilistisk , men den kan de-randomiseres uden en væsentlig stigning i køretid .

Farvekodning er også anvendelig til detektion af cyklusser af en given længde og mere generelt til problemet med at finde en isomorf subgraf ( NP-komplet problem ), hvor den giver polynomiske tidsalgoritmer, hvis den ønskede subgraf har en afgrænset træbredde .

Farvekodningsmetoden blev foreslået og analyseret i 1994 af Noga Alon , Rafael Yuster og Yuri Zvik [1] [2] .

Resultater

Følgende resultater kan opnås ved farvekodning:

For enhver fast konstant k , hvis grafen indeholder en cyklus af størrelse k , kan en sådan cyklus findes i: $G=(V,E)$
- $O(V^{\omega })$ gennemsnitstid, eller
- $O(V^{\omega}\log V)$ værste tid, hvor er eksponenten
for matrixmultiplikation [3] . $\omega$

For enhver fast konstant k og enhver graf fra en ikke-triviel familie af grafer lukket i mol (såsom plane grafer ), hvis G indeholder en simpel cyklus af størrelse k , så kan en sådan cyklus findes i:

G=(V,E)

O ( V ) middeltid, eller pr
O ( V log V ) tid i værste fald.

Hvis en graf indeholder en undergraf, der er isomorf til en afgrænset træbreddegraf, der har O (log V ) toppunkter, så kan en sådan undergraf findes i polynomisk tid .

G=(V,E)

Metode

For at løse problemet med at finde en undergraf i en given graf , hvor H kan være en sti, en cyklus eller en hvilken som helst graf med begrænset træbredde , og , starter farvekodningsmetoden med at farve hvert hjørne tilfældigt i G med farver, og derefter forsøger at finde en fuldfarvekopi af H i den farvelagte G. _ Her forstås en fuldfarvegraf som en graf, hvor hvert hjørne er farvet i sin egen farve. Metoden fungerer ved at gentage (1) en tilfældig farvning af grafen og (2) finde en fuldfarvekopi af målsubgrafen. Til sidst kan målsubgrafen findes, hvis processen gentages nok gange. $H=(V_{H},E_{H})$ $G=(V,E)$ $|V_{H}|=O(\log V)$ $k=|V_{H}|$

Antag, at en kopi af H i G bliver fuldfarve med en sandsynlighed p , der ikke er nul . Heraf følger umiddelbart, at hvis den tilfældige farvelægning gentages én gang, vil denne kopi forekomme én gang. Bemærk, at selv når sandsynligheden p er lille, er det kendt, at sandsynligheden p kun er polynomielt lille. Antag, at der er en algoritme, der givet en graf G og en farve, der afbilder hvert toppunkt af G til en af k farver, finder en kopi af fuldfarvekopi af H , hvis den findes, på et stykke tid O ( r ) . Så er den forventede tid til at finde en kopi af H i G , hvis den findes, . ${\tfrac {1}{p}}$ $|V_{H}|=O(\log V)$ $O({\tfrac {r}{p)))$

Nogle gange er det ønskeligt at bruge en mere stiv version af farveskemaet. For eksempel, i forbindelse med at finde cyklusser i plane grafer , kan man udvikle en algoritme til at finde velfarvede cyklusser. Her mener vi med en velfarvet cyklus farvning med på hinanden følgende farver.

Eksempel

Lad os som et eksempel tage søgningen efter en simpel cyklus med længden k i grafen . $G=(V,E)$

Når du bruger den tilfældige farvningsmetode, har hver enkel cyklus en chance for at blive fuldfarvet, da der er måder at farve k hjørner af cyklussen, blandt hvilke der er varianter af fuldfarvet farvning. Derefter kan algoritmen (beskrevet nedenfor) bruges til at finde fuldfarvecyklusser i en tilfældigt farvet graf G i tid , hvor er matrixmultiplikationskonstanten. Så tager det samlet tid at finde en simpel cyklus med længden k i G . $k!/k^{k}>e^{-k}$ ${\displaystyle k^{k))$ $k!$ $O(V^{\omega })$ $\omega$ $e^{k}\cdot O(V^{\omega })$

Sløjfesøgningsalgoritmen i fuld farve finder først alle par af hjørner i V , der er forbundet med en simpel vej med længden k − 1 , og kontrollerer derefter, om to hjørner i hvert par er forbundet. Givet en farvefunktion for en graf G , omnummerer alle partitioner i farvesættet til to undersæt af størrelse ca. i hver. For hver sådan partition, lad være sættet af hjørner farvet fra , og lad være sættet af hjørner farvet fra . Lad og betegne undergraferne genereret af hhv . Find rekursivt fuldfarvede længdebaner i og . Forestil dig , at de boolske matricer repræsenterer forbindelsen af hvert par af hjørnepunkter i henholdsvis en fuldfarvet sti, og lad B være en matrix, der beskriver tilgrænsende hjørner og , så giver det boolske produkt alle par af knudepunkter i V forbundet ved en fuldfarvebane med længden k − 1 . Foreningen af matricerne opnået på alle partitioner i sættet af farver giver , hvilket fører til køretiden . Selvom denne algoritme kun finder endepunkterne for en fuldfarvesti, kan en anden algoritme af Alon og Naor [4] bruges , som faktisk finder fuldfarvestien. $c\colon V\to \{1,\dots ,k\}$ $\{1,\dots ,k\}$ $C_{1},C_{2}$ $k/2$ $V_{1}$ $C_{1}$ $V_{2}$ $C_{2}$ $G_{1}$ $G_{2}$ $V_{1}$ $V_{2}$ $k/2-1$ $G_{1}$ $G_{2}$ $A_{1}$ $A_{2}$ $G_{1}$ $G_{2}$ $V_{1}$ $V_{2}$ $A_{1}BA_{2}$ $t(k)\leqslant 2^{k}\cdot t(k/2)$ $2^{O(k)}\cdot V^{\omega }=O(V^{\omega })$

Derandomisering

Derandomisering af en farvekodning involverer en liste over mulige farvninger af grafen G , så randomisering af farvningen af G ikke længere er nødvendig. For at kunne finde en målundergraf H i G , skal opregningen omfatte mindst ét tilfælde, hvor H er fuldfarvet. For at få dette er det tilstrækkeligt at opregne den k -perfekte familie F af hashfunktioner fratil {1, ..., k } . Per definition er en funktion F k -perfekt, hvis der for en hvilken som helst delmængde S af sættet, hvor, eksisterer en hashfunktion h fra F , således at dener en ideel hashfunktion . Med andre ord skal der være en hashfunktion i F , der farver de givne k hjørner med k forskellige farver. $\{1,\dots ,|V|\}$ $\{1,\dots ,|V|\}$ $|S|=k$ ${\displaystyle h\colon S\to \{1,\dots ,k\))$

Der er flere tilgange til at konstruere sådan en k -ideal hashfamilie:

Den bedste eksplicitte konstruktion blev foreslået af Moni Naor, Leonard J. Shulman og Aravind Srinivasan [5] , hvor man kan få en familie af størrelse . Denne konstruktion kræver ikke, at målsubgrafen er indeholdt i det originale subgrafproblem. $e^{k}k^{O(\log k)}\log |V|$
En anden eksplicit konstruktion foreslået af Janetta P. Schmidt og Alan Siegel [6] giver en familie af størrelse . $2^{O(k)}\log ^{2}|V|$
En anden konstruktion, som dukkede op i den originale artikel af Nog Alon et al. [2] , kan først opnås ved at konstruere en k -perfekt familie, der afbildes til , med konstruktionen af en anden k -perfekt familie, der afbildes til . På det første trin kan man konstruere sådan en familie med 2 n log k tilfældige bits, der er næsten 2log k -uafhængige [7] [8] , og den plads, der skal til for at generere disse tilfældige bits, kan begrænses af . På det andet trin, som vist af Janetta P. Schmidt og Alan Siegel [6] , kan størrelsen af en sådan k -ideal familie være . Ved at sammensætte k -idealfamilier fra begge trin kan man derfor opnå en k -perfekt familie af størrelse , der kortlægges fra til . $\{1,\dots ,|V|\}$ $\{1,\dots ,k^{2}\}$ $\{1,\dots ,k^{2}\}$ $\{1,\dots ,k\}$ $k^{O(1)}\log |V|$ $2^{O(k)}$ $2^{O(k)}\log |V|$ $\{1,\dots ,|V|\}$ $\{1,\dots ,k\}$

I tilfælde af derandomisering af ideel farvning, når hvert hjørne af subgrafen farves sekventielt, kræves en k - ideal familie af hashfunktioner fra til . En tilstrækkelig k -perfekt familiekortlægning fra til kan konstrueres på en måde svarende til fremgangsmåde 3 ovenfor (første trin). Dette gøres især ved hjælp af tilfældige bits, der er næsten uafhængige, og størrelsen af den resulterende k -perfekte familie vil være . $\{1,\dots ,|V|\}$ $\{1,\dots ,k!\}$ $\{1,\dots ,|V|\}$ $\{1,\dots ,k^{k}\}$ $nk\log k$ $k\log k$ $k^{O(k)}\log |V|$

Derandomiseringen af farvekodningsmetoden kan let paralleliseres, hvilket fører til effektive algoritmer i NC -klassen .

Ansøgninger

For nylig har farvekodning tiltrukket sig opmærksomhed fra forskere inden for bioinformatik. Et eksempel er bestemmelsen af signalveje i protein-protein interaktionsnetværk (PPI'er). Et andet eksempel er opdagelsen og optællingen af antallet af motiver i BPI-netværkene. Når man studerer både signalveje og motiver , tillader en dybere forståelse af lighedsforskellen mellem mange biologiske funktioner, processer og strukturer i organismer.

På grund af den store mængde genetiske data, der kan indsamles, kan det tage lang tid at finde veje eller motiver. Men ved at bruge farvekodningsmetoden kan motiver og signalveje med toppunkter i et netværk G med n toppunkter findes meget effektivt i polynomisk tid. Dette gør det muligt at udforske mere komplekse eller større strukturer i WWW- netværk . $k=O(\log n)$

Noter

↑ Alon, Yuster, Zwick, 1994 , s. 23-25.
↑ 1 2 Alon, Yuster, Zwick, 1995 , s. 844-856.
↑ Se Coppersmith-Winograd-algoritmen . Eksponenten for matrixmultiplikation er styrken af matrixstørrelsen af den asymptotiske kompleksitet af matrixmultiplikationsalgoritmen. $\omega$ $\omega$ $n$
↑ Alon, Naor, 1994 .
↑ Naor, Schulman, Srinivasan, 1995 , s. 182.
↑ 12 Schmidt og Siegel, 1990 , s. 775-786.
↑ Naor, Naor, 1990 , s. 213-223.
↑ Alon, Goldreich, Hastad, Peralta, 1990 , s. 544-553.

Litteratur

Naor J., Naor M. Små-bias sandsynlighedsrum: effektive konstruktioner og anvendelser // Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, USA, 13.-17. maj 1990) / H. Ortiz, red. - New York, NY: ACM, 1990. - doi : 10.1145/100216.100244 .
Alon N., Goldreich O., Hastad J., Peralta R. Simpel konstruktion af næsten k-vise uafhængige stokastiske variable // Proceedings of the 31st Annual Symposium on Foundations of Computer Science (22.–24. oktober 1990). SFCS.. - Washington, DC: IEEE Computer Society, 1990. - doi : 10.1109/FSCS.1990.89575 .
Alon N., Yuster R., Zwick U. Farvekodning: en ny metode til at finde simple stier, cyklusser og andre små undergrafer i store grafer // Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec) , Canada, 23.-25. maj 1994). STOC '94.. - New York, NY: ACM, 1994. - doi : 10.1145/195058.195179 .
Alon N., Yuster R., Zwick U. Farvekodning. // J. ACM. - 1995. - T. 42 , no. 4 . - doi : 10.1145/210332.210337 .
Alon N., Naor M. Derandomisering, Vidner til boolsk matrixmultiplikation og konstruktion af perfekte hashfunktioner. // teknisk rapport. UMI ordrenummer: CS94-11.,. — Weizmann Science Press of Israel, 1994.
Naor M., Schulman LJ, Srinivasan A. Splittere og næsten optimal derandomisering // I Proceedings of the 36th Annual Symposium on Foundations of Computer Science (23.-25. oktober 1995). FOCS.. - Washington, DC: IEEE Computer Society, 1995. - V. 182.
Schmidt JP, Siegel A. Den rumlige kompleksitet af oblivious k-probe Hash-funktioner // SIAM J. Comput.. - 1990. - Vol. 19 , nr. 5 . - doi : 10.1137/0219054 .

Læsning for yderligere læsning

Alon N., Dao P., Hajirasouliha I., Hormozdiari F., Sahinalp SC Optælling og opdagelse af biomolekylære netværksmotiver ved farvekodning // Bioinformatik. - 2008. - T. 24 , no. 13 . — S. i241–i249 . - doi : 10.1093/bioinformatics/btn163 . — PMID 18586721 .
Hüffner F., Wernicke S., Zichner T. Algoritmeteknik for farvekodning med applikationer til detektion af signalveje // Algoritmisk. - 2008. - T. 52 , no. 2 . — S. 114–132 . - doi : 10.1007/s00453-007-9008-7 .