1 23
Theory of Computing Systems ISSN 1432-4350
Volume 64 Number 2
Theory Comput Syst (2020) 64:251-271 DOI 10.1007/s00224-019-09938-8
Graph Modification to First-Order Logic Properties
Fedor V. Fomin, Petr A. Golovach &
Dimitrios M. Thilikos
1 23
Springer Nature. This e-offprint is for personal use only and shall not be self-archived in electronic repositories. If you wish to self- archive your article, please use the accepted manuscript version for posting on your own website. You may further deposit the accepted manuscript version in any repository,
provided it is only made publicly available 12
months after official publication or later and
provided acknowledgement is given to the
original source of publication and a link is
inserted to the published article on Springer's
website. The link must be accompanied by
the following text: "The final publication is
available at link.springer.com”.
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
Fedor V. Fomin1·Petr A. Golovach1 ·Dimitrios M. Thilikos2
©
Abstract
We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formulaϕ, we consider the problem of deciding whether an input graph can be modified by removing/adding at mostkvertices/edges such that the resulting modification has the property expressible by ϕ. We provide sufficient and necessary conditions on the structure of the prefix ofϕ specifying when the corresponding graph modifica- tion problem is fixed-parameter tractable (parameterized byk) and when it admits a polynomial kernel.
Keywords First-order logic·Graph modification·Parameterized complexity· Descriptive complexity·Kernelization
1 Introduction
A variety of algorithmic graph problems, calledmodification problems, can be for- mulated as problems of modifying a graph such that the resulting graph satisfies some
The two first authors have been supported by the Research Council of Norway via the projects
“CLASSIS” and “MULTIVAL”. The third author has been supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). All authors have been supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.
Petr A. Golovach [email protected] Fedor V. Fomin [email protected] Dimitrios M. Thilikos [email protected]
1 Department of Informatics, University of Bergen, Bergen, Norway
2 AlGCo Project Team, CNRS, LIRMM, Universit´e de Montpellier, Montpellier, France Published online:24July2019
Springer Science+Business Media, LLC, part of Springer Nature 2019
fixed desired property. The study of graph modification problems is one of the most popular trends in graph algorithms, and in particular, in parameterized complexity.
One of the classic results about graph modification problems is the work of Lewis and Yannakakis [16], which provides necessary and sufficient conditions (assum- ing P=NP) of polynomial time solvability of vertex-removal problems for hereditary properties. For other types of graph modification problems, like edge-removal prob- lems [21], no such dichotomy is known. For the past 30 years graph modification problems served as a strong inspiration for developing new methods and techniques in parameterized/kernelization algorithms and complexity, see the books [6,7,9,17]
for an overview of the area.
In this paper we approach graph modification problems from the perspective of descriptive complexity. Descriptive complexity is the field of logic which studies the relations between computational complexity and expressibility in logic. The classic example of a theorem in descriptive complexity is the theorem of Fagin [8] asserting that a property of graphs is inNP if and only if it is definable by an existential second- order formula. We refer to the recent book of Grohe [12] for a modern overview of descriptive complexity. The significant amount of research in descriptive complexity is devoted to the study of prefix classes of certain logics. A prefix class is a syntactic fragment of first-order or second-order logic with formulas in prenex normal form and imposed constrains on the patterns of quantifiers in formulas. For example, the study of prefix classes of first-order logic is provided in the book of B¨orger, Gr¨adel, and Gurevich [4], see also the work of Gottlob, Kolatis and Schwentick [11] on characterizing the computationa l complexity of prefix classes of second-order logic.
Our results Let φ be an FOL formula on (undirected) graphs in prenex normal form. In particular, φ = Q1x1Q2x2· · ·Qtxtχ, where t is some constant, each Qi
∈{∀,∃}is a quantifier,xi is a variable, andχ is a quantifier-free part that depends on the variablesx1,. . . ,xt. We consider the following generic problems (we use “−” for the vertex/edge removal, “+” for the edge addition and “” for the symmetric difference).
For example, for φ= ∀u∀v¬(u∼v), Vertex-Removal toφis equivalent to Ver- tex Cover that is the graph modification problem asking whether one can remove at mostkvertices such that the resulting graph has no edges (we use u ∼ v for the adjacency predicate). More generally, any vertex-removal problem to a graph class characterized by a finite set of forbidden subgraphs, can be expressed as Vertex- Removal to φ for some φ with only ∀ quantifications over variables, where the number of variables is the maximum number of vertices of a forbidden graph. Clearly, using FOL, we are able to express other properties. For example, the property that the diameter of a graph is at most two cannot be expressed using forbidden subgraphs but can easily be written as the FOL formula ∀u∀v∃w[(u=v)∨(u∼v)∨((u ∼ w)∧(v ∼w))]. Similarly, the edge variants of modification problems toφcapture quite a few interesting and well-studied problems like Cluster Editing, where the task is to change at mostkadjacencies in the graph resulting in a disjoint union of cliques.
We consider modification problems, where the specification of a prefix class of formulaφis defined according to the arithmetic hierarchy (also known as Kleene- Mostowski hierarchy) used for classifications of the formulas in the first-order arithmetic language (see, e.g., [18]). We define prefix classes according to alterna- tions of quantifiers, that is, switchings from∀to∃or vice versa in the prefix string of the formula. We allow a formula to havefree, i.e., non-quantified, variables. Let0
=π0be the classes of FOL-formulas without quantifiers. For a positive integer, the classcontains formulas that could be written in the form
φ= ∃x1∃x2· · · ∃xsψ,
whereψis aπ−1-formula,sis some integer, andx1,. . . ,xsare free variables ofψ.
Respectively,πconsists of formulas
φ= ∀x1∀x2· · · ∀xsψ,
whereψis a−1-formula andx1,. . . ,xsare free variables ofψ. Note that we allow s= 0, which implies that for > , ∪π⊆ ∩π.
We establish a number of algorithmic results about modification problems where the target property is definable in FOL. We complement these results by lower bounds, which in combination provide neat dichotomy theorems about the param- eterized complexity of such problems. Hence we establish sufficient and necessary conditions on the prefix classes of FOL-formulas such that the corresponding graph modification problems are fixed-parameter tractable and/or admit a polynomial kernel.
Our first result shows the following dichotomy (subject to W[2]=FPT) for Vertex- Removal toφ, depending on the structure of the prefix class ofφ.
Theorem 1
(i) For everyφ∈3without free variables,Vertex-Removal toφisFPT.
(ii) There isφ∈π3withoutfree variables such thatVertex-Removal toφisW[2]- hard.
In other words, if the prefix of an FOL-formulaφhas at most two alternations of quantifiers and, in the case of exactly two alternations, if the first quantifier is∃, then Vertex-Removal toφisFPT. For each other type of quantifier alternations, there exists a formula for which the problem becomes W[2]-hard.
For kernelization complexity of Vertex-Removal toφ, we establish the following dichotomy.
Theorem 2
(i) For every φ ∈1 ∪π1 withoutfree variables, Vertex-Removal to φ admitsa polynomial kernel.
(ii) There isφ∈2(φ∈π2)without free variables such thatVertex-Removal toφ admitsno polynomial kernel unless NP ⊆coNP/poly.
For edge-modification problems we prove the following.
Theorem 3
(i) For everyφ∈2without free variables,Edge-Removal toφ,Edge-Completion toφ,andEdge-Editing toφareFPT.
(ii) There existsφ∈π2withoutfree variables such thatEdge-Removal toφ(respec- tively,Edge-Completion toφandEdge-Editing toφ)isW[2]-hard.
We observe that ifφ∈1, then all considered problems can be solved in polyno- mial time. Clearly, this means that they areFPT and have trivial polynomial kernels.
We complement this with lower bounds and summarize these results in the following theorem.
Theorem 4
(i) For everyφ∈1withoutfree variables,Edge-Removal toφ,Edge-Completion toφ,andEdge-Editing toφadmitpolynomial kernels.
(ii) There existsφ∈π1withoutfree variables such thatEdge-Removal toφ(respec- tively, Edge-Completion to φ and Edge-Editing to φ)admits no polynomial kernel unless NP ⊆coNP/poly.
This paper is organized as follows. In Section2, we introduce basic notions and state some auxiliary results. In Section3, we obtain the algorithmic upper bounds, that is, we show the claims (i) of Theorems 1–4. In Section4, we complement these results by the lower bounds given in the claims (ii) of Theorems 1–4. We conclude with Section5, where we discuss some possible extension of our results and mention some directions for further research.
2 Preliminaries
Sets We useNto denote the set of all non-negative numbers. Given somek∈N, we denote [k] = [1,k]. Given a setA, we denote by 2Athe set of all its subsets and we define
A 2
:= {e|e∈2A∧ |e| =2}. We denote bya=a1,. . . ,ara sequence of elements of a setAand callaanr-tupleof simply atuple. Note that the elements ofa not necessarily pairwise distinct. We denote byabtheconcatenationof tuplesaand b.
Graphs All graphs in this paper are undirected, loop-less, and without multiple edges unless explicitly stated otherwise. Given a graphG, we denote byV(G) its vertex set and byE(G) its edge set. For an edgee={x,y}∈E(G), we use instead the notation e=xy, that is equivalent toe=yx. We denote|G|=|V(G)|. Throughout the paper we usento denote|G|if it does not create confusion. For a vertexv,dG(v) denotes the degree ofv. For any set of vertices S ⊆V (G), we denote byG[S] the subgraph ofGinduced by the vertices fromS. We also defineG−S:=G[V(G)S]. Given an edge set F ⊆ E(G), we denoteG−F= (V(G),E(G)F). Also, given a set F ⊆
V (G 2
E(G), i.e., Fis a set of pairs of vertices that are not edges of G, we defineG+F= (V(G),E(G)∪F), and for F ⊆
V (G 2
, we defineGF= (V (G),E(G)−E(G)∩F+FE(G)).
Formulas In this paper we deal with logic formulas on graphs. In particular, we will deal with formulas of first-order logic (FOL). The syntax of FOL-formulas on graphs includes the logical connectives∨,∧,¬, variables for vertices, the quanti- fiers∀,∃that are applied to these variables, the predicate u ∼ v, whereuandv are vertex variables and the interpretation is thatuandvare adjacent, and the equal- ity of variables representing vertices. It also convenient to assume that we have the logical connectives→ and ⇐⇒. An FOL-formulaφ is inprenex normal formif it is written asφ=Q1x1Q2x2· · ·Qtxtχ where eachQi∈{∀,∃}is a quantifier,xiis a variable, andχ is a quantifier-free part that depends on the variablesx1,. . . ,xt. Then Q1x1Q2x2· · ·Qtxtis referred as theprefixofφ. From now on, when we mention the term “FOL-formula”, we mean an FOL-formula on graphs that is in prenex normal form. For an FOL-formulaφwithout free variables and a graphG, we writeG|=φto denote thatφevaluates totrueonG.
For technical reasons, we extend FOL-formulas on graphs to structures of a special type. We say that a pair (G,v), wherev=v1,. . . ,vris anr-tuple of vertices ofG, is an r-structure. Letφbe an FOL-formula without free variables and letx=x1,. . . ,xrbe anr-tuple of pairwise distinct variables ofφ. We denote byφ[x] the formula obtained fromφ by the deletion of the quantification over x1,. . . ,xr, that is, these variables become the free variables ofφ[x]. For anr-structure (G,v) withv=v1,. . . ,vrand φ[x], we write (G,v)|=φ[x] to denote thatφ[x] evaluates totrueonGifxiis assigned vi fori ∈[r]. Ifr= 0, that is,vandxare empty, then (G,v)|=φ[x] is equivalent to G|=φ.
Parameterized Complexity We refer to the books [6, 7, 9, 17] for the detailed introduction to the field. Here we only briefly review the basic notions.
Parameterized Complexity is a bivariate framework for studying the computational complexity of computational problems. One variable is the input sizenand the other is aparameter kassociated with the input. The main goal is to confine the combi- natorial explosion in the running time of an algorithm for anNP-hard problem to depend only onk. Thus, a parameterized problem is defined formally as a language L ⊆ ∗×N, where ∗is a set of strings over a finite alphabet. A parameter- ized problem is said to befixed parameter tractable(orFPT) if it can be solved in time f (k)·nO(1)for some computable functionf. Also, we say that a parameterized problem belongs in the class XPif it can be solved in timeO(nf(k)) for some com- putable functionf. The complexity classFPT consists of all fixed parameter tractable problems. Parameterized complexity theory also provides tools to disprove the exis- tence ofFPT algorithms under plausible complexity-theoretic assumptions. For this, Downey and Fellows introduced a hierarchy of parameterized complexity classes, namely FPT⊆W[1] ⊆W[2] ⊆W[3] ⊆ · · · ⊆XP and conjectured that it is proper.
This conjecture plays a central role in obtaining lower complexity bounds. The basic way to show that it is unlikely that a parameterized problem admit anFPT algorithm is to show that it is W[1] or W[2]-hard using aparameterized reductionfrom a known W[1] or W[2]-hard problem.
Akernelizationfor a parameterized problem is a polynomial time algorithm that maps each instance (I,k) of a parameterized problem with the inputIand parameter kto an instance (I, k)of the same problem such that
(i) (I,k) is ayes-instance if and only if (I, k)is ayes-instance, and (ii) |I| +kis bounded byf(k) for some computable functionf.
The output (I, k) is called a kernel. The functionf is said to be the size of the kernel. A kernel ispolynomialif f is polynomial. While it can be shown that every decidable parameterized problem isFPT if and only if it admits a kernel, it is unlikely that every problem inFPT has a polynomial kernel. In particular, the now standardcomposition andcross-composition techniques [2, 3] allow to show that certain problems have no polynomial kernels unless NP ⊆coNP/poly.
To solve all considered problems, we have to solve the Model Checking problem for first-order logic on graphs:
Model Checking is known to be PSPACE-complete [19]. The problem is also hard from the parameterized complexity viewpoint when parameterized by the size of the formula. It was proved by Frick and Grohe in [10] that the problem is AW[∗]- complete for this parametrization (see, e.g., the book [9] for the definition of the class). Thus, it is unlikely that Model Checking isFPT when parameterized by the formula size. This immediately implies that the problem Vertex-Removal toφ as
well as the problems Edge-Removal/Completion/Editing toφare AW[∗]-hard when parameterized by the size ofφeven fork= 0. However, Model Checking is inXP when parameterized by the number of variables. In particular, ifφhas rvariables and input size isn, then it can be solved in time O(nr)by exhaustive search. The currently best algorithm is given by Williams in [20] who proved the following.
Theorem 5 (20) Model Checking can be solved in time O˜(nω) for formulas with 3 variables and if the number of variablesr≥3, then it can be solved in time O˜(nr−3+ω)whereω is the matrix-multiplication exponent. Moreover, ifr ≥9, then Model Checkingcan be solved in timenr−1+o(1).
Here O˜(f (n))is used to denote an upper bound O(f (n)logcn)for some positive constantc. These algorithms are, in fact, asymptotically optimal up to theStrong Exponential Time Hypothesis(SETH) (see [6,14] for the definition). It was shown by Williams [20] that if Model Checking for formulas withr≥4 can be solved in time O(nr−1−ε)for someε >0, then SETH is false.
Because of these results, we assume throughout the paper that the FOL-formulas in the considered modification problems have aconstantnumber of variables and, therefore, constant sizes. In particular, the exponents of polynomials in running times and the sizes of kernels should depend on the length|φ|of the formulaφ.
We conclude this section by observing that Theorems 3 and 4 claim the same com- plexity status for EDGE-REMOVAL TOφand EDGE-COMPLETION TOφ. This is not surprising, because these problems are equivalent in the following sense. Denote by Gthecomplementof a graphG, that is, the graph with the same vertex set such that every two distinct vertices are adjacent in Gif and only if they are nonadjacent inG.
For an FOL-formulaφ, denote by φthe formula obtained fromφby replacing each adjacency predicate by the subformula expressing non-adjacency of distinct vertices, that is, u∼vis replaced by ¬(u=v)∧¬(u∼v). Then we can make the following straightforward observation.
Observation 1 For every FOL-formula φ, (G,k) is a y es-instance of EDGE- REMOVAL TOφif and only if (G, k)is a ayes-instance of EDGE-COMPLETION TO
φ.
By Observation 1, it is sufficient to show Theorems 3 and 4 for EDGE-REMOVAL TOφand EDGE-EDITING TOφ.
3 Upper Bounds
In this section we prove the claims (i) of Theorems 1–4. First, we consider VERTEX- REMOVAL TOφ.
Lemma 1 For everyφ∈3withoutfree variables,VERTEX-REMOVAL TOφcan be solved in time |φ|k·nO(|φ|).
Proof Consider an instance (G,k) of VERTEX-REMOVAL TOφfor φ= ∃x1· · · ∃xr∀y1· · · ∀ys∃z1· · · ∃ztχ ,
wherer,s,t≥0 andχ is quantifier-free. Letx=x1,. . . ,xr,y=y1,. . . ,ys, andz= z1,. . . ,zt.
Assume that (G,k) is ayes-instance of VERTEX-REMOVAL TOφ. This means that there is S ⊆ V (G)of size at mostksuch thatG−S|=φ. Observe thatG−S|=φ if and only if there is anr-tupleu=u1,. . . ,urof vertices ofG−Ssuch that (G− S,u)|=φ[x].
We use this observation, and for eachr-tupleuof vertices ofG, check whether there is S ⊆ V (G)of size at mostkthat has no common vertices withuand it holds that (G−S,u)|=φ[x]. If we find such a setS, we return this solution for the considered instance of VERTEX-REMOVAL TOφ. Otherwise, if we fail to findSfor allr-tuples u, we conclude that (G,k) is ano-instance. From now we assume thatuis given.
Suppose that (G,u)|=φ[x] does not hold. Then there is ans-tuplev=v1,. . . ,vsof vertices ofGsuch that (G,uv)|=φ[xy] does not hold. Our algorithm is based on the following crucial claim.
Claim 1.1 For every S⊆V (G)such that S is disjoint withuand (G−S,u)|=φ[x], S contains at least one vertex ofv.
The proof is by contradiction. Assume that (G−S,u)|=φ[x] butSandvare dis- joint. Then (G−S,uv)|=φ[xy]. By definition, this means that there is at-tuple of verticeswofG−Ssuch that (G−S,uvw)|=φ[xyz]. In other words,χ evaluates to trueif thex,yandz-variables are assigned tou,vandwrespectively. This immedi- ately implies that (G,uvw)|=φ[xyz] and, therefore, (G,uv)|=φ[xy]. This contradicts the assumption that (G,uv)φ[xy].
Claim 1.1 leads to the following recursive algorithm that find a solutionSfor the givenu(if such a solution exist). The algorithm receives as the input the current set Sthat is initially set to be empty and finds a solution S∗⊇Sas follows.
1. If (G−S,uv)|=φ[xy] for alls-tuplesv=v1,. . . ,vsof vertices ofG−S, then returnSand stop.
2. Otherwise, for ans-tuplev= v1,. . . ,vsof vertices of G−Ssuch that (G− S,uv)φ[xy], do the following:
(i) if|S|=kor all the vertices ofvare inu, then stop;
(ii) else, for eachvi∈vthat is not inu, call the algorithm for S=S∪ {vi}. The correctness of the algorithm follows from Claim 1.1. Concerning the running time of the algorithm. At each iteration we check at mostns s-tuplesvand for each vwe verify in time nO(|φ|)whether (G−S,uv)|=φ[xv]. Hence, each iteration takes time nO(|φ|). Also at each iteration we branch into at mostssubproblems and the depth of the search tree produced by the algorithm is at mostk. Thus the running time is sk·nO(|φ|). Recall that we call the algorithm for eachr-tupleu. Since there arenr such tuples, we have that the total running time is sk·nO(|φ|), which can be rewritten as |φ|k·nO(|φ|).
Lemma 1 immediately implies Theorem 1 (i).
We move to Edge-Removal toφand Edge-Editing toφ.
Lemma 2 For every φ ∈2 without free variables, EDGE-REMOVAL TO φ and EDGE-EDITING TOφcan be solved in time |φ|2k·nO(|φ|).
Proof The proof is similar to the proof of Lemma 1. We show the claim for EDGE- REMOVAL TOφand then explain how it should be modified for EDGE-EDITING TO
φ.
Let (G,k) be an instance of EDGE-REMOVAL TOφfor φ= ∃x1· · · ∃xr∀y1· · · ∀ysχ ,
whereχis quantifier-free. Letx=x1,. . . ,xrandy=y1,. . . ,ys.
We observe that F ⊆E(G)of size at mostkis a solution for an instance (G,k) of EDGE-REMOVAL TOφif and only if there is anr-tupleu=u1,. . . ,urof vertices ofGsuch that (G−F,u)|=φ[x]. Respectively, for eachr-tupleu of vertices ofG, we check whether there is F ⊆E(G)of size at mostksuch that (G−F,u)|=φ[x].
If we find suchF, we return this solution and we obtain that (G,k) is ano-instance otherwise. Assume thatuis given.
If the property (G,u)|=φ[x] is not fulfilled, then there is ans-tuplev=v1,. . . ,vs of vertices ofGsuch that it does not hold that (G,uv)|=φ[xy]. We use the following claim.
Claim 2.1 For every F ⊆E(G)such that (G−F,u)|=φ[x], F contains at least one edge with both end-vertices inuv.
To obtain a contradiction, assume that (G−F,u)|=φ[x] but every edge ofFhas at least one end-vertex outside the tuplesuandv. This means thatχevaluates totrueon G−Fif thexanyy-variables are assigned touandvrespectively. Notice that every two vertices ofuvare adjacent inG−Fif and only if they are adjacent inG. Hence, χevaluates totrueonGif thexanyy-variables are assigned touandvrespectively.
This means that (G,uv)|=φ[xy]; a contradiction.
We construct the following recursive branching algorithm that finds a solutionF for the givenuif it exists. The algorithm takes as the input the current setFthat is initially empty and finds a solution F∗⊇F:
1. If (G−F,uv)|=φ[xy] for alls-tuplesv=v1,. . . ,vsof vertices ofG, then return Fand stop.
2. Otherwise, for an s-tuple v = v1,. . . ,vs of vertices of G such that (G − F,uv)φ[xy], do the following:
(i) set L⊆E(G)be the set of edges with both end-vertices inuv, (ii) if|F|=korL=∅, then stop;
(iii) else, and for eache∈L, call the algorithm for F=F ∪ {e}.
The correctness of the algorithm follows from Claim 2.1. On each iteration we check at mostns s-tuples v, and for each v, verify in time nO(|φ|) whether (G−
F,uv)|=φ[xv]. Hence, each iteration can be done in time nO(|φ|). Also on each itera- tion we have at most |L| ≤r+s
2
branches and the depth of the search tree produced by the algorithm is at mostk. This implies that the running time is (r+s)2k·nO(|φ|). Recall that we call the algorithm for eachr-tupleu. Since there arenr such tuples, we have that the total running time is |φ|2k·nO(|φ|).
For EDGE-EDITING TOφ, the algorithm is essentially the same. The difference is that in addition to edge removal we allowed to add edges. Respectively, we replace G−FbyGFin the above algorithm and modify Steps 2 (i)—(iii):
(i) setLbe the set of pairs of distinct vertices ofuv, (ii) if|F|=korL=∅, then stop;
(iii) else, and for eache∈L, call the algorithm for F=F ∪ {e}.
Notice that the variant of Claim 2.1 , whereG−Fis replaces byGF, holds and this implies correctness. The time analysis is the same.
Lemma 2 together with Observation 1 implies Theorem 3(i). Our next aim is show kernelization upper bounds. First, we observe that for1-formulas, our problems can be solved in polynomial time.
Lemma 3 For everyφ∈1without free variables,VERTEX-REMOVAL TOφ,Edge- Removal toφ, andEdge-Editing toφcan be solved in time nO(|φ|).
Proof Assume that
φ= ∃x1· · · ∃xrχ whereχis quantifier-free.
For VERTEX-REMOVAL TOφ, it is sufficient to observe that (G,k) is ayes-instance of the problem if and only ifG|=φ. We can use Theorem 5 and solve the problem in time nO(|φ|).
For Edge-Removal toφand Edge-Editing toφ, we can observe that (G,k) is ay es-instance if and only if there is a set of verticesUof size s=min{r, n}such that (G[U],k) is ayes-instance. We can check all such setsUin time nO(|φ|), and for each set, we use brute force to verify whether (G[U],k) is ayes-instance. Since the brute force checking of all subsets of edges or pairs of vertices ofG[U] of size at most k =min{k,s
2
}can be done in time s2k, the total running time is s2s2·nO(|φ|). Becauses≤|φ|, we can write it as nO(|φ|).
Because every problem that can be solved in polynomial time has a trivial polyno- mial kernel, Lemma 3 together with Observation 1 implies Theorem 4(i). Clearly, the lemma also implies the claim of Theorem 2(i) for1-formulas. It remains to prove it forπ1-formulas. For this, we need the classic result of Lewis and Yannakakis [16]. A graph propertyPis said to behereditaryif for each graphGsatisfyingP, it hold that Pholds for every induced subgraph ofG. A propertyPisnontrivialif it is true for infinitely many graphs and it is false for infinitely many graphs. VERTEX-REMOVAL TOPasks, given a graphGand a positive integerk, whether it is possible to remove at mostkvertices ofGto obtain a graph satisfyingP. It was proved by Lewis and Yan- nakakis [16] that the following dichotomy holds for a hereditary propertyPthat can
be tested in polynomial time: VERTEX-REMOVAL TOPcan be solved in polynomial time ifPis trivial, and the problem isNP-complete otherwise.
Lemma 4 For everyφ∈π1without free variables,Vertex-Removal toφadmits a polynomial kernel.
Proof Let (G,k) be an instance of Vertex-Removal toφfor φ= ∀x1· · · ∀xrχ
whereχis quantifier-free. Letx=x1,. . . ,xr. Observe that the graph propertyG|=φ is hereditary forπ1-formulas. If this property is trivial, we can solve Vertex-Removal toφin polynomial time [16] and conclude that the problem admits a trivial polyno- mial kernel. Assume from now that the propertyG|=φis not trivial. By the result of Lewis and Yannakakis [16], Vertex-Removal toφisNP-complete.
For every tuplevof vertices ofG, denote byUvthe set of vertices contained inv.
Let
U = {Uv|vis anr-tuple of vertices ofGsuch that(G,v)φ[x]}.
The crucial observation is that S ⊆V (G)of size at mostkis a solution for (G,k) if and only ifSis ahitting setfor U, that is,S∩Uv=∅ for every Uv ∈ U. This observation is proved by the same arguments as Claim 1.1 assuming thatuis empty.
Thes-HITTINGSETproblem that asks, given a family of sets U of size at mosts over some universe and a non-negative integerk, whether there is a hitting setSfor Uin known to have a polynomial kernel of size at most (2s−1)ks−1+kby the result of Abu-Khzam [1]. Apparently HITTINGSETis inNP. Hence, there is a polynomial reduction from HITTINGSETto theNP-complete problem Vertex-Removal toφ. This implies that Vertex-Removal toφadmits a polynomial kernel.
4 Lower Bounds
Here we prove the hardness claims of Theorems 1–4. In Section4.1, we give the technical result about reducing EDGE-REMOVAL TOφto VERTEX-REMOVAL TOψ.
In Section4.2, we show W[2]-hardness and in Section4.3we obtain kernelization lower bounds.
4.1 Reducing Edge Removal to Vertex Removal
In this section we construct a generic reduction of EDGE-REMOVAL TO φ to VERTEX-REMOVAL TOψ that we use twice in the proofs of our complexity lower bounds.
We say that an FOL-formulaφ is ∀-containing if the prefix ofφ contains a ∀ quantifier.
Lemma 5 For every∀-containing FOL-formulaφ∈∪πwithout free variables for≥1, there is formulaψ∈+ 1∪π+ 1without free variables such that
(i) |ψ|= poly(|φ|),
(ii) ifφ∈(resp.φ∈π),thenψ∈+ 1(resp.ψ∈π+ 1),
(iii) there is a polynomial reduction of EDGE-REMOVAL TO φ toVERTEX- REMOVAL TO ψ thattransforms each instance(G,k)ofEDGE-REMOVAL TO
φ toan equivalent instance (G, k) ofVERTEX-REMOVAL TO ψ,i.e., the parameterkremains the same.
Proof Let (G,k) be an instance of EDGE-REMOVAL TOφ. We construct the instance (G, k)of VERTEX-REMOVAL TOψfrom (G,k) and then we constructψ. The main idea is to replace edge removals by vertex removals switching to the incidence graph ofGor, equivalently, by subdividing edges ofG. Then we have to “label” the vertices of the original graph that should not be removed. We do it by making them adjacent to sufficiently many pendant vertices. Formally, we construct Gas follows.
• Construct a copy ofGand subdivide each edge, that is, for eache=xy∈E(G), delete e, construct a new vertexveand make it adjacent to x and y. We say that the vertices ofGare branching vertices and the vertices obtained by the edge subdivisions are called subdivision vertices.
• For each branching vertex u, introducek+ 3 new verticesv1,. . . ,vk+ 3and make them adjacent to u; we call these vertices pendant.
Notice that every subdivision vertex has degree 2 and every branching vertex has degree at least 3. Moreover, if H is obtained from G by the removal of at most k vertices, then still every remaining branching vertex has degree at least 3. Observe also that H has isolated vertices if and only if at least one branching vertex ofGis removed in the construction of H.
Our next aim is to constructψ fromφto ensure that (G,k) is a yes-instance of EDGE-REMOVAL TOφif and only if (G, k)is ayes-instance of VERTEX-REMOVAL TOψ. Let
φ=Q1x1. . . Qpxpχ
whereQ1,. . . ,Qpare quantifiers,x1,. . . ,xpare variables andχis quantifier-free. We also assume thatχis written in conjunctive normal form.
The construction ofψ is done in several steps. First, we take care of adjacencies inφ. Recall that two verticesuandvare adjacent in Gif and only if they have a common neighbor in G. Respectively, we modify the adjacency predicates inχ.
Letπ={π1,. . . ,πs}be the family (multiset) of all predicates of the form xi∼xj
that occur inχwithout negations. If the same predicate xi∼xjoccurs several times, then for each occurrence, we include it inπ. Similarly, let π= {π1, . . . , πt}be the family (multiset) of all predicates of the form ¬(xi ∼xj)that occur inχ. Then we do the following.
• Constructsnew variablesy1,. . . ,ysandtnew variablesz1,. . . ,zt.
• For eachh∈{1,. . . ,s}, consider πh=xi∼xjfor somei,j∈{1,. . . ,p}and replace it by ¬(xi =xj)∧(xi∼yh)∧(yh∼xj).
• For eachh∈{1,. . . ,t}, consider πh = ¬(xi ∼ xj)for somei,j∈{1,. . . ,p}and replace it by (xi=xj)∨ ¬(xi∼zh)∨ ¬(zh ∼xj).
• Denote the formula obtained fromχby χ. Then
– ifQp=∃, set σ = ∃y1. . .∃ys∀z1. . .∀zt χ, and – ifQp=∀, set σ = ∀z1. . .∀zt∃y1. . .∃ys χ.
Consider the formulaα=Q1x1. . .Qpxpσ. Observe that we added new quantified variables in the end of the prefix of φ in such a way that we obtain at most one additional alternation of quantifiers. That is, we obtain thatα∈+ 1ifφ∈ and α∈π+ 1 if φ ∈π. The crucial property of the above construction is given in the following straightforward claim.
Claim 5.1 G|=φif and only if G|=βwhere
β=Q1x1. . . Qpxp σwith the domains of the variablesx1, . . . , xprestricted toV (G).
Moreover, for every set of pendant verticesXof size at mostk,G|=φif and only if (G−X)|=β.
Notice that in the formula of Claim 5.1 we insist to restrict the domains of the variablesx1,. . . ,xpinβ toV(G), that is,β is not an FOL-formula (andβ=α). Our next aim is to express these additional constraints in the first-order logic. We do it using the property that the branching vertices of Ghave degrees at least 3 and all the other vertices have degrees at most 2.
We consecutively construct the formulasρn+ 1,. . . ,ρ1. First, we setρn+ 1=σ. Note that x1,. . . ,xp are free variable for ρn+ 1. Assume inductively that 1 ≤ i ≤ p and ρi+ 1with free variablesx1,. . . ,xi is already constructed. Denote byPi+ 1the prefix andμi+ 1 the quantifier-free part ofρi+ 1respectively, that is,ρi+ 1= Pi+ 1μi+ 1. The construction ofρidepends on the quantifierQi.
• Introduce 3 new variables ri1, ri2, ri3.
• IfQi=∃, then set
ρi= ∃xi∃ri1∃ri2∃ri3Pi+1[ (¬(ri1=ri2)∧ ¬(ri1=ri3)∧ ¬(ri2=ri3))∧ ((xi∼ri1)∧(xi∼ri2)∧(xi∼ri3))∧μi+1].
• IfQi=∀, then set
ρi= ∀xi∀ri1∀ri2∀ri3Pi+1[ ((¬(ri1=ri2)∧ ¬(ri1=ri3)∧ ¬(ri2=ri3))∧ ((xi∼ri1)∧(xi∼ri2)∧(xi∼ri3))→μi+1
].
Letγ =ρ1. Note that in our construction ofγ, we do not create new alternations of quantifications, that is,γ ∈+ 1or inπ+ 1depending on whetherα∈+ 1or in π+ 1. The construction ofγ implies the next claim.
Claim 5.2 G|=φif and only if G|=γ. Moreover, for every set of pendant vertices X of size at most k,G|=φif and only if (G−X)|=γ.
Recall that the removal of the edges inGcorresponds to the removal of subdivision vertices of G. Respectively, our next aim is to ensure that the removal of a branching vertex of Gleads to the graph for which our formula is false. We use the property
that for every setSof at mostkvertices of G, G−Shas an isolated vertex if and only ifScontains a branching vertex. We use the property that the condition that a graph has no an isolated can be expressed by the formula ∀s1∃s2 (s1 ∼ s2)and modifyγ as follows. LetPbe the prefix ofγ and letμbe the quantifier-free part.
We writePas the concatenation of 3 partsP1,P2andP3whereP1and/orP3may be empty. Recall that the prefix of the original formulaφ contains∀xi for somei
∈{1,. . . ,p}by the condition of the lemma. Hence, the same holds forγ. LetP1be the first part ofPuntil the first occurrence of the quantifier∀. ThenP2is the next part until the first occurrence of the quantifier∃or until the end ofPif such a quantifier does not exist. Respectively,P3is the remaining part. We define
ψ=P1∀s1P2∃s2P3 [(s1∼s2)∧μ]
using two new variabless1ands2.
Notice that the insertion of the new quantifications is done in such a way that we do not introduce new alternations of quantifiers unlessP3is empty. But ifP3is empty, thenφ∈π1 orφ∈2and the new alternations were not introduced in the construction ofαfromφ. We have that eitherφ,γ ∈ andψ ∈+ 1orφ,γ ∈π
andψ∈π+ 1.
We show the following claim.
Claim 5.3 The instance (G,k) is ayes-instance of EDGE-REMOVAL TO φ if and only if (G, k)is ayes-instance of VERTEX-REMOVAL TOψ.
To show the claim, assume first that (G,k) is ayes-instance of EDGE-REMOVAL TOφ. Then there is F ⊆E(G)of size at mostksuch that (G−F)|=φ. We define S⊆V (G)be the the set of the subdivision vertices ofGcorresponding to the edges ofF, that is,S={ve|e∈F}. Clearly,|S|≤k. Notice that our reduction algorithm for graphs produces G−SfromG−F. Hence, by Claim 5.2, (G−F )|=γ. Because G−Shas no isolated vertices, we have that (G−S)|=ψ. It means that (G, k) is ayes-instance of VERTEX-REMOVAL TOψ.
Suppose now that (G, k)is ayes-instance of VERTEX-REMOVAL TOψ. Then there is S ⊆ V (G)of size at most ksuch that (G −S) |= ψ. Since ψ = P1∀s1P2∃s2P3 [(s1∼s2)∧μ], we have that G−Shas no isolated vertices, that is, Scontains only subdivision vertices ofGor pendants vertices. Also this immediately implies that (G−S)|=γ. Let Sbe the set of subdivision vertices ofSand letXbe the set of pendant vertices inS. We defineFto be the set of edges ofGcorresponding to the subdivision vertices in S, that is, F = {e ∈ E(G) | ve ∈ S}. We have that|F|≤k. Let alsoX be the set of pendant vertices inS. Observe again that our reduction algorithm for graphs produces G−SfromG−F. Then by Claim 5.2, we have that (G−F)|=φ. We conclude that (G,k) is ayes-instance of EDGE-REMOVAL TOφ.
To complete the proof of the lemma, observe that the size ofψ is polynomial in the size ofφ by our construction of the formula and this shows (i). To show (ii), observe thatψ∈+ 1 ifφ∈ andψ∈π+ 1 ifφ∈π. The last claim (iii) of the lemma immediately follows from Claim 5.3.
4.2 W[2]-hardness
In this subsection we show that there are formulasφinπ2andπ3for which EDGE- REMOVAL(EDITING)TOφand VERTEX-REMOVAL TOψ, respectively, are W[2]- hard when parameterized byk. First, we show the claim for EDGE-REMOVAL TOφ and EDGE-EDITING TOφ.
Lemma 6 There is an FOL-formulaφ∈π2without free variables with 5 variables such thatEDGE-REMOVAL TOφandEDGE-EDITING TOφareW[2]-hard.
Proof We define the formulaφas follows:
φ= ∀x∃y1∃y2∃y3∃y4[ (x∼y1)∧(x∼y2)∧(x∼y3)∧(x∼y4)∧(y1∼y2)∧(y1∼y3)∧ (y2∼y3)∧(y2∼y4)∧(y3∼y4)∧ ¬(y1=y4)∧ ¬(y1∼y4)].
In terms of graphs, G|=φ means that for every vertex x ofG, there are vertices y1,y2,y3,y4 such that these vertices together with xinduce the graph W shown in Fig.1. We say thatWis aφ-witness subgraph rooted in x.
We show hardness for EDGE-EDITING TO φ by reducing the SET COVER
problem:
It is well-known that SETCOVERis W[2]-hard when parameterized by k [7].
Let (U,S, k)be an instance SETCOVER, S= {S1, . . . , Sm}andU={u1,. . . ,un}. We construct the graphGas follows.
• For eachi∈{1,. . . ,m}, construct the graphHiwith 4root vertices si1, si2, s3i, si4 as it is shown in Fig.2a.
• For eachj∈{1,. . . ,n}, construct 2k+ 1 vertices u0j, . . . , u2kj and make them adja- cent to the root vertices of all the gadgetsHr such that the elementuj of the universeUis in the set Sr ∈S.
We claim that (U,S, k)is ayes-instance SETCOVERif and only if (G,k) is ay es-instance of EDGE-EDITING TOφ.
Fig. 1 Theφ-witness graphW
Fig. 2 Construction ofHiand the witness subgraphs for the vertices ofHi. The witness subgraphs are shown by thick lines and the other edges are shown by dashed lines
Suppose that (U,S, k)is ayes-instance SETCOVER. Let S∗ ⊆S be a family of size at mostkthat coversU. We construct the set of edgesFofGas follows. For every Si∈S∗, we include the edge s1isi4of the gadgetHiinF. Clearly,|F|≤k. Let G=GF =G−F. We show that G|=φ. Recall that we have to show that for every x ∈ V (G), there arey1,y2,y3,y4, such thatG[{x,y1,y2,y3,y3}] is aφ-witness subgraph rooted inx. For x∈m
i=1V (Hi), such subgraphs are shown in Fig.2b. Let x=uhj forj∈{1,. . . ,n}andh∈{0,. . . ,2k}. The elementuj∈Uis covered by some set Si∈S∗. Since si1si4∈F, we have that G[uhj, si1, s2i, si3, si4]is aφ-witness subgraph rooted inx. We conclude that G |= φand, therefore, (G,k) is ayes-instance of EDGE-EDITING TOφ.
Assume that (G,k) is ayes-instance of EDGE-EDITING TOφ. Then there is F ⊆ V (G)
2
with|F|≤ksuch that for G =GF, it holds that G |=φ. Consider the auxiliary graphQ= (V(G),F). Fori∈{1,. . . ,m}, let δi=
v∈V (Hi)dQ(v). We define S∗ = {Si | 1≤ i ≤ m, δi ≥ 2}. Because|F|≤k, n
i=1δi ≤2kand, therefore,
|S∗| ≤k. We claim that S∗coversU. To obtain a contradiction, assume that there isj∈{1,. . . ,n}such thatujis not covered by S∗. Since|F|≤k, there ish∈{0,. . . ,2k} such that the vertex uhj is not incident to the pairs ofF. Because G|=φ, there is a φ-witness subgraph rooted in x=uhj. Hence, there arey1,y2,y3,y4∈V(G) such that G[{x,y1,y2,y3,y4}] is aφ-witness subgraph. Notice that y1, y2, y3, y4∈ ∪mi=1V (Hi).
Observe that if ys ∈ V (Hi), then F ∩
V (Hi) 2
= ∅, because δi ≤1. Hence, it