Search Results

Documents authored by Stock, Frederick

Document
DOI: 10.4230/LIPIcs.ESA.2025.28
Sliding Squares in Parallel

Authors: Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.
Cite as

Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding Squares in Parallel. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.28,
  author =	{A. Akitaya, Hugo and Fekete, S\'{a}ndor P. and Kramer, Peter and Molaei, Saba and Rieck, Christian and Stock, Frederick and Wallner, Tobias},
  title =	{{Sliding Squares in Parallel}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.28},
  URN =		{urn:nbn:de:0030-drops-244961},
  doi =		{10.4230/LIPIcs.ESA.2025.28},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, motion planning, multi-agent path finding, makespan, swarm robotics, computational geometry}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2025.85
Finding Shortest Reconfiguration Sequences for Modular Robots (Media Exposition)

Authors: UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
This paper introduces a set of tools built to help researchers design algorithms for modular robots. These tools can brute force solutions to specific reconfigurations, visualize movements of modular robots, and can be used to design specific configurations of robots. Multiple models of modular robots are supported, and can be added by users.
Cite as

UML Modular Robotics Group, Hugo A. Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock. Finding Shortest Reconfiguration Sequences for Modular Robots (Media Exposition). In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 85:1-85:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{umlmodularroboticsgroup_et_al:LIPIcs.SoCG.2025.85,
  author =	{UML Modular Robotics Group and A. Akitaya, Hugo and Clements, Andrew and Downey, Sam and Eisenbies, Jonathan and Samanta, Soham and Shahrouzi, Gabriel and Stock, Frederick},
  title =	{{Finding Shortest Reconfiguration Sequences for Modular Robots}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{85:1--85:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.85},
  URN =		{urn:nbn:de:0030-drops-232371},
  doi =		{10.4230/LIPIcs.SoCG.2025.85},
  annote =	{Keywords: modular reconfigurable robots, sliding cube model, reconfiguration}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.17
Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents

Authors: William K. Moses Jr., Amanda Redlich, and Frederick Stock

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In this paper, we revisit the problem of Broadcast, introduced by Das, Giachoudis, Luccio, and Markou [OPODIS, 2020], where k+1 agents are initially placed on an n node dynamic graph, where 1 agent has a message that must be broadcast to the remaining k ignorant agents. The original paper studied the relationship between the number of agents needed to solve the problem and the edge density of the graph. The paper presented strong evidence that edge density of a graph, or the number of redundant edges within the graph, may be the correct graph property to accurately differentiate whether k = o(n) agents (low edge density) or k = Ω(n) agents (high edge density) are needed to solve the problem. In this paper, we show that surprisingly, edge density is not in fact the differentiating property. The original paper presents graphs with edge density 1.1 ̅{6} that require Ω(n) agents, however, we construct graphs with edge density > 1.1 ̅{6} and develop an algorithm to solve the problem on those graphs using only o(n) agents. We further show that the relationship between edge density and number of agents is fairly weak by first constructing graphs with edge density tending to 1 from above that require Ω(n/f(n)) agents to solve, for any function f(n) → ∞ as n → ∞. We then construct an infinite family of graphs with edge density < ρ requiring exactly k ignorant agents to solve Broadcast, for any k > 0 and ρ > 1. Finally, we investigate different versions of connectivity as possible properties determining the number of agents. We show that edge connectivity is not related to the number of agents: it is possible for a graph to have low (constant) edge connectivity but require a high (linear) number of agents to solve Broadcast. More generally, for any arbitrary λ, we construct a family of graphs on n nodes with edge connectivity (n-1)/λ requiring exactly k = n - 2 λ + 1 agents. On the other hand, we show vertex connectivity can impact the required number of agents: for any graph with vertex connectivity ≥ 3 and minimum degree δ, k ≥ δ - 1 agents are required to solve Broadcast. Finally, we show that for any graph containing a certain type of bond with m edges, Broadcast is unsolvable when k ≤ m-2.
Cite as

William K. Moses Jr., Amanda Redlich, and Frederick Stock. Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 17:1-17:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mosesjr._et_al:LIPIcs.SAND.2025.17,
  author =	{Moses Jr., William K. and Redlich, Amanda and Stock, Frederick},
  title =	{{Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties \& Agents}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{17:1--17:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.17},
  URN =		{urn:nbn:de:0030-drops-230708},
  doi =		{10.4230/LIPIcs.SAND.2025.17},
  annote =	{Keywords: Mobile agents, mobile robots, broadcast, dynamic graph, dynamic network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.4
Minimum Plane Bichromatic Spanning Trees

Authors: Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case.
Cite as

Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth. Minimum Plane Bichromatic Spanning Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2024.4,
  author =	{A. Akitaya, Hugo and Biniaz, Ahmad and Demaine, Erik D. and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D.},
  title =	{{Minimum Plane Bichromatic Spanning Trees}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.4},
  URN =		{urn:nbn:de:0030-drops-221319},
  doi =		{10.4230/LIPIcs.ISAAC.2024.4},
  annote =	{Keywords: Bichromatic Spanning Tree, Minimum Spanning Tree, Plane Tree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.51
Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs

Authors: MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, and Zixiang Zhou

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
To prove #P-hardness, a single-call reduction from #2SAT needs a clause gadget to have exactly the same number of solutions for all satisfying assignments - no matter how many and which literals satisfy the clause. In this paper, we relax this condition, making it easier to find #P-hardness reductions. Specifically, we introduce a framework called Generalized #SAT where each clause contributes a term to the total count of solutions based on a given function of the literals. For two-variable clauses (a natural generalization of #2SAT), we prove a dichotomy theorem characterizing when Generalized #SAT is in FP versus #P-complete. Equipped with these tools, we analyze the complexity of counting solutions to Constraint Graph Satisfiability (CGS), a framework previously used to prove NP-hardness (and PSPACE-hardness) of many puzzles and games. We prove CGS ASP-hard, meaning that there is a parsimonious reduction (with algorithmic bijection on solutions) from every NP search problem, which implies #P-completeness. Then we analyze CGS restricted to various subsets of features (vertex and edge types), and prove most of them either easy (in FP) or hard (#P-complete). Most of our results also apply to planar constraint graphs. CGS is thus a second powerful framework for proving problems #P-hard, with reductions requiring very few gadgets.
Cite as

MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, and Zixiang Zhou. Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.ISAAC.2024.51,
  author =	{MIT Hardness Group and Brunner, Josh and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Hecher, Markus and Stock, Frederick and Zhou, Zixiang},
  title =	{{Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.51},
  URN =		{urn:nbn:de:0030-drops-221790},
  doi =		{10.4230/LIPIcs.ISAAC.2024.51},
  annote =	{Keywords: Counting, Computational Complexity, Sharp-P, Dichotomy, Constraint Graph Satisfiability}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.1
A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

Authors: Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
In the modular robot reconfiguration problem, we are given n cube-shaped modules (or robots) as well as two configurations, i.e., placements of the n modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least Ω(n²) moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm - i.e., we show that any n-module configuration can reconfigure itself into any specified n-module configuration using just sliding moves. Our algorithm achieves reconfiguration in O(n²) moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.
Cite as

Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, and Frederick Stock. A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.SoCG.2024.1,
  author =	{Abel, Zachary and A. Akitaya, Hugo and Kominers, Scott Duke and Korman, Matias and Stock, Frederick},
  title =	{{A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.1},
  URN =		{urn:nbn:de:0030-drops-199468},
  doi =		{10.4230/LIPIcs.SoCG.2024.1},
  annote =	{Keywords: modular reconfigurable robots, sliding cube model, reconfiguration}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact