ZODIAC: database-independent molecular formula annotation using Gibbs sampling reveals unknown small molecules

Marcus Ludwig; Louis-Félix Nothias; Kai Dührkop; Irina Koester; Markus Fleischauer; Martin A. Hoffmann; Daniel Petras; Fernando Vargas; Mustafa Morsy; Lihini Aluwihare; Pieter C. Dorrestein; Sebastian Böcker

Proof. It is clear that the Multicolored Subgraph problem is in NP. We show that the problem is NP-hard by reduction from Clique 51 : Let G = (V, E) be an undirected, simple graph, is there a clique of size k in G? Clearly, k ≤ n := |V |. We construct a graph H := G K k as the Cartesian graph product of G and the empty graph K k with k nodes and no edges: That is, for every node v ∈ V we generate k copies (v, 1), . . . , (v, k) in H, and there is an edge {(u, i), (v, j)} with i = j in H if and only if there is an edge uv in G. Now, k ≤ n implies that H contains at most n 2 nodes. We dene node colors 1, . . . , k such that c (v, i) = i for v ∈ V and 1 ≤ i ≤ k. We assign zero node weights and unit edge weights for all nodes and edges in H. Now, any assignment in H corresponds to a k-node induced subgraph in G, and the weight of the assignment equals the number of edges in the node-induced subgraph; to this end, an assignment of weight k 2 would correspond to a k-clique in G.