Színkódolás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 14-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A színkódolás egy algoritmikus technika , amely hasznos a szerkezeti motívumok kimutatására . Használható például egy k hosszúságú egyszerű út megkeresésére egy adott gráfban . A hagyományos színkódolási algoritmus valószínűségi , de derandomizálható anélkül, hogy a futási időt jelentősen megnövelné .

A színkódolás alkalmazható adott hosszúságú ciklusok detektálására és általánosabban egy izomorf részgráf megtalálásának problémájára ( NP-complete problem ), ahol polinomiális idő algoritmusokat ad, ha a kívánt részgráf korlátos faszélességű .

A színkódolási módszert 1994-ben Noga Alon , Rafael Yuster és Yuri Zvik javasolta és elemezte [1] [2] .

Eredmények

Színkódolással a következő eredmények érhetők el:

Bármely rögzített k állandó esetén , ha a gráf tartalmaz egy k méretű ciklust , egy ilyen ciklus megtalálható: $G=(V,E)$
- $O(V^{\omega })$ átlagos idő, ill
- $O(V^{\omega }\log V)$ legrosszabb idő, ahol
a mátrixszorzás kitevője [3] . $\omega$

Bármely fix konstanshoz és egy nem triviális gráfcsaládból származó gráfokhoz ( például síkgráfokhoz ), ha G egy egyszerű k méretű ciklust tartalmaz , akkor egy ilyen ciklus megtalálható:

G=(V,E)

O ( V ) átlagos idő, vagy per
O ( V log V ) idő a legrosszabb esetben.

Ha egy gráf olyan részgráfot tartalmaz, amely izomorf egy korlátos faszélességű gráfhoz , amelynek O (log V ) csúcsa van, akkor egy ilyen részgráf polinomidőben található .

G=(V,E)

Módszer

Egy részgráf megtalálásának problémáját egy adott gráfban , ahol H lehet egy útvonal, egy ciklus vagy bármilyen korlátozott faszélességű gráf és , a színkódolási módszer azzal kezdődik, hogy véletlenszerűen színekkel színezi ki a G minden csúcsát , majd megpróbálja megtalálni a H színes másolatát a színes G - ben . Itt egy színes gráf alatt olyan gráfot értünk, amelyben minden csúcs a saját színére van színezve. A módszer úgy működik, hogy megismétli (1) a gráf véletlenszerű színezését, és (2) megkeresi a cél részgráf teljes színű másolatát. Végül a cél részgráfot meg lehet találni, ha a folyamatot elégszer megismétli. $H=(V_{H},E_{H})$ $G=(V,E)$ $|V_{H}|=O(\log V)$ $k=|V_{H}|$

Tételezzük fel, hogy a G-ben szereplő H másolata valamilyen p valószínűséggel teljesen színes lesz . Ebből rögtön az következik, hogy ha a véletlenszerű színezést egyszer megismétlik, akkor ez a másolat egyszer megtörténik. Vegyük észre, hogy még akkor is, ha p valószínűség kicsi, ismert, hogy a p valószínűség csak polinomiálisan kicsi. Tegyük fel, hogy van egy algoritmus, amely adott egy G gráfot és egy színezést, amely G minden csúcsát k szín valamelyikére képezi le , és megkeresi a H teljes színű másolatát , ha létezik, bizonyos időn belül O ( r ) . Ekkor a G -beli H másolatának megtalálásának várható ideje , ha létezik, . ${\tfrac {1}{p}}$ $|V_{H}|=O(\log V)$ $O({\tfrac {r}{p)))$

Néha kívánatos a színséma merevebb változatát használni. Például a síkgráfokban lévő ciklusok keresésével összefüggésben kidolgozhatunk egy algoritmust a jól színezett ciklusok megtalálására. Itt a jól színezett ciklus alatt az egymást követő színekkel történő színezést értjük.

Példa

Példaként vegyük egy k hosszúságú egyszerű ciklus keresését a gráfban . $G=(V,E)$

A véletlenszerű színezési módszer használatakor minden egyszerű ciklusnak megvan az esélye arra, hogy színessé váljon, mivel van mód a ciklus k csúcsának színezésére, amelyek között vannak teljes színű színezés változatai. Ekkor az alábbiakban ismertetett algoritmussal egy véletlenszerűen színezett G gráfban teljes színű ciklusokat találhatunk időben , ahol a mátrixszorzási állandó. Ekkor teljes időbe telik egy k hosszúságú egyszerű ciklus megtalálása G- ben . ${\displaystyle k!/k^{k}>e^{-k))$ ${\displaystyle k^{k))$ $k!$ $O(V^{\omega })$ $\omega$ $e^{k}\cdot O(V^{\omega })$

