2026-08-25T18:47:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27162 2026-08-25T13:18:16Z ddc:004 open_access

Sliding Cubes in Parallel A. Akitaya, Hugo Dorfer, Joseph Kramer, Peter Rieck, Christian Shahrouzi, Gabriel Stock, Frederick Sliding squares parallel motion reconfigurability three dimensions constant makespan log-APX-hardness NP-hardness worst-case optimality In the classic sliding cube model for programmable matter in three dimensions, the task is to find a reconfiguration sequence between two connected configurations of n indistinguishable unit cube modules by sliding modules along their neighbors' faces. Depending on the objective, this sequence should minimize either the total energy expended (the number of moves) or the total elapsed time (the makespan). We give a number of results for the three-dimensional setting, including (i) the first algorithm that achieves worst-case optimal makespan under parallel motion in three dimensions, (ii) a proof of log-APX-hardness to decide either the optimal makespan or the optimal number of moves, which is the strongest known inapproximability bound in any related model, and (iii) a proof of NP-hardness to decide the optimal makespan under parallel motion, even if the two configurations differ only by one module and the optimal makespan is at most two. Our results strengthen the inapproximability claim from [Hugo A. Akitaya et al., 2022] and answer a question of [Akitaya et al., 2025] in the negative. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Joseph Dorfer and Peter Kramer and Christian Rieck and Gabriel Shahrouzi and Frederick Stock 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.26 urn:nbn:de:0030-drops-271621 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode