imported>David Eppstein: Undid revision 1257998436 by Pateldarshak10 (talk) a summary of the main idea is not an application

2024-11-17T17:58:32Z

Undid revision 1257998436 by Pateldarshak10 (talk) a summary of the main idea is not an application

New page

{{about|a technique in the design of graph algorithms|the use of color to display information|color code||Color code (disambiguation)}}
In [[computer science]] and [[graph theory]], the term '''color-coding''' refers to an [[algorithmic technique]] which is useful in the discovery of [[Network motif|network motifs]]. For example, it can be used to detect a [[Path (graph theory)|simple path]] of length {{mvar|k}} in a given [[graph theory|graph]]. The traditional color-coding algorithm is [[probabilistic algorithms|probabilistic]], but it can be [[Derandomization#Derandomization|derandomized]] without much overhead in the running time.

Color-coding also applies to the detection of [[Cycle (graph theory)|cycles]] of a given length, and more generally it applies to the [[subgraph isomorphism|subgraph isomorphism problem]] (an [[NP-complete]] problem), where it yields [[polynomial time|polynomial time algorithms]] when the subgraph pattern that it is trying to detect has bounded [[treewidth]].

The color-coding method was proposed and analyzed in 1994 by [[Noga Alon]], [[Raphael Yuster]], and [[Uri Zwick]].<ref>Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994). STOC '94. ACM, New York, NY, 326–335. DOI= http://doi.acm.org/10.1145/195058.195179</ref><ref name="orig">Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI= http://doi.acm.org/10.1145/210332.210337</ref>

==Results==
The following results can be obtained through the method of color-coding:

* For every fixed constant {{mvar|k}}, if a graph {{math|''G'' {{=}} (''V'', ''E'')}} contains a simple cycle of size {{mvar|k}}, then such a cycle can be found in:
** <math>O(|V|^\omega)</math> expected time, or
** <math>O(|V|^\omega \log |V|)</math> worst-case time, where {{mvar|ω}} is the exponent of [[matrix multiplication]].<ref>[[Coppersmith–Winograd algorithm|Coppersmith–Winograd Algorithm]]</ref>
* For every fixed constant {{mvar|k}}, and every graph {{math|''G'' {{=}} (''V'', ''E'')}} that is in any nontrivial [[Minor (graph theory)#Minor-closed graph families|minor-closed graph family]] (e.g., a [[planar graph]]), if {{mvar|G}} contains a simple cycle of size {{mvar|k}}, then such cycle can be found in:
** {{math|''O''(''V'')}} expected time, or
** {{math|''O''(''V'' log ''V'')}} worst-case time.
* If a graph {{math|''G'' {{=}} (''V'', ''E'')}} contains a subgraph isomorphic to a bounded [[treewidth]] graph which has {{math|''O''(log ''V'')}} vertices, then such a subgraph can be found in [[polynomial time]].

==The method==
To solve the problem of finding a subgraph <math>H = (V_H, E_H)</math> in a given graph {{math|''G'' {{=}} (''V'', ''E'')}}, where {{mvar|H}} can be a path, a cycle, or any bounded [[treewidth]] graph where <math>|V_H| = O(\log |V|)</math>, the method of color-coding begins by randomly coloring each vertex of {{mvar|G}} with <math>k = |V_H|</math> colors, and then tries to find a colorful copy of {{mvar|H}} in colored {{mvar|G}}. Here, a graph is colorful if every vertex in it is colored with a distinct color. This method works by repeating (1) random coloring a graph and (2) finding colorful copy of the target subgraph, and eventually the target subgraph can be found if the process is repeated a sufficient number of times.

Suppose a copy of {{mvar|H}} in {{mvar|G}} becomes colorful with some non-zero probability {{mvar|p}}. It immediately follows that if the random coloring is repeated {{math|{{sfrac|1|''p''}}}} times, then this copy is expected to become colorful once. Note that though {{mvar|p}} is small, it is shown that if <math>|V_H| = O(\log |V|)</math>, {{mvar|p}} is only polynomially small. Suppose again there exists an algorithm such that, given a graph {{mvar|G}} and a coloring which maps each vertex of {{mvar|G}} to one of the {{mvar|k}} colors, it finds a copy of colorful {{mvar|H}}, if one exists, within some runtime {{math|''O''(''r'')}}. Then the expected time to find a copy of {{mvar|H}} in {{mvar|G}}, if one exists, is <math>O(\tfrac{r}{p})</math>.

Sometimes it is also desirable to use a more restricted version of colorfulness. For example, in the context of finding cycles in [[planar graphs]], it is possible to develop an algorithm that finds well-colored cycles. Here, a cycle is well-colored if its vertices are colored by consecutive colors.

===Example===
An example would be finding a simple cycle of length {{mvar|k}} in graph {{math|''G'' {{=}} (''V'', ''E'')}}.

By applying random coloring method, each simple cycle has a probability of <math>k!/k^k > e^{-k}</math> to become colorful, since there are <math>k^k</math> ways of coloring the {{mvar|k}} vertices on the cycle, among which there are <math>k!</math> colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph {{mvar|G}} in time <math>O(V^\omega)</math>, where <math>\omega</math> is the matrix multiplication constant. Therefore, it takes <math>e^k\cdot O(V^\omega)</math> overall time to find a simple cycle of length {{mvar|k}} in {{mvar|G}}.

The colorful cycle-finding algorithm works by first finding all pairs of vertices in {{mvar|V}} that are connected by a simple path of length {{math|''k'' − 1}}, and then checking whether the two vertices in each pair are connected. Given a coloring function {{math|''c'' : ''V'' → {1, ..., ''k''} }} to color graph {{mvar|G}}, enumerate all partitions of the color set {{math|{1, ..., ''k''} }} into two subsets {{math|''C''1, ''C''2}} of size <math>k/2</math> each. Note that {{mvar|V}} can be divided into {{math|''V''1}} and {{math|''V''2}} accordingly, and let {{math|''G''1}} and {{math|''G''2}} denote the subgraphs induced by {{math|''V''1}} and {{math|''V''2}} respectively. Then, recursively find colorful paths of length <math>k/2 - 1</math> in each of {{math|''G''1}} and {{math|''G''2}}. Suppose the boolean matrix {{math|''A''1}} and {{math|''A''2}} represent the connectivity of each pair of vertices in {{math|''G''1}} and {{math|''G''2}} by a colorful path, respectively, and let {{mvar|B}} be the matrix describing the adjacency relations between vertices of {{math|''V''1}} and those of {{math|''V''2}}, the boolean product <math>A_1BA_2</math> gives all pairs of vertices in {{mvar|V}} that are connected by a colorful path of length {{math|''k'' − 1}}. Thus, the recursive relation of matrix multiplications is <math>t(k) \le 2^k\cdot t(k/2)</math>, which yields a runtime of <math>2^{O(k)}\cdot V^\omega</math>. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor<ref>Alon, N. and Naor, M. 1994 Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of Israel.</ref> that finds colorful paths themselves can be incorporated into it.

==Derandomization==
The [[derandomization]] of color-coding involves enumerating possible colorings of a graph {{mvar|G}}, such that the randomness of coloring {{mvar|G}} is no longer required. For the target subgraph {{mvar|H}} in {{mvar|G}} to be discoverable, the enumeration has to include at least one instance where the {{mvar|H}} is colorful. To achieve this, enumerating a {{mvar|k}}-perfect family {{mvar|F}} of hash functions from {{math|{1, ..., {{!}}''V''{{!}}} }} to {{math|{1, ..., ''k''} }} is sufficient. By definition, {{mvar|F}} is {{mvar|k}}-perfect if for every subset {{mvar|S}} of {{math|{1, ..., {{!}}''V''{{!}}} }} where <math>|S| = k</math>, there exists a hash function {{mvar|h}} in {{mvar|F}} such that {{math|''h'' : ''S'' → {1, ..., ''k''} }} is [[perfect hash|perfect]]. In other words, there must exist a hash function in {{mvar|F}} that colors any given {{mvar|k}} vertices with {{mvar|k}} distinct colors.

There are several approaches to construct such a {{mvar|k}}-perfect hash family:

# The best explicit construction is by [[Moni Naor]], [[Leonard J. Schulman]], and [[Aravind Srinivasan]],<ref>Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995). FOCS. IEEE Computer Society, Washington, DC, 182.</ref> where a family of size <math>e^k k^{O(\log k)} \log |V|</math> can be obtained. This construction does not require the target subgraph to exist in the original subgraph finding problem.
# Another explicit construction by [[Jeanette P. Schmidt]] and Alan Siegel<ref name="SS90">{{cite journal | last1 = Schmidt | first1 = J. P. | last2 = Siegel | first2 = A. | year = 1990 | title = The spatial complexity of oblivious k-probe Hash functions | doi = 10.1137/0219054 | journal = SIAM J. Comput. | volume = 19 | issue = 5| pages = 775–786 }}</ref> yields a family of size <math>2^{O(k)}\log^2 |V|</math>.
# Another construction that appears in the original paper of [[Noga Alon]] et al.<ref name="orig" /> can be obtained by first building a {{mvar|k}}-perfect family that maps {{math|{1, ..., {{!}}''V''{{!}}} }} to {{math|{1, ..., ''k''2},}} followed by building another {{mvar|k}}-perfect family that maps {{math|{1, ..., ''k''2} }} to {{math|{1, ..., ''k''}.}} In the first step, it is possible to construct such a family with {{math|2''n''log ''k''}} random bits that are almost {{math|2log ''k''}}-wise independent,<ref>Naor, J. and Naor, M. 1990. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990). H. Ortiz, Ed. STOC '90. ACM, New York, NY, 213-223. DOI= http://doi.acm.org/10.1145/100216.100244</ref><ref>Alon, N., Goldreich, O., Hastad, J., and Peralta, R. 1990. Simple construction of almost k-wise independent random variables. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (October 22–24, 1990). SFCS. IEEE Computer Society, Washington, DC, 544-553 vol.2. {{doi|10.1109/FSCS.1990.89575}}</ref> and the sample space needed for generating those random bits can be as small as <math>k^{O(1)}\log |V|</math>. In the second step, it has been shown by Jeanette P. Schmidt and Alan Siegel<ref name="SS90"/> that the size of such {{mvar|k}}-perfect family can be <math>2^{O(k)}</math>. Consequently, by composing the {{mvar|k}}-perfect families from both steps, a {{mvar|k}}-perfect family of size <math>2^{O(k)}\log |V|</math> that maps from {{math|{1, ..., {{!}}''V''{{!}}} }} to {{math|{1, ..., ''k''} }} can be obtained.

In the case of derandomizing well-coloring, where each vertex on the subgraph is colored consecutively, a {{mvar|k}}-perfect family of hash functions from {{math|{1, ..., {{!}}''V''{{!}}} }} to {{math|{1, ..., ''k''!} }} is needed. A sufficient {{mvar|k}}-perfect family which maps from {{math|{1, ..., {{!}}''V''{{!}}} }} to {{math|{1, ..., ''kk''} }} can be constructed in a way similar to the approach 3 above (the first step). In particular, it is done by using {{math|''nk''log ''k''}} random bits that are almost {{math|''k''log ''k''}} independent, and the size of the resulting {{mvar|k}}-perfect family will be <math>k^{O(k)}\log |V|</math>.

The derandomization of color-coding method can be easily parallelized, yielding efficient [[NC (complexity)|NC]] algorithms.

==Applications==
Recently, color-coding has attracted much attention in the field of bioinformatics. One example is the detection of [[Wnt signaling pathway|signaling pathways]] in [[protein-protein interaction]] (PPI) networks. Another example is to discover and to count the number of [[Structural motif|motifs]] in PPI networks. Studying both [[Wnt signaling pathway|signaling pathways]] and [[Structural motif|motifs]] allows a deeper understanding of the similarities and differences of many biological functions, processes, and structures among organisms.

Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with <math>k=O(\log n)</math> vertices in a network {{mvar|G}} with {{mvar|n}} vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.

==Further reading==

* {{cite journal | last1 = Alon | first1 = N. | last2 = Dao | first2 = P. | last3 = Hajirasouliha | first3 = I. | last4 = Hormozdiari | first4 = F. | last5 = Sahinalp | first5 = S. C. | year = 2008 | title = Biomolecular network motif counting and discovery by color coding | doi = 10.1093/bioinformatics/btn163 | journal = Bioinformatics | volume = 24 | issue = 13| pages = i241–i249 | pmid=18586721 | pmc=2718641}}
* {{cite journal | last1 = Hüffner | first1 = F. | last2 = Wernicke | first2 = S. | last3 = Zichner | first3 = T. | year = 2008 | title = Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection | doi = 10.1007/s00453-007-9008-7 | journal = Algorithmica | volume = 52 | issue = 2| pages = 114–132 | citeseerx = 10.1.1.68.9469 | s2cid = 81069 }}

==References==
{{reflist|2}}

{{DEFAULTSORT:Color-Coding}}
[[Category:Graph algorithms]]

Color-coding - Revision history

imported>David Eppstein: Undid revision 1257998436 by Pateldarshak10 (talk) a summary of the main idea is not an application