Färgkodning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 april 2022; kontroller kräver 8 redigeringar .

Färgkodning är en algoritmisk teknik som är användbar för att upptäcka strukturella motiv . Till exempel kan den användas för att hitta en enkel väg med längden k i en given graf . Den traditionella färgkodningsalgoritmen är probabilistisk , men den kan avrandomiseras utan en signifikant ökning av körtiden .

Färgkodning är också tillämpbar för detektering av cykler av en given längd och, mer allmänt, på problemet med att hitta en isomorf subgraf ( NP-komplett problem ), där den ger polynomtidsalgoritmer om den önskade subgrafen har en begränsad trädbredd .

Färgkodningsmetoden föreslogs och analyserades 1994 av Noga Alon , Rafael Yuster och Yuri Zvik [1] [2] .

Resultat

Följande resultat kan erhållas genom färgkodning:

För varje fast konstant k , om grafen innehåller en cykel av storlek k , kan en sådan cykel hittas i: $G=(V,E)$
- $O(V^{\omega })$ medeltid, eller
- $O(V^{\omega }\log V)$ värsta tiden, var är exponenten
för matrismultiplikation [3] . $\omega$

För vilken fast konstant k som helst och vilken graf som helst från en icke-trivial familj av grafer stängda i moll (som plana grafer ), om G innehåller en enkel cykel av storleken k , så kan en sådan cykel hittas i:

G=(V,E)

O ( V ) medeltid, eller per
O ( V log V ) tid i värsta fall.

Om en graf innehåller en subgraf som är isomorf till en graf med begränsad trädbredd som har O (log V ) hörn, så kan en sådan subgraf hittas i polynomtid .

G=(V,E)

Metod

För att lösa problemet med att hitta en subgraf i en given graf , där H kan vara en bana, en cykel eller vilken graf som helst med begränsad trädbredd , och , börjar färgkodningsmetoden med att slumpmässigt färga varje vertex i G med färger, och sedan försöker hitta en fullfärgskopia av H i det färgade G. _ Här förstås en fullfärgsgraf som en graf där varje vertex är färgad i sin egen färg. Metoden fungerar genom att upprepa (1) en slumpmässig färgläggning av grafen och (2) hitta en fullfärgskopia av målsubgrafen. Så småningom kan målsubgrafen hittas om processen upprepas tillräckligt många gånger. $H=(V_{H},E_{H})$ $G=(V,E)$ $|V_{H}|=O(\log V)$ $k=|V_{H}|$

Antag att en kopia av H i G blir fullfärg med någon sannolikhet som inte är noll p . Av detta följer omedelbart att om den slumpmässiga färgläggningen upprepas en gång, kommer denna kopia att ske en gång. Observera att även när sannolikheten p är liten, är det känt att, eftersom , sannolikheten p endast är polynomiellt liten. Anta att det finns en algoritm som, givet en graf G och en färgning som mappar varje vertex av G till en av k färger, hittar en kopia av fullfärgskopian av H , om den finns, någon gång O ( r ) . Då är den förväntade tiden för att hitta en kopia av H i G , om den finns, . ${\tfrac {1}{p}}$ $|V_{H}|=O(\log V)$ $O({\tfrac {r}{p)))$

Ibland är det önskvärt att använda en mer stel version av färgschemat. Till exempel, i samband med att hitta cykler i plana grafer , kan man utveckla en algoritm för att hitta välfärgade cykler. Här menar vi med en välfärgad cykel färgning med på varandra följande färger.

Exempel

Som ett exempel, låt oss ta sökningen efter en enkel cykel med längden k i grafen . $G=(V,E)$

