The Descriptive Complexity of Relation Modification Problems
This work addresses foundational complexity theory problems for researchers in computational logic and parameterized complexity, providing a complete classification based on descriptive complexity.
The paper tackles the problem of classifying the complexity of relation modification problems, where a logical structure must be modified to satisfy a property, and finds that these problems exhibit a strong dichotomy, being either very easy (e.g., in paraAC^{0↑} or TC^0) or intractable (e.g., W[2]-hard or NP-hard).
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined property. We provide a complete classification of the classical and parameterized complexity of relation modification problems - the latter w. r. t. the modification budget k - based on the descriptive complexity of the respective target property. We consider different types of logical structures on which modifications are performed: Whereas monadic structures and undirected graphs without self-loops each yield their own complexity landscapes, we find that modifying undirected graphs with self-loops, directed graphs, or arbitrary logical structures is equally hard w. r. t. quantifier patterns. Moreover, we observe that all classes of problems considered in this paper are subject to a strong dichotomy in the sense that they are either very easy to solve (that is, they lie in paraAC^{0\uparrow} or TC^0) or intractable (that is, they contain W[2]-hard or NP-hard problems).