Color-Coding Techniques In Combinatorics

Color-coding is an important parameterize techniques and it has beenapplied to various fields such likeκ-PATH, subgraph isomorphism, match-ing and packing. Thus, color-coding is a fundamental problem, and itsimprovement will lead to a series of breakthroughs in many other prob-lems. The performance of color-coding based algorithms depends on thenumber of the colorings, thus we should reduce the colorings as much aspossible with the accuracy ensured. Color-coding can be classified into twocategories depending on the coloring set: the randomized one use O(e~κ)random colorings to gain the optimized solution with a relative high proba-bility; while the deterministic one use a larger set named coloring-scheme.The prevalent deterministic algorithms are based on perfect hash functionsand fixed parameter tractable theories. And these methods are being im-proved continually, especially by J. Chen et al., whose algorithm runs intime O~*(6.1~κ).Based on the deep analysis of color-coding theory, the author firstlyproposes a partition-based color-coding algorithm, which can be applied ton≤2κ. Moreover, the efficiency is shown by actual data and the compari-son of the asymptotic bounds with n≤2κproved in this paper. Then, withdivide-and-conquer, perfect-hash and PBCC, the author formulates anotherhybrid-architecture-based color-coding algorithm, which can be applied toarbitrary parameters. Also, the algorithm is proved efficient through actualdata.At last, the author sums up the whole study work on color-coding anddiscusses the further work on some related open problems in this field.