## Complexity of graph self-assembly in accretive systems and self-destructible systems

Publication ,  Journal Article
Reif, JH; Sahu, S; Yin, P
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
July 13, 2006

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years see convergent interest and efforts in studying selfassembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretic studies of self-assembly utilize mathematical models with two limitations: 1) only attraction, while no repulsion, is studied; 2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify one fundamental problem in them: the sequential construction of a given graph, referred to as Accretive Graph Assembly Problem (AGAP) and Self-Destructible Graph Assembly Problem (DGAP), respectively. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete. © Springer-Verlag Berlin Heidelberg 2006.

## Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

1611-3349

0302-9743

July 13, 2006

3892 LNCS

## Start / End Page

257 / 274

• Artificial Intelligence & Image Processing
• 46 Information and computing sciences

### Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., Sahu, S., & Yin, P. (2006). Complexity of graph self-assembly in accretive systems and self-destructible systems. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3892 LNCS, 257–274. https://doi.org/10.1007/11753681_21
Reif, J. H., S. Sahu, and P. Yin. “Complexity of graph self-assembly in accretive systems and self-destructible systems.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3892 LNCS (July 13, 2006): 257–74. https://doi.org/10.1007/11753681_21.
Reif JH, Sahu S, Yin P. Complexity of graph self-assembly in accretive systems and self-destructible systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2006 Jul 13;3892 LNCS:257–74.
Reif, J. H., et al. “Complexity of graph self-assembly in accretive systems and self-destructible systems.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3892 LNCS, July 2006, pp. 257–74. Scopus, doi:10.1007/11753681_21.
Reif JH, Sahu S, Yin P. Complexity of graph self-assembly in accretive systems and self-destructible systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2006 Jul 13;3892 LNCS:257–274.

## Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

1611-3349

0302-9743

July 13, 2006

3892 LNCS

257 / 274