FO Value Discovery and Partial Vertex Cover Discovery

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 $k$ tokens, and a movement budget $b$. The task is to find a reachable target configuration satisfying a prescribed condition. Our results are inspired by $\text{textsc}PartialVertexCoverDiscovery$, where the condition is that the~$k$ tokens cover at least $t$ edges of the input graph. This objective is not merely a sum of independent occupied vertex contributions: each selected vertex contributes its degree, but edges with both endpoints selected have to be subtracted once. To capture this phenomenon, we introduce $\text{textsc}FOValueDiscovery$, an optimization problem in which the value of a selected tuple is given by unary vertex weights together with first-order definable correction terms. We further generalize the setting to $\text{textsc}FOCost-ValueDecision$, where vertices carry both costs and values, and the task is to decide whether there is a tuple whose first-order value expression reaches a prescribed value threshold while respecting a cost bound. Finally, we study the parameterized complexity of $\text{textsc}PartialVertexCoverDiscovery$ and $\text{textsc}VertexCoverDiscovery$. As a consequence of the logical meta-theorems, we obtain fixed-parameter tractability of $\text{textsc}PartialVertexCoverDiscovery$ on several graph classes, including classes of locally bounded cliquewidth. We also show that $\text{textsc}PartialVertexCoverDiscovery$ is W[1]-hard parameterized by $k+b$ and fixed-parameter tractable on $d$-degenerate graphs parameterized by $k+d$. For $\text{textsc}VertexCoverDiscovery$, we prove NP-hardness on planar graphs, W[1]-hardness parameterized by the clique cover number, even when a clique cover is supplied with the input, and W[1]-hardness with respect to parameter cutwidth.