Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{FixedAngle_CCCG2022,
  AUTHOR        = {Erik D. Demaine and Hiro Ito and Jayson Lynch and Ryuhei Uehara},
  TITLE         = {Computational Complexity of Flattening Fixed-Angle Orthogonal Chains},
  BOOKTITLE     = {Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG 2022)},
  bookurl       = {https://www.torontomu.ca/canadian-conference-computational-geometry-2022/},
  ADDRESS       = {Toronto, Ontario, Canada},
  MONTH         = {August 25--27},
  YEAR          = 2022,
  PAGES         = {to appear},

  unrefereed    = 1,
  length        = {7 pages},
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineILU22},
  comments      = {The full paper is available as <A HREF="https://arXiv.org/abs/2212.12450">arXiv:2212.12450</A>.},
  papers        = {SnakeCube2D_CCCG2023; HamPath_JIP},
}

Abstract:

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.)

Comments:

The full paper is available as arXiv:2212.12450.

Length:

The paper is 7 pages.

Availability:

The paper is available in PDF (471k).

See information on file formats.

[Google Scholar search]

Related papers:

HamPath_JIP (Finding a Hamiltonian Path in a Cube with Specified Turns is Hard)