Résumé
La distance d'élimination par rapport à une propriété de graphe cible P est un paramètre général de modification de graphe introduit par Bulian et Dawar. Nous commençons l'étude des distances d'élimination vers des propriétés de graphes exprimables en logique du premier ordre. Nous délimitons la traçabilité des paramètres fixes du problème en identifiant des conditions suffisantes et nécessaires sur la structure des préfixes des formules de la logique du premier ordre. Notre résultat principal est le méta-théorème suivant : Pour toute propriété de graphe P exprimable par une formule logique du premier ordre φ ∈ Σ3, c'est-à-dire de la forme φ = ∃x 1 ∃x 2 ⋯∃x r ∀y 1 ∀y 2 ⋯∀y s ∃z 1 ∃z 2 ⋯∃z t ψ, où ψ est une formule du premier ordre sans quantificateur, vérifiant si la distance d'élimination d'un graphe à P ne dépasse pas k, est tractable à paramètres fixes paramétrée par k. Les propriétés des graphes exprimables par des formules de Σ3 incluent le fait d'être de degré borné, d'exclure un sous-graphe interdit, ou de contenir un ensemble dominant borné. Nous complétons ce théorème en montrant qu'un tel énoncé général n'est pas valable pour les formules ayant une structure préfixe légèrement plus expressive : Il existe des formules φ ∈ Π3, pour lesquelles le calcul de la distance d'élimination est W[2]-hard.