Parameterized Complexity of Elimination Distance to First-Order Logic Properties

被引:2
作者
Fomin, Fedor, V [1 ]
Golovach, Petr A. [1 ]
Thilikos, Dimitrios M. [2 ]
机构
[1] Univ Bergen, Dept Informat, PB 7803, N-5020 Bergen, Norway
[2] Univ Montpellier, CNRS, LIRMM, 161 Rue Ada, F-34095 Montpellier 5, France
关键词
First-order logic; elimination distance; parameterized complexity; descriptive complexity; 2ND-ORDER LOGIC;
D O I
10.1145/3517129
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula phi is an element of Sigma(3), that is, of the form phi = there exists x(1)there exists x(2) ... there exists x(r) for all y(1)for all y(2) ... for all y(s) there exists z(1)there exists z(2) ... there exists z(t) psi, where psi is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Sigma(3) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulaswith even slightly more expressive prefix structure: There are formulas phi epsilon Pi(3), for which computing elimination distance is W[2]-hard.
引用
收藏
页数:35
相关论文
共 32 条
[21]  
Guo J, 2004, LECT NOTES COMPUT SC, V3162, P162
[22]   Elimination Distances, Blocking Sets, and Kernels for Vertex Cover [J].
Hols, Eva-Maria C. ;
Kratsch, Stefan ;
Pieterse, Astrid .
37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
[23]   Vertex Deletion Parameterized by Elimination Distance and Even Less [J].
Jansen, Bart M. P. ;
de Kroon, Jari J. H. ;
Wlodarczyk, Michal .
STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, :1757-1769
[24]   THE NODE-DELETION PROBLEM FOR HEREDITARY PROPERTIES IS NP-COMPLETE [J].
LEWIS, JM ;
YANNAKAKIS, M .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 20 (02) :219-230
[25]  
Lindermayr A., 2020, LIPIcs, V170, P65, DOI [DOI 10.4230/LIPICS, 10.4230/LIPIcs.MFCS.]
[26]  
Lindermayr Alexander, 2020, LIPIcs, V170, DOI [10.4230/LIPIcs.MFCS.2020.65, DOI 10.4230/LIPICS.MFCS.2020.65]
[27]  
Lokshtanov D., 2018, Leibniz International Proceedings in Informatics (LIPIcs), V135, DOI [10.4230/LIPIcs.ICALP.2018.135, DOI 10.4230/LIPICS.ICALP.2018.135]
[28]  
Lokshtanov Daniel, 2018, ABS1802014532018 COR
[29]   Tree-depth, subgraph coloring and homomorphism bounds [J].
Nesetril, Jaroslav ;
Ossona de Mendez, Patrice .
EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (06) :1022-1041
[30]  
Smorynski C., 1977, Handbook of Mathematical Logic, VVolume 90, P821