Algorithmic Tile Assembly for Solution of the Maximum Clique Problem

The maximum clique problem has diverse applications in the field of pattern recognition, computer vision, information processing etc. The connection between self-assembly and computation has implied that the tile assembly can perform arithmetical computation. Approaches to algorithmic self-assembly require the use of DNA nanostructures, called tiles, which have efficient computational power, and convenient input and output mechanisms. We present a theoretical tile assembly model for the maximum clique problem. We take some transformation to the maximum clique problem and convert it into the 0-1 programming problem. By use of the huge parallelism inherent in the arithmetic tile assembly, it outputs a reporter strand which includes the solution to the problem. It is proved that this method can be extended to the maximum independent set problem and 0-1 programming problem. The arithmetic tile assembly model proposed here can give the answer by use of O(2n(2) + 2mn + 12n) tile types in time linear with the input size.