Please note: This PhD seminar will take place online.
Stephanie Maaz, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Naomi Nishimura, Amer E. Mouawad
Solution discovery asks whether a given (infeasible) starting configuration to a problem can be transformed into a feasible solution using a limited number b of transformation steps. This paper investigates meta-theorems for solution discovery for graph problems definable in monadic second-order logic (MSO$_1$) and first-order logic (FO) where the transformation step is to slide a token to an adjacent vertex, focusing on parameterized complexity and structural graph parameters that do not involve the transformation budget b.
We present both positive and negative results. On the algorithmic side, we prove that MSO$_1$-Discovery is fixed-parameter tractable when parameterized by neighborhood diversity. On the hardness side, we establish that FO-Discovery is W[1]-hard when parameterized by twin cover number, modulator to stars, or modulator to paths numbers. Additionally, we prove that MSO$_1$-Discovery is W[1]-hard when parameterized by bandwidth.
These results complement the straightforward observation that solution discovery for the studied problems is fixed-parameter tractable when the budget b is included in the parameter (in particular, parameterized by cliquewidth+b, where cliquewidth is at most each of the studied parameters), and provide a near-complete (fixed-parameter tractability) meta-theorems investigation for solution discovery problems for MSO$_1$- and FO-definable graph problems and structural parameters larger than cliquewidth.