När du använder den slumpmässiga färgmetoden har varje enkel cykel en chans att bli fullfärgad, eftersom det finns sätt att färga k hörn av cykeln, bland vilka det finns varianter av fullfärgad färg. Sedan kan algoritmen (beskrivs nedan) användas för att hitta fullfärgscykler i en slumpmässigt färgad graf G i tid , där är matrismultiplikationskonstanten. Sedan tar det total tid att hitta en enkel cykel med längden k i G . ${\displaystyle k!/k^{k}>e^{-k))$ ${\displaystyle k^{k))$ $k!$ $O(V^{\omega })$ $\omega$ $e^{k}\cdot O(V^{\omega })$

Sökalgoritmen för helfärgsslingor hittar först alla par av hörn i V som är förbundna med en enkel väg med längden k − 1 , och kontrollerar sedan om två hörn i varje par är anslutna. Givet en färgningsfunktion för en graf G , numrera om alla partitioner i färguppsättningen till två delmängder av storlek ungefär i varje. För varje sådan partition, låt vara uppsättningen av hörn färgade från , och låt vara uppsättningen av hörn färgade från . Låt och beteckna subgraferna som genereras av respektive . Rekursivt hitta fullfärgsbanor av längd i och . Föreställ dig att de booleska matriserna och representerar kopplingen av varje par av hörn i respektive en fullfärgsbana, och låt B vara en matris som beskriver närliggande hörn och , då ger den booleska produkten alla par av hörn i V anslutna med en fullfärgsbana med längden k − 1 . Föreningen av matriserna som erhålls på alla partitioner av färguppsättningen ger , vilket leder till körtiden . Även om denna algoritm bara hittar ändpunkterna för en fullfärgsbana, kan en annan algoritm av Alon och Naor [4] användas som faktiskt hittar fullfärgsbanan. $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

Avrandomisering av en färgkodning innebär att listar möjliga färgningar av grafen G så att randomisering av färgningen av G inte längre behövs. För att kunna hitta en målsubgraf H i G måste uppräkningen inkludera minst ett fall där H är fullfärg. För att få detta räcker det med att räkna upp k -perfektfamiljen F av hashfunktioner fråntill {1, ..., k } . Per definition är en funktion F k -perfekt om för någon delmängd S av mängden, där, det finns en hashfunktion h från F så att denär en idealisk hashfunktion . Med andra ord måste det finnas en hash-funktion i F som färgar de givna k hörnen med k olika färger. $\{1,\dots ,|V|\}$ $\{1,\dots ,|V|\}$ $|S|=k$ ${\displaystyle h\colon S\to \{1,\dots ,k\))$

Det finns flera sätt att konstruera en sådan k -ideal hashfamilj:

