This master's thesis explores the color-coding method, an algorithmic technique for solving the subgraph isomorphism problem. This NP-complete problem appears in computer vision, bioinformatics, cheminformatics, and data mining. The thesis begins with an introduction to the theoretical foundations of the subgraph isomorphism problem and its parameterized complexity, followed by a detailed presentation of the color-coding method developed by Noga Alon, Raphael Yuster, and Uri Zwick in 1994. The core of the thesis analyzes various techniques within color-coding: the method of random orientations, the method of random colorings, and the derandomization of these algorithms. Special attention is given to finding vertices of colorful paths using the concept of witnesses in matrix multiplication. The thesis also investigates the extension of the method to finding trees and more complex subgraphs with bounded treewidth. It presents the connection between color-coding and graph degeneracy, with emphasis on minor-closed graph families, where a method for finding cycles is introduced. The conclusion presents advanced strategies for improving the method, including interval-based coloring, the order-and-shift method, the technique of representative sets, and the divide-and-color method. The thesis also includes experimental analysis, where the results of measurements of various color-coding algorithms and other approaches for finding isomorphic subgraphs are presented on practical examples. The master's thesis combines theoretical proofs and algorithms with practical insights into the utility of the color-coding method for solving challenging problems on large graphs.
|
