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

Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz, Naomi Nishimura, Sebastian Siebertz · 2025

Read On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers by Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz, Naomi Nishimura, Sebastian Siebertz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17344.txt.

Introduction

Some graph problems start from a broken layout that must be repaired by sliding tokens along edges, step by step, within a small budget of moves. Nicolas Bousquet and four co-authors ask when such repair tasks, called solution discovery, can be solved efficiently for whole families of problems stated in formal logic. Their focus is on which structural measures of a graph make the task tractable.

Bousquet and his co-authors prove positive results for two logic families under measures such as treewidth and neighbourhood diversity. They also prove hardness results for other measures, showing that efficient methods are unlikely there. Together, the findings nearly complete the map of which settings admit fast algorithms and which do not.

Catalog record

CREATORNicolas Bousquet, Amer E. Mouawad, Stephanie Maaz, Naomi Nishimura, Sebastian Siebertz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE149 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-17344

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers Nicolas Bousquet, Amer E. Mouawad, Stephanie Maaz, Naomi Nishimura, Sebastian Siebertz Abstract 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. This paper investigates meta-theorems for solution discovery for graph problems definable in monadic second-order logic ( MSO 1 and MSO 2 ) and first-order logic ( 𝖥𝖮 \mathsf{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 b . We present both positive and negative results. On the algorithmic side, we prove that MSO 2 - Discovery is in 𝖷𝖯 \mathsf{XP} when parameterized by treewidth and that MSO 1 - Discovery is fixed-parameter tractable when parameterized by neighborhood diversity. On the hardness side, we establish that FO - Discovery is 𝖶 \mathsf{W} [1]-hard when parameterized by modulator to stars, modulator to paths, as well as twin cover, numbers. Additionally, we prove that MSO 1 - Discovery is 𝖶 \mathsf{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 b is included in the parameter (in particular, parameterized by cliquewidth + b +b , where the cliquewidth of a graph is at most any of the studied parameters), and provide a near-complete (fixed-parameter tractability) meta-theorems investigation for solution discovery problems for MSO - and 𝖥𝖮 \mathsf{FO} -definable graph problems and structural parameters larger than cliquewidth. 1 Introduction Real-world systems rarely remain static. From automated warehouses adapting to shifting demand patterns [ 29 ] to quantum circuits reallocating qubits for optimal computation [ 50 , 62 , 63 ] , systems must continuously transform their configurations through sequences of local modifications. This dynamic nature of real systems motivates the study of transformation problems, where we seek to change one configuration into another through a sequence of permitted operations. Over the last few decades, considerable effort has focused on finding efficient transformations between solutions. For example, bounded transformation problems under the combinatorial reconfiguration framework [ 58 , 66 ] take as input two configurations (for example, solutions to a problem instance, such as independent sets of a graph) and determine whether the first can be transformed into the second via a bounded length sequence of small, local modifications, while maintaining feasibility at every intermediate step. For vertex subset problems, such as Independent Set , we can view a configuration as a set of tokens placed on the vertices of a solution. Each reconfiguration step corresponds to a simple change, such as adding, deleting, or moving a token. The solution space and the complexity of deciding the existence of a transformation depend on the allowed modification rules such as in the token jumping model where, at each step, exactly one token can be moved to any unoccupied vertex in the graph and in the token sliding model where, at each step, exactly one token moves along an edge of the graph to an unoccupied vertex. While the reconfiguration framework captures situations in which, starting with a solution, we need each transformation to result in another solution, many practical scenarios present a different challenge. For instance, urban bike-sharing systems require the distribution of bicycles every few hours to match demand patterns at different stations. When commuters leave many stations empty and others overflowing, the current distribution becomes invalid (that is, it fails to meet minimum inventory requirements). Rebalancing trucks must then transform this infeasible configuration into any valid one while minimizing travel distance to reduce operational costs. The key insight is that during redistribution, stations are allowed to have too few or too many bikes; what matters is reaching as efficiently as possible any final configuration where all minimum requirements are satisfied. Similarly, in many other applications, if a system becomes corrupted with an invalid configuration, maintaining feasibility during transformation is not required, as it may often be permissible or even preferable to shut down the system during the transformation. We then simply wish to obtain a valid solution with minimum transformation cost (that is, time or other resources), preferring efficient restoration over maintaining functionality throughout the transformation. Inspired by this observation, Fellows et al. [ 33 ] introduced solution discovery where instead of seeking a feasibility-preserving transformation between two known solutions, we begin with one known infeasible (corrupted) configuration and ask whether a solution can be reached via a short transformation sequence. Although similar ideas have been studied in various fields from graphs to geometry with discrete or continuous optimization [ 23 , 2 ] , solution discovery formalizes and further generalizes the approach. The goal of this paper is to investigate meta-theorems for a class of solution discovery problems on graphs. Although the application of solution discovery extends far beyond graphs, in this paper, we confine our focus to the following problem: (fix/given) a vertex subset property \Pi of graphs, given a graph G , an initial infeasible configuration S\subseteq V(G) , and an integer budget b , does there exist a final feasible configuration T\subseteq V(G) that satisfies \Pi on G such that there exists a transformation sequence of length at most b from S to T ? To further specify the transformation sequence, we represent S by placing a token on each vertex of S , and (mainly) consider transformation sequences where a transformation step consists of a token slide. Unlike problems in reconfiguration (where both endpoints of the reconfiguration sequence are part of the input and intermediate steps are solutions), solution discovery starts with an infeasible configuration, introduces existential quantification over the final configuration, and does not require intermediate configurations to be solutions. These subtle changes significantly alter the computational landscape. Many reconfiguration problems are \mathsf{PSPACE} -complete [ 46 , 67 ] ; moreover, the requirement that all configurations in the sequence be solutions can lead to exponential length transformations [ 15 , 12 ] . In sharp contrast, in solution discovery the number of steps needed to reach a final configuration, if one exists, is at most kn steps, where k is the number of tokens, or, in other words, the solution or configuration size, and n is the number of vertices of the instance graph. Hence, the transformation sequence can serve as a polynomial-size certificate, demonstrating that the problems lie in \mathsf{NP} . Not surprisingly, the solution discovery variants of common \mathsf{NP} -complete problems (where \Pi is defined through the classical problem and the final configurations must satisfy the standard problem definition) such as Vertex Cover, Independent Set , and Dominating Set , are \mathsf{NP} -complete [ 33 , 24 ] . More surprisingly, the solution discovery variants of polynomial-time solvable problems such as Vertex Cut, Matching , and Shortest Path are also \mathsf{NP} -complete [ 41 ] . A fine-grained parameterized classification of the above problems with respect to the parameters k (number of tokens), b (discovery budget), and structural parameters such as treewidth, pathwidth, and feedback vertex set number was established in several papers [ 24 , 33 , 41 , 42

Read the complete text