Den bästa explicita konstruktionen föreslogs av Moni Naor, Leonard J. Shulman och Aravind Srinivasan [5] , där man kan få en familj av storlek . Denna konstruktion kräver inte att målsubgrafen ingår i det ursprungliga subgrafproblemet. $e^{k}k^{O(\log k)}\log |V|$
En annan explicit konstruktion föreslagen av Janetta P. Schmidt och Alan Siegel [6] ger en familj av storlek . $2^{O(k)}\log ^{2}|V|$
En annan konstruktion, som förekom i den ursprungliga artikeln av Nog Alon et al. [2] , kan erhållas först genom att konstruera en k -perfekt familj som mappar till , med konstruktionen av en annan k -perfekt familj som mappar till . I det första steget kan man konstruera en sådan familj med 2 n log k slumpmässiga bitar som är nästan 2log k -oberoende [7] [8] , och utrymmet som behövs för att generera dessa slumpmässiga bitar kan begränsas av . I det andra steget, som visat av Janetta P. Schmidt och Alan Siegel [6] , kan storleken på en sådan k -ideal familj vara . Genom att komponera k -idealfamiljer från båda stegen kan man därför få en k -perfekt familj av storlek som mappar från till . $\{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 fallet med avrandomisering av ideal färgning, när varje vertex i subgrafen färgas sekventiellt, krävs en k -ideal familj av hashfunktioner från till . En tillräcklig k -perfekt familjeavbildning från till kan konstrueras på ett sätt som liknar tillvägagångssätt 3 ovan (första steget). I synnerhet görs detta med slumpmässiga bitar som är nästan oberoende, och storleken på den resulterande k -perfekta familjen blir . $\{1,\dots ,|V|\}$ $\{1,\dots ,k!\}$ $\{1,\dots ,|V|\}$ $\{1,\dots ,k^{k}\}$ $nk\log k$ $k\log k$ $k^{O(k)}\log |V|$

Avrandomiseringen av färgkodningsmetoden kan lätt parallelliseras, vilket leder till effektiva algoritmer i NC -klassen .

Applikationer

Nyligen har färgkodning uppmärksammats av forskare från bioinformatikområdet. Ett exempel är bestämning av signalvägar i protein-protein-interaktionsnätverk (PPI). Ett annat exempel är upptäckten och räkningen av antalet motiv i BPI-nätverken. När man studerar både signalvägar och motiv , tillåter en djupare förståelse av likhetsskillnaden mellan många biologiska funktioner, processer och strukturer i organismer.

På grund av den stora mängd genetisk data som kan samlas in kan det ta lång tid att hitta vägar eller motiv. Men med hjälp av färgkodningsmetoden kan motiv och signalvägar med hörn i ett nätverk G med n hörn hittas mycket effektivt i polynomtid. Detta gör det möjligt att utforska mer komplexa eller större strukturer i WWW -nätverk . $k=O(\log n)$

Anteckningar

↑ Alon, Yuster, Zwick, 1994 , sid. 23-25.
↑ 1 2 Alon, Yuster, Zwick, 1995 , sid. 844-856.
↑ Se Coppersmith-Winograd-algoritmen . Exponenten för matrismultiplikation är styrkan av matrisstorleken för den asymptotiska komplexiteten hos matrismultiplikationsalgoritmen. $\omega$ $\omega$ $n$
↑ Alon, Naor, 1994 .
↑ Naor, Schulman, Srinivasan, 1995 , sid. 182.
↑ 12 Schmidt och Siegel, 1990 , sid. 775–786.
↑ Naor, Naor, 1990 , sid. 213-223.
↑ Alon, Goldreich, Hastad, Peralta, 1990 , sid. 544-553.

Litteratur

Naor J., Naor M. Små-bias sannolikhetsutrymmen: effektiva konstruktioner och tillämpningar // 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. Enkel konstruktion av nästan k-vis oberoende slumpvariabler // 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. Färgkodning: en ny metod för att hitta enkla vägar, cykler och andra små subgrafer inom stora grafer // Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec) , Kanada, 23–25 maj 1994). STOC '94.. - New York, NY: ACM, 1994. - doi : 10.1145/195058.195179 .
Alon N., Yuster R., Zwick U. Färgkodning. // J. ACM. - 1995. - T. 42 , nr. 4 . - doi : 10.1145/210332.210337 .
Alon N., Naor M. Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. // teknisk rapport. UMI beställningsnummer: CS94-11.,. — Weizmann Science Press of Israel, 1994.
Naor M., Schulman LJ, Srinivasan A. Splitters and near-optimal derandomization // In 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 rumsliga komplexiteten hos omedvetna k-probe Hash-funktioner // SIAM J. Comput.. - 1990. - Vol. 19 , nr. 5 . - doi : 10.1137/0219054 .

Läsning för vidare läsning

Alon N., Dao P., Hajirasouliha I., Hormozdiari F., Sahinalp SC Räkning och upptäckt av biomolekylära nätverksmotiv genom färgkodning // Bioinformatik. - 2008. - T. 24 , nr. 13 . — S. i241–i249 . - doi : 10.1093/bioinformatics/btn163 . — PMID 18586721 .
Hüffner F., Wernicke S., Zichner T. Algoritmteknik för färgkodning med applikationer för detektion av signalvägar // Algorithmica. - 2008. - T. 52 , nr. 2 . — S. 114–132 . - doi : 10.1007/s00453-007-9008-7 .