{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiauyd3rgb7uouhvre5sq3cm4a5fismte7giqu2x7tnkhk5qyd6pb4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhtyzzziix52"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.22043v1",
  "publishedAt": "2026-03-24T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Florian Chudigiewitsch",
    "Marlene Gründel",
    "Christian Komusiewicz",
    "Nils Morawietz",
    "Till Tantau"
  ],
  "textContent": "**Authors:** Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz, Nils Morawietz, Till Tantau\n\nA 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).",
  "title": "The Descriptive Complexity of Relation Modification Problems"
}