Complexity issues in color-preserving graph embeddings (Q846361)

A graph based formalism is used to detect the preservation of a given protein complex in the protein-protein interaction graph of another species with respect to orthologous proteins. The authors give an efficient exponential time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences the authors prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small orthologous numbers, linear forests and very simple yet hard instances.