6 papers
FO Value Discovery and Partial Vertex Cover Discovery
Enna Gerhard, Stephanie Maaz, Pascale Schott +2
We study solution discovery in the token-sliding model from a logical and cost-value optimization perspective. In solution discovery, we are given a graph, an initial placement of…
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.…
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…
Deterministic Parikh automata on infinite words
Mario Grobler, Sebastian Siebertz
Various variants of Parikh automata on infinite words have recently been introduced in the literature. However, with some exceptions only their non-deterministic versions have been…
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…
Vertex Cover Reconfiguration and Beyond
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman +1
In the Vertex Cover Reconfiguration (VCR) problem, given a graph , positive integers and and two vertex covers and of of size at most , we determine wh…