A színes hurokkereső algoritmus először megkeresi V -ben az összes olyan csúcspárt, amelyeket egy egyszerű k − 1 hosszúságú útvonal köt össze , majd ellenőrzi, hogy minden párban két csúcs össze van-e kapcsolva. Adott egy színezési függvény egy G gráfhoz , számozza át a színkészlet összes partícióját két nagyságú részhalmazra . Minden ilyen partícióhoz legyen a -ból színezett csúcsok halmaza , és -ból színezett csúcsok halmaza . Jelölje és jelölje a és által generált részgráfokat . Rekurzívan keresse meg a és -ben hosszúságú színes útvonalakat . Képzeljük el, hogy a és a logikai mátrixok minden egyes csúcspár összekapcsolását egy színes útvonalon, illetve egy színes útvonalon ábrázolják, és legyen B egy mátrix, amely leírja a csúcsok szomszédságát és , akkor a Boole-szorzat megadja a V -ben lévő összes csúcspárt összekapcsolva egy k − 1 hosszúságú színes pályával . A színhalmaz összes partícióján kapott mátrixok egyesítése adja , ami a futási időhöz vezet . Bár ez az algoritmus csak a színes útvonal végpontjait találja meg, egy másik Alon és Naor [4] algoritmus is használható , amely ténylegesen megtalálja a színes útvonalat. $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 })$

Derandomizálás

Egy színkódolás derandomizálása magában foglalja a G gráf lehetséges színeinek felsorolását, így a G színezésének véletlenszerűvé tételéretöbbé nincs szükség. Ahhoz, hogy meg lehessen találni egy cél H részgráfot G - ben, a felsorolásnak tartalmaznia kell legalább egy olyan esetet, amikor H színes. Ennek eléréséhez elegendő felsorolni a k -tökéletes F hash-függvénycsaládot {1, ..., k } -be. Definíció szerint egy F függvény k -tökéletes, ha a halmaz bármely S részhalmazára, ahol ,létezik egy h hash függvény F - bőlúgy, hogyaz ideális hash függvény . Más szóval, F -ben kell lennie egy hash függvénynek, amely az adott k csúcsot k különböző színnel színezi. $\{1,\dots ,|V|\}$ $\{1,\dots ,|V|\}$ $|S|=k$ ${\displaystyle h\colon S\to \{1,\dots ,k\))$

Számos megközelítés létezik egy ilyen k -ideális hash-család létrehozására:

A legjobb explicit konstrukciót Moni Naor, Leonard J. Shulman és Aravind Srinivasan [5] javasolta , amelyben egy méretű családot kaphatunk . Ez a konstrukció nem igényli, hogy a cél részgráfot az eredeti részgráf-probléma tartalmazza. $e^{k}k^{O(\log k)}\log |V|$
Egy másik explicit konstrukció, amelyet Janetta P. Schmidt és Alan Siegel [6] javasolt, egy méretű családot ad . $2^{O(k)}\log ^{2}|V|$
Egy másik konstrukció, amely Nog Alon és munkatársai [2] eredeti cikkében jelent meg , először úgy érhető el, hogy létrehozunk egy k -tökéletes családot, amely leképeződik -re , majd egy másik k -perfect család megalkotásával, amely -re . Első lépésben létrehozhatunk egy ilyen 2 n log k véletlenszerű bites családot, amely majdnem 2log k -tól független [7] [8] , és a véletlenszerű bitek generálásához szükséges területet korlátozhatjuk . A második lépésben, amint azt Janetta P. Schmidt és Alan Siegel [6] mutatja, egy ilyen k -ideális család mérete lehet . Ezért, ha mindkét lépésből k -ideális családot állítunk össze , egy k -tökéletes méretű családot kaphatunk , amely -től -ig leképez . $\{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\}$

Ideális színezés derandomizálása esetén, amikor a részgráf minden csúcsát szekvenciálisan színezzük, egy k -ideális hash függvénycsaládra van szükség től -ig . Elegendő k -tökéletes családleképezés től -ig a fenti 3. megközelítéshez hasonló módon (első lépés) készíthető. Ez különösen véletlenszerű bitek felhasználásával történik, amelyek szinte függetlenek, és a kapott k -perfect család mérete . $\{1,\dots ,|V|\}$ $\{1,\dots ,k!\}$ $\{1,\dots ,|V|\}$ $\{1,\dots ,k^{k}\}$ $nk\log k$ $k\log k$ $k^{O(k)}\log |V|$

