Paper by Erik D. Demaine
- Erik D. Demaine, Hiro Ito, Jayson Lynch, and Ryuhei Uehara, “Computational Complexity of Flattening Fixed-Angle Orthogonal Chains”, in Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG 2022), Toronto, Ontario, Canada, August 25–27, 2022, to appear.
Planar/flat configurations of fixed-angle chains and trees are well studied in
the context of polymer science, molecular biology, and puzzles. In this
paper, we focus on a simple type of fixed-angle linkage: every edge has unit
length (equilateral), and each joint has a fixed angle of 90° (orthogonal)
or 180° (straight). When the linkage forms a path (open chain), it always
has a planar configuration, namely the zig-zag which alternating the 90°
angles between left and right turns. But when the linkage forms a cycle
(closed chain), or is forced to lie in a box of fixed size, we prove that the
flattening problem — deciding whether there is a planar noncrossing
configuration — is strongly NP-complete.
Back to open chains, we turn to the Hydrophobic–Hydrophilic (HP) model
of protein folding, where each vertex is labeled H or P, and the goal is to
find a folding that maximizes the number of H–H adjacencies. In the
well-studied HP model, the joint angles are not fixed. We introduce and
analyze the fixed-angle HP model, which is motivated by real-world proteins.
We prove strong NP-completeness of finding a planar noncrossing configuration
of a fixed-angle orthogonal equilateral open chain with the most H–H
adjacencies, even if the chain has only two H vertices. (Effectively, this
lets us force the chain to be closed.)
- The paper is 7 pages.
- The paper is available in PDF (471k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by