2026-08-21T18:34:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27475 2026-08-21T14:42:41Z ddc:004 open_access

The Descriptive Complexity of Relation Modification Problems Chudigiewitsch, Florian Gründel, Marlene Komusiewicz, Christian Morawietz, Nils Tantau, Till graph problems descriptive complexity edge modification parameterized complexity circuit complexity 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 para-AC^{0↑} or TC^0) or intractable (that is, they contain W[2]-hard or NP-hard problems). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Chudigiewitsch and Marlene Gründel and Christian Komusiewicz and Nils Morawietz and Till Tantau 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.93 urn:nbn:de:0030-drops-274752 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.93 eng https://creativecommons.org/licenses/by/4.0/legalcode