11 papers
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…