A színkódolási módszer derandomizálása könnyen párhuzamosítható, ami hatékony algoritmusokhoz vezet az NC osztályban .

Alkalmazások

A közelmúltban a színkódolás felkeltette a bioinformatika területén dolgozó tudósok figyelmét. Példa erre a jelátviteli útvonalak meghatározása protein-protein interakciós hálózatokban (PPI). motívumok számának felfedezése és megszámlálása a BPI hálózatokban. A jelátviteli útvonalak és a motívumok tanulmányozása során az lehetővé teszi az organizmusok számos biológiai funkciója, folyamata és szerkezete közötti hasonlóság-különbség mélyebb megértését.

Az összegyűjthető genetikai adatok nagy mennyisége miatt az utak vagy indítékok megtalálása sokáig tarthat. A színkódolási módszert alkalmazva azonban egy n csúcsú G hálózatban csúcsokkal rendelkező motívumok és jelutak nagyon hatékonyan megtalálhatók polinomiális időben. Ez lehetővé teszi a WWW hálózatok bonyolultabb vagy nagyobb struktúráinak feltárását . $k=O(\log n)$

Jegyzetek

↑ Alon, Yuster, Zwick, 1994 , p. 23-25.
↑ 1 2 Alon, Yuster, Zwick, 1995 , p. 844-856.
↑ Lásd Coppersmith-Winograd algoritmus . A mátrixszorzás kitevője a mátrixszorzási algoritmus aszimptotikus komplexitásának mátrixméretének hatványa. $\omega$ $\omega$ $n$
↑ Alon, Naor, 1994 .
↑ Naor, Schulman, Srinivasan, 1995 , p. 182.
↑ 12 Schmidt és Siegel, 1990 , p. 775–786.
↑ Naor, Naor, 1990 , p. 213-223.
↑ Alon, Goldreich, Hastad, Peralta, 1990 , p. 544-553.

Irodalom

Naor J., Naor M. Small-bias valószínűségi terek: hatékony konstrukciók és alkalmazások // Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, Egyesült Államok, 1990. május 13–17.) / H. Ortiz, szerk. - New York, NY: ACM, 1990. - doi : 10.1145/100216.100244 .
Alon N., Goldreich O., Hastad J., Peralta R. Simple construction of majdnem k-wise független valószínűségi változók // Proceedings of the 31st Annual Symposium on Foundations of Computer Science (1990. október 22–24.). SFCS.. - Washington, DC: IEEE Computer Society, 1990. - doi : 10.1109/FSCS.1990.89575 .
Alon N., Yuster R., Zwick U. Színkódolás: új módszer egyszerű utak, ciklusok és más kis részgráfok megtalálására nagy gráfokon belül // Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec) , Kanada, 1994. május 23–25.). STOC '94.. - New York, NY: ACM, 1994. - doi : 10.1145/195058.195179 .
Alon N., Yuster R., Zwick U. Színkódolás. // J. ACM. - 1995. - T. 42 , sz. 4 . - doi : 10.1145/210332.210337 .
Alon N., Naor M. Derandomizáció, Tanúk a Boole-féle mátrixszorzáshoz és a tökéletes hash-függvények felépítéséhez. // technikai jelentés. UMI rendelési szám: 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 (1995. október 23–25.). FOCS.. - Washington, DC: IEEE Computer Society, 1995. - V. 182.
Schmidt JP, Siegel A. The spatial complexity of oblivious k-probe Hash functions // SIAM J. Comput.. - 1990. - Vol. 19 , no. 5 . - doi : 10.1137/0219054 .

Olvasás további olvasáshoz

Alon N., Dao P., Hajirasouliha I., Hormozdiari F., Sahinalp SC Biomolecular network motif counting and discovery by color coding // Bioinformatics. - 2008. - T. 24 , sz. 13 . — S. i241–i249 . - doi : 10.1093/bioinformatika/btn163 . — PMID 18586721 .
Hüffner F., Wernicke S., Zichner T. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection // Algorithmica. - 2008. - T. 52 , sz. 2 . – S. 114–132 . - doi : 10.1007/s00453-007-9008-7 .