Color-coding

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the term color-coding refers to an <a href="/facts/Algorithmic_technique/9Gyb1FUb">algorithmic technique</a> which is useful in the discovery of <a href="/facts/Network_motif/osqmLDSy">network motifs</a>. For example, it can be used to detect a <a href="/facts/Path_(graph_theory)/WMsq21Nf">simple path</a> of length k in a given <a href="/facts/Graph_theory/VVPCd4TX">graph</a>. The traditional color-coding algorithm is <a href="/facts/Probabilistic_algorithms/Fngl1zgk">probabilistic</a>, but it can be <a href="/facts/Derandomization/Fngl1zgk">derandomized</a> without much overhead in the running time. 
Color-coding also applies to the detection of <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a> of a given length, and more generally it applies to the <a href="/facts/Subgraph_isomorphism/86LLWRg4">subgraph isomorphism problem</a> (an <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problem), where it yields <a href="/facts/Polynomial_time/77T62gmf">polynomial time algorithms</a> when the subgraph pattern that it is trying to detect has bounded <a href="/facts/Treewidth/uoITxzRJ">treewidth</a>.
The color-coding method was proposed and analyzed in 1994 by <a href="/facts/Noga_Alon/tuqq2GUl">Noga Alon</a>, Raphael Yuster, and <a href="/facts/Uri_Zwick/q9cnA3EU">Uri Zwick</a>.

Color-coding open-in-new

Color-coding