On the Parameterized Complexity of Graph Modification to First-Order Logic Properties

2018/05/11 by Fomin, Fedor V., Golovach, Petr A., Thilikos, Dimitrios M. · 1 citation
#05C85 #68R10 #68W05 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.04375

Abstract

We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula ϕfor the problem to be fixed-parameter tractable or to admit a polynomial kernel.

Cited by

• On the Computational Power of Extensional ESO

Related

• Parameterized Complexity of Elimination Distance to First-Order Logic Properties
• The parameterized complexity of k-edge induced subgraphs
• Existential Second-Order Logic Over Graphs: Parameterized Complexity
• Logical complexity of graphs: a survey
• Fixed-parameter tractability, definability, and model checking