14 citations · 69 across the 31 of their papers we have counts for
40 papers
On the complexity of the single-move labeled token routing problem
Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad +1
In neutral-atom quantum computers, atoms are moved to target positions along paths of empty positions, and a target position may be reserved for one species of atom. Motivated by t…
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
Finding Graph Isomorphisms in Heated Spaces in Almost No Time
Sara Najem, Amer E. Mouawad
Determining whether two graphs are structurally identical is a fundamental problem with applications spanning mathematics, computer science, chemistry, and network science. Despite…
Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching
Hussein Amro, Basel Fakhri, Amer E. Mouawad +1
Algorithms for finding minimum or bounded vertex covers in graphs use a branch-and-reduce strategy, which involves exploring a highly imbalanced search tree. Prior GPU solutions as…
On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz +2
Solution discovery asks whether a given (infeasible) starting configuration to a problem can be transformed into a feasible solution using a limited number of transformation steps.…
On the complexity of constrained reconfiguration and motion planning
Nicolas Bousquet, Remy El Sabeh, Amer E. Mouawad +1
Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves ro…
The tape reconfiguration problem and its consequences for dominating set reconfiguration
Nicolas Bousquet, Quentin Deschamps, Arnaud Mary +2
A dominating set of a graph is a set of vertices whose closed neighborhood is , i.e., . We view a dominating set as a collection of tokens plac…
Low-latency control system for feedback experiments with optical tweezer arrays
Amir H. Dadpour, Timur Khayrullin, Fouad Afiouni +4
We present and characterize a modular, open-source system to perform feedback control experiments on configurations of atoms and molecules in arrays of optical tweezers. The system…
Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs
Fouad Afiouni, Remy El Sabeh, Naomi Nishimura +3
We present efficient implementations of atom reconfiguration algorithms for both CPUs and GPUs, along with a batching routine to merge displacement operations for parallel executio…
Kernelization Complexity of Solution Discovery Problems
Mario Grobler, Stephanie Maaz, Amer E. Mouawad +3
In the solution discovery variant of a vertex (edge) subset problem on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph tog…
Parameterized Shortest Path Reconfiguration
Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri +1
An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A…
Solution discovery via reconfiguration for problems in P
Mario Grobler, Stephanie Maaz, Nicole Megow +4
In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of tokens on a graph and the q…
Data reduction for directed feedback vertex set on graphs without long induced cycles
Jona Dirks, Enna Gerhard, Mario Grobler +2
We study reduction rules for Directed Feedback Vertex Set (DFVS) on directed graphs without long cycles. A DFVS instance without cycles longer than naturally corresponds to an…
Minimum Separator Reconfiguration
Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud +4
We study the problem of reconfiguring one minimum --separator into another minimum --separator in some -vertex graph containing two non-adjacent vertices…
On Solution Discovery via Reconfiguration
Michael R. Fellows, Mario Grobler, Nicole Megow +5
The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current…
Efficient algorithms to solve atom reconfiguration problems. II. The assignment-rerouting-ordering (aro) algorithm
Remy El Sabeh, Jessica Bohm, Zhiqian Ding +5
Programmable arrays of optical traps enable the assembly of configurations of single atoms to perform controlled experiments on quantum many-body systems. Finding the sequence of c…
Efficient algorithms to solve atom reconfiguration problems. I. The redistribution-reconfiguration (red-rec) algorithm
Barry Cimring, Remy El Sabeh, Marc Bacvanski +5
We propose the redistribution-reconfiguration (red-rec) algorithm to prepare large configurations of atoms using arrays of dynamic optical traps. Red-rec exploits simple heuristics…
On finding short reconfiguration sequences between independent sets
Akanksha Agrawal, Soumita Hait, Amer E. Mouawad
Assume we are given a graph , two independent sets and in of size , and a positive integer . The goal is to decide whether there exists a sequ…
Combinatorial and Algorithmic Aspects of Monadic Stability
Jan Dreier, Nikolas Mählmann, Amer E. Mouawad +2
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Mon…
Token sliding on graphs of girth five
Valentin Bartier, Nicolas Bousquet, Jihad Hanna +2
In the Token Sliding problem we are given a graph and two independent sets and in of size . The goal is to decide whether there exists a sequence $\la…
A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems
Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura +1
A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices…
Parallel Vertex Cover Algorithms on GPUs
Peter Yamout, Karim Barada, Adnan Jaljuli +2
Finding small vertex covers in a graph has applications in numerous domains. Two common formulations of the problem include: Minimum Vertex Cover, which finds the smallest vertex c…
Galactic Token Sliding
Valentin Bartier, Nicolas Bousquet, Amer E. Mouawad
Given a graph and two independent sets and of size , the independent set reconfiguration problem asks whether there exists a sequence of -sized independent se…
Parameterized complexity of reconfiguration of atoms
Alexandre Cooper, Stephanie Maaz, Amer E. Mouawad +1
Our work is motivated by the challenges presented in preparing arrays of atoms for use in quantum simulation. The recently-developed process of loading atoms into traps results in…