Cover Image

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bousquet, Nicolas, Mouawad, Amer E., Maaz, Stephanie, Nishimura, Naomi, Siebertz, Sebastian
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

Parameterized complexity of reconfiguration of atoms
by: Cooper, Alexandre, et al.
Published: (2021)

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
by: von Bergen, Hanno, et al.
Published: (2026)

On the complexity of constrained reconfiguration and motion planning
by: Bousquet, Nicolas, et al.
Published: (2025)

Data reduction for directed feedback vertex set on graphs without long induced cycles
by: Dirks, Jona, et al.
Published: (2023)

Parameterized Shortest Path Reconfiguration
by: Bousquet, Nicolas, et al.
Published: (2024)

On girth and the parameterized complexity of token sliding and token jumping
by: Bartier, Valentin, et al.
Published: (2020)

The tape reconfiguration problem and its consequences for dominating set reconfiguration
by: Bousquet, Nicolas, et al.
Published: (2025)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
by: Sharma, Vidya Sagar
Published: (2023)

Algorithmic Extensions of Dirac's Theorem
by: Fomin, Fedor V., et al.
Published: (2020)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Fixed-Parameter Tractable Submodular Maximization over a Matroid
by: Nematollahi, Shamisa, et al.
Published: (2025)

Binary $k$-Center with Missing Entries: Structure Leads to Tractability
by: Soheil, Farehe, et al.
Published: (2025)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
by: Kanellopoulos, Sotiris, et al.
Published: (2026)

Independent set reconfiguration in H-free graphs
by: Bartier, Valentin, et al.
Published: (2024)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
by: Holtgrefe, Niels, et al.
Published: (2026)

Algorithmic Problems in Categories of Partitions
by: Faroß, Nicolas, et al.
Published: (2025)

On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
by: Kumar, Rinku, et al.
Published: (2025)

Reconfiguration of Multisets with Applications to Bin Packing
by: Kam, Jeffrey, et al.
Published: (2024)

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
by: Arenas, Marcelo, et al.
Published: (2024)

Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
by: Mizutani, Yosuke, et al.
Published: (2024)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
by: Tayal, Mumuksh
Published: (2025)

Dynamic Network Discovery via Infection Tracing
by: Bals, Ben, et al.
Published: (2024)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
by: Xu, Xiaojia, et al.
Published: (2024)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

A Levelset Algorithm for 3D-Tarski
by: Haslebacher, Sebastian, et al.
Published: (2025)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
by: Chen, Yixin, et al.
Published: (2025)

Risk-Sensitive Online Algorithms
by: Christianson, Nicolas, et al.
Published: (2024)

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes
by: Green-Maimon, Naomi, et al.
Published: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Global certification via perfect hashing
by: Bousquet, Nicolas, et al.
Published: (2024)

Courcelle's Theorem for Lipschitz Continuity
by: Gima, Tatsuya, et al.
Published: (2025)

Distributed Freeze Tag: a Sustainable Solution to Discover and Wake-up a Robot Swarm
by: Gavoille, Cyril, et al.
Published: (2025)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
by: Honorato-Droguett, Nicolás, et al.
Published: (2023)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)