1 23
Algorithmica ISSN 0178-4617 Volume 71 Number 1
Algorithmica (2015) 71:1-20 DOI 10.1007/s00453-013-9776-1
Kernelization and Approximation
Fedor V. Fomin, Geevarghese Philip &
Yngve Villanger
1 23
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”.
Minimum Fill-in of Sparse Graphs:
Kernelization and Approximation
Fedor V. Fomin·Geevarghese Philip· Yngve Villanger
Received: 23 May 2012 / Accepted: 30 March 2013 / Published online: 11 April 2013
© Springer Science+Business Media New York 2013
Abstract The MINIMUMFILL-INproblem is to decide if a graph can be triangulated by adding at mostkedges. The problem has important applications in numerical alge- bra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on pla- nar graphs, and kernels of sizeO(k3/2)in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratiosO(logk)on planar graphs and O(√
klogk) onH-minor-free graphs. These results significantly improve the pre- viously known kernelization and approximation results for MINIMUM FILL-IN on sparse graphs.
Keywords Parameterized complexity·Kernelization·Minimum fill-in· Planar graphs·Linear kernel·d-Degenerate graphs
The research of Fedor V. Fomin was supported by the European Research Council (ERC) grant
“Rigorous Theory of Preprocessing”, reference 267959.
The research of Yngve Villanger was supported by the Research Council of Norway. The research of Geevarghese Philip was done while he was with The Institute of Mathematical Sciences, Chennai, India.
A preliminary version of this paper appeared in the proceedings of FSTTCS 2011 [14].
F.V. Fomin·Y. Villanger
Department of Informatics, University of Bergen, 5020 Bergen, Norway F.V. Fomin
e-mail:[email protected] Y. Villanger
e-mail:[email protected]
G. Philip (
)Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany e-mail:[email protected]
1 Introduction
A graph is chordal (or triangulated) if every cycle of length at least four has a chord, i.e. an edge between nonadjacent vertices of the cycle. In the MINIMUM FILL-IN
problem (also known as MINIMUMTRIANGULATIONand CHORDALGRAPHCOM-
PLETION) the task is to check if at mostkedges can be added to a graph such that the resulting graph is chordal. That is
MINIMUMFILL-IN
Input: A graphG=(V , E)and a non-negative integerk.
Question: Is thereF⊆ [V]2,|F| ≤k, such that graphH=(V , E∪F )is chordal?
This is a classical computational problem motivated by, and named after, a fun- damental issue arising in sparse matrix computations. During Gaussian eliminations of large sparse matrices, new non-zero elements—called fill—can replace original zeros, thus increasing storage requirements, the time needed for the elimination, and the time needed to solve the system after the elimination. The problem of finding the right elimination ordering minimizing the amount of fill elements can be expressed as the MINIMUMFILL-INproblem on graphs [27]. Besides sparse matrix computations, applications of MINIMUM FILL-INcan be found in database management, artificial intelligence, and the theory of Bayesian statistics. The survey of Heggernes [19] gives an overview of techniques and applications of minimum and minimal triangulations.
Unfortunately, the problem is notoriously difficult to analyze from the algorithmic perspective. MINIMUMFILL-IN(under the name CHORDALGRAPHCOMPLETION) was one of the 12 open problems presented at the end of the first edition of Garey and Johnson’s book [15] and it was proved to be NP-complete by Yannakakis [31].
Due to its importance the problem has been studied intensively, and many heuristics, without performance guarantees, have been developed [24,27].
Very few approximation and FPT algorithms for MINIMUMFILL-INare known.
Chung and Mumford [8] proved that every planar, and more generally, H-minor- free,n-vertex graph has a fill-in withO(nlogn)edges, thus yielding anO(nlogn)- approximation on these classes of graphs. Agrawal et al. [1] gave an algorithm with the approximation ratio O(m1.25log3.5n/ k+√
mlog3.5n/ k0.25), where m is the number of edges andnthe number of vertices in the input graph. For graphs of degree at mostd, they obtained a better approximation factorO(((nd+k)√
dlog4n)/ k).
Natanzon et al. [22] provided another type of approximation algorithms for MINI-
MUM FILL-IN. For an input graph with a minimum fill-in of sizek, their algorithm produces a fill-in of size at most 8k2 , i.e., within a factor of 8k of optimal. For graphs with maximum degreed, they gave another approximation algorithm achiev- ing the ratioO(d2.5log4(kd)). Kaplan et al. proved that MINIMUMFILL-INis fixed parameter tractable (FPT) for the parameterk by giving an algorithm which runs inO(k616k+k2mn)time [20]. Following this, faster FPT algorithms were devised for the problem, with running times that have smaller constants in the base of the exponent [6,7]. Very recently, the first and third authors of this paper developed a subexponential FPT algorithm for the problem which runs inO(2O(√klogk)+k2nm) time [13].
In this paper we study kernelization algorithms for MINIMUMFILL-INon differ- ent classes of sparse graphs. Kernelization can be regarded as systematic mathemat- ical investigation of preprocessing heuristics within the framework of parameterized complexity. In parameterized complexity each problem instance comes with a param- eterkand the parameterized problem is said to admit a polynomial kernel if there is a polynomial time algorithm (the degree of the polynomial is independent ofk), called a kernelization algorithm, that reduces the input instance down to an instance with size bounded by a polynomialp(k)ink, while preserving the answer. This reduced instance is called ap(k) kernel for the problem. Ifp(k)=O(k), then we call it a linear kernel. For example, for the instance(G, k)of PLANARMINIMUMFILL-IN, whereGis a planar graph andkis the parameter, the pair(G, k)is a linear kernel if Gis planar, the size ofG, i.e., the number of edges and vertices, isO(k), and there is a fill-in ofGwith at mostkfill edges if and only if there is a fill-in ofGwith at mostkfill edges. Kernelization has been extensively studied, resulting in polynomial kernels for a variety of problems. In particular, it has been shown that many problems have polynomial and linear kernels on planar and other classes of sparse graphs [2, 5,26].
There are several known polynomial kernels for the MINIMUM FILL-IN prob- lem [20] on general (not sparse) graphs. The best known kernelization algorithm is due to Natanzon et al. [22], which for a given instance (G, k) outputs in time O(k2nm)an instance(G, k)such thatk≤k,|V (G)| ≤2k2+4k, and(G, k)is a YES instance if and only if(G, k)is. Note that not every kernelization algorithm for fill-in in general graphs produces a sparse kernel, even if the input is a sparse graph. For example, the algorithm of Natanzon et al. [22], while reducing the number of vertices in the input graphG, introduces new edges. Thus the resulting kernelG can be very dense. In order to obtain kernels on classes of sparse graphs, we have to design new kernelization algorithms which preserve the sparsity of the kernel.
Our Results We provide kernelization algorithms for three important and increas- ingly general classes of graphs. For planar graphs, we obtain anO(k)kernel, and for graphs excluding a fixed graph as a minor and graphs of bounded degeneracy, kernels of sizeO(k3/2). Our reduction rules are easy to implement. Small kernels for sparse graphs can be used as an argument explaining the successful behavior of several heuristics for sparse matrix computations. As a byproduct of our results, we obtain an approximation algorithm that, for an input planar graph with minimum fill-in of sizek, produces a fill-in of sizeO(klogk), which is within factorO(logk)of opti- mal. ForH-minor-free graphs our kernelization yields an approximation algorithm with the ratioO(√
klogk).
It is natural to ask why such kernelization algorithms, which preserve the graph class, might be worth the trouble involved in developing them. We offer three rea- sons to justify this effort. Our first reason is purely theoretical. Observe that one can think of a kernelization algorithm as a polynomial-time encoding of an arbitrarily- sized input instance to a “small” instance, where the encoding preserves theYES/NO answer. Given a graph problem and, say, a planar instance of the problem, it is not a priori clear why there must exist a polynomial-time algorithm which can encode the answer for this instance as a small planar graph. It is eminently possible that for cer- tain problems, reducing the total size—in terms of, say, the number of bits required
to represent the reduced instance—while preserving the answer necessarily entails creating so many edges that the resulting graph is, in general, non-planar. Our results show that such is not the case for the MINIMUMFILL-INproblem, for the three graph classes mentioned above.
A second justification for preserving planarity (or the other two properties) is somewhat more practical. It is well-known that a number of graph problems be- come significantly easier to solve on planar graphs and their sparse generalizations, as compared to the same problems on general graphs. Thus, many NP-hard graph prob- lems become polynomial-time solvable in these classes, while others become eas- ier to approximate. More pertinently, a host of graph problems have subexponential FPT algorithms—which run in timeO(co(k)nO(1))for some constantc—on planar, H-minor free, and bounded-degeneracy graphs, while the best known algorithms for these problems on general graphs take timeO(cO(k)nO(1))or worse. Reducing to a planar kernel (or a kernel of the other two kinds), even at the expense of some in- crease in the instance size, could thus be justified, since it may allow us to apply significantly faster algorithms to solve the reduced instance.
As a third justification, we present the approximation algorithms which we obtain using our kernels—see Sect.6. These algorithms depend critically on the fact that the kernels belong to the respective graph classes—it is not sufficient that the kernel sizes are small.
2 Preliminaries
All graphs in this paper are finite and undirected. In general we follow the graph terminology of Diestel [9]. For a vertexvin graphG,NG(v)is the set of neighbours ofv, and for two non-adjacent verticesu, v,NG(u, v)≡NG(u)∩NG(v). We drop the subscriptGwhere there is no scope for confusion. ForS⊆V (G), we useN (S) for the set of neighbours inV (G)\Sof the vertices inS, andN[S] ≡N (S)∪S. We also useG[S]to denote the subgraph ofGinduced by S, andG\S to denote the subgraphG[V \S].
The operation of contracting an edge{u, v}of a graph consists of replacing its endpointsu, vwith a single vertex which is adjacent to all the former neighbours of uandvinG. A graphHis said to be a contraction of a graphGifHcan be obtained fromGby contracting zero or more edges ofG. GraphH is a minor ofGifH is a contraction of some subgraph ofG. A familyFof graphs is said to beH-minor free if no graph inFhasHas a minor. Ford∈N, a graphGis said to bed-degenerate if every subgraph ofGhas a vertex of degree at mostd. A familyF of graphs is said to be of bounded degeneracy if there is some fixedd∈Nsuch that every graph in the family isd-degenerate. Note that all graph properties discussed in this paper (being chordal, planar,H-minor free, andd-degenerate) are hereditary, i.e., are closed under taking induced subgraphs.
Minimal Separators Letu, vbe two vertices in a graphG. A setSof vertices ofG is said to be au, v-separator ofGifuandvare in different components in the graph G\S. The setSis said to be a minimalu, v-separator if no proper subset ofS is a
u, v-separator ofG. A setSof vertices ofGis said to be a (minimal) separator ofG if there exist two verticesu, vinGsuch thatSis a (minimal)u, v-separator ofG.
LetSbe a separator of a graphG. A connected componentCofG\Sis said to be associated withS, and is said to be a full component ifN (C)=S.
The following proposition is an exercise in Golumbic’s book on perfect graphs [16].
Proposition 1 A setS of vertices of a graphGis a minimalu, v-separator if and only ifuandvare in different full components ofG\S.
A setS of vertices of a graphG is said to be a clique separator ofGifS is a separator ofG, andG[S]is a clique.
Minimal and Minimum Fill-in Chordal or triangulated graphs are graphs contain- ing no induced cycles of length more than three. In other words, every cycle of length at least four in a chordal graph contains a chord. LetF be a set of edges which, when added to a graphG, makes the resulting graph chordal. ThenF is called a fill-in ofG, and the edges inF are called fill edges. A fill-inF ofGis said to be minimal if no proper subset ofF is a fill-in ofG, andF is a minimum fill-in if no fill-in ofGcon- tains fewer edges. Notice that every minimum fill-in is also minimal, and so to find a minimum fill-in it is sufficient to search the set of minimal fill-ins.
The following proposition relates minimal separators of a certain kind with mini- mum fill-ins of the graph.
Proposition 2 [6] LetGbe a graph, and let S be a minimal separator ofG such thatG[S]is a complete graph minus one edge, and there is a vertexv inV (G)\S which is adjacent to every vertex inS. Then there exists a minimum fill-in ofGwhich contains the single missing edge inG[S]as a fill edge.
The following proposition is folklore; for a proof see, e.g., Bodlaender et al.’s recent article on faster FPT algorithms for the MINIMUMFILL-INproblem [6].
Proposition 3 Letv1, v2, v3, v4, . . . , vtbe a chordless cycle in a graphG, and let Fbe a minimal fill-in ofG. If{v1, v3}∈/F, then{v2, v} ∈F for somev∈ {v4, . . . , vt}.
The following proposition relates minimal fill-ins of a graph with minimal fill-ins of the components of the graph obtained by deleting a minimal separator.
Proposition 4 [21] LetSbe a minimal separator ofG, letGbe the graph obtained by completingSinto a clique, and letES=E(G)\E(G). LetC1, C2, . . . , Cr be the connected components ofG\S. ThenES∪F is a minimal fill-in ofGif and only if F=r
i=1Fi, whereFi is the set of fill edges in a minimal fill-in ofG[N[Ci]].
IfS is a minimal clique separator ofGandF is any minimal fill-in ofG, then the above proposition implies that no edge ofF has its end points in two distinct components ofG\S. Since every clique separatorSofGcontains a minimal clique separatorS, and since all the vertices ofS\S belong to the same component of G S, we have
Corollary 1 LetSbe a clique separator ofG, and letF be a minimal fill-in ofG.
Then no edge inF has its end vertices in two distinct components ofG\S.
Parameterized Complexity Parameterized algorithms [11,12,23] constitute one ap- proach towards solving NP-hard problems in “feasible” time. A parameterized prob- lemΠis a subset ofΓ∗×Nfor some finite alphabetΓ. An instance of a parameter- ized problem is of the form(x, k), wherekis called the parameter. A central notion in parameterized complexity is fixed parameter tractability (FPT) which means, for a given instance(x, k), solvability in timef (k)·p(|x|)wheref is an arbitrary function ofk, andpis a polynomial in the input size whose degree is independent ofk.
Kernelization A kernelization algorithm for a parameterized problemΠ⊆Γ∗×N takes a pair(x, k)∈Γ∗×Nas input, and runs in time polynomial in|x|+k. It outputs a pair(x, k)∈Γ∗×N, called the kernel, such that(x, k)∈Πif and only if(x, k)∈ Π. Further, there exist computable functionsf, gsuch that max{k,|x|} ≤g(k)and k≤f (k). The functiongis referred to as the size of the kernel. Ifg(k)=O(k), then we say thatΠadmits a linear kernel.
The kernels in this paper are obtained by applying a sequence of polynomial time reduction rules. We use the following notational convention: for each reduction rule, (G, k) denotes the instance on which the rule is applied, and(G, k)denotes the resulting instance. We say that a rule is safe if(G, k)is aYESinstance if and only if(G, k)is aYESinstance. We show that each rule is safe. We also show—in most cases—that the resulting graph is in the same class asG.
The remaining part of the paper is organized as follows. Sections3,4, and5give kernelization algorithms for planar,d-degenerate, andH-minor free graphs, respec- tively. All the three kernels use Rule2of Sect.3, and Rule6 of Sect.4 is used in Sect.5as well. The kernels obtained are then used in Sect.6to get approximation algorithms for planar andH-minor free graphs. Section7shows that the problem re- mains NP-complete on 2-degenerated bipartite graphs. We conclude and state some open problems in Sect.8.
3 A Linear Kernel for Planar Graphs
In this section we show that the planar minimum fill-in problem has a linear kernel.
The kernel is obtained by applying four reduction rules. Rules1,2, and3are applied exhaustively, while Rule4is only applied if none of the other three can be applied.
At the end of this process, the algorithm either solves the problem (giving eitherYES orNOas the answer), or it yields an equivalent instance(G, k);k≤kwhereGis of sizeO(k).
Reduction Rule 1 [29] LetSbe a minimal clique separator inGand letC1, . . . , Ct be the connected components ofG\S. We setGto be the disjoint union of the graphs G1, G2, . . . , Gt, whereGi is isomorphic toG[N[Ci]], 1≤i≤t, and setk←k.
By Proposition4, we have the following lemma.
Lemma 1 Rule1is safe.
Since each connected component of graphG produced by Rule1is an induced subgraph ofG, it follows that ifGis planar,d-degenerate, orH-minor free, thenG also has the same property.
Our next rule deletes vertices which are not part of any chordless cycle; as we show later (Lemma3), a vertexvsatisfies the conditions of the rule if and only if it is not part of any chordless cycle in the graph. This rule can be inferred from previous work due to Tarjan [29] and Berry et al. [3].
Reduction Rule 2 For a vertexvofG, letC1, C2, . . . , Ct be the connected compo- nents ofG\N[v]. If for every 1≤i≤t, the vertex setN (Ci)is a clique inG, then setG←G\ {v},k←k.
Lemma 2 Rule2is safe.
Proof LetH be a chordal graph obtained by addingk edges toG. Chordality is a hereditary property, and thus the graphH=H\ {v}is chordal. ButHis a triangu- lation ofG=G\ {v}, and since it is obtained by adding at mostkedges, we have thatGhas a fill-in of size at mostk≤k.
For the opposite direction, letHbe a minimal triangulation obtained fromGby adding the set of fill edgesF, where|F| ≤k. Then the graphHobtained by adding FtoGis chordal. Indeed, ifH was not chordal, it would contain a chordless cycle Aof length at least 4 passing throughv. Letwbe a vertex ofAnot adjacent tovand letCbe the connected component ofG\N[v]containingw. The setS=NG(C)is a clique minimal separator inGand thus by Corollary1, we can conclude that inH every path fromwtovshould go through some vertex ofS. Hence the setScontains at least two non-consecutive (inA) verticesaandbofA. ButSis a clique inG, and thus is a clique inH. Hence,a andb form a chord inA, which is a contradiction.
Therefore,H is chordal.
In Reduction Rule2, we only remove a vertex, and thus this rule does not change hereditary properties of graphs, like beingH-minor free. We now state some useful properties of graphs on which the above reduction rules cannot be applied.
Lemma 3 A vertexvin a graphGdoes not satisfy the conditions of Reduction Rule2 if and only ifvis part of a chordless cycle inG.
Proof Letv be a vertex in Gwhich does not satisfy the conditions of Reduction Rule2. Then there exists a connected componentC of G\N[v] such that N (C) contains two non adjacent vertices, sayx, y∈N (v). LetP be a shortest path fromx toy inG[C∪ {x, y}]. Sincexandyare not adjacent, the pathP is of length at least two; letP= x=v1, v2, . . . , v=y. SinceP is an induced path,v, x=v1, v2, . . . , v=yis a chordless cycle containingv.
Conversely, letv=v1, v2, v3, . . . , vr−2, vr−1, vr =vbe a chordless cycle inG containingv, and letCbe the connected component ofG\N[v]which containsv3 andvr−2. The vertex setN (C)does not contain the edge{v2, vr−1}and hence is not
a clique.
If Reduction Rule2does not apply to a graph, then every vertex in the graph has at least one edge of every fill-in in its neighbourhood, in the following sense.
Lemma 4 LetGbe a graph to which Rule2cannot be applied, and letF be an edge set such thatH=(V , E∪F )is chordal. Then for every vertexvinG, there either exists an edge{v, x} ∈F, or an edge{u, w} ∈F, whereu, w∈N (v).
Proof From Lemma3it follows that every vertexvinGis part of at least one chord- less cyclev=v1, v2, v3, v4, . . . , vt. From Proposition3 it follows—by induction on the length of the chordless cycle—that for every vertexvthere is either a fill edge {v, vi} ∈F or an edge{v2, vt} ∈F, fori∈ {3, . . . , t−1}.
Our next reduction rule pertains to almost-clique separators.
Reduction Rule 3 [6] Let(G, k)be an input instance of MINIMUMFILL-IN. IfG has a minimal separatorSsuch that adding exactly one edge toG[S]turns it into a complete graph, and there exists a vertexvinV (G)\Ssuch that all vertices ofSare adjacent tov, then
1. TurnG[S]into a complete graph by adding one edge, 2. Apply Rule1on the resulting minimal clique separator, and 3. Reducekby one.
The correctness of this rule is evident from Proposition2and Lemma1. We now show that the rule preserves the planarity of the graph. Observe that if the input graph Gis planar, then|S| ≤4.
Claim 1 Reduction Rule3preserves the planarity of the graph.
Proof LetG, S be as in the statement of the rule, and letG be the graph obtained by applying the rule toG. By Proposition1, there are at least two full components, sayC1, C2, associated withS inG. Let{u, v}be the missing edge inG[S]. Notice that for eachi=1,2, there is auv-path inGwith all internal vertices contained in Ci. This implies that each of the connected components of the output graphG is a
minor of planar graphG, and thus is planar.
Reduction Rule 4 Let (G, k)be an input instance of MINIMUM FILL-IN, where none of the Rules1,2, and3can be applied. If|V (G)|>6k−4 then return a trivial NOinstance and stop.
Lemma 5 Reduction Rule4is safe.
Proof Let(G, k) be a YES instance whereG=(V , E)is planar and none of the Rules1,2, and3can be applied. We now argue that|V| ≤6k−4.
LetF be an edge set such that|F| ≤kandH=(V , E∪F )is chordal, and letVF be the set of at most 2kvertices that are incident to the edges inF. We then have:
Claim 2 Each vertexv∈V \VF is adjacent to at least three vertices ofVF. Proof Since Rule2cannot be applied on vertexvit follows thatN[v]V. LetCbe a connected component ofG\N[v]and letS=N (C)be the minimal separator ofG separating vertices ofC fromv. Rules1and3cannot be applied onS, so the graph G[S]is missing at least two edges{x1, y1}and{x2, y2}. By finding a shortest path P fromxj toyj inG[C∪ {xj, yj}]we can create a chordless cycle consisting ofP andxj, v, yj forj ∈ {1,2}. By Proposition3every fill-in of a chordless cycle either adds an edge incident to vertexvon the chordless cycle or adds a fill edge between its two unique neighbours. By definition there is no fill edge inF incident tov, and thus both{x1, y1}and{x2, y2}are contained inF. Two edges have to be incident to
at least three vertices, and the claim follows.
We construct a new graphB=(V , EB)whose edge setEBis a subset ofE, such that {u, w} ∈EB if and only if{u, w} ∈E, u∈VF, andw∈VF. The graphB is planar since it is a subgraph of planar graphG, and is bipartite by construction with the two partite sets beingV1=VF andV2=V \VF. As noted before,|V1| ≤2k;
we now bound|V2|. LetF be the set of faces in any fixed planar embedding ofB.
Lets=
f∈F(number of edges on the facef ). SinceBis bipartite, each face has at least four sides, and sos≥4|F|. Since each edge ofBlies on at most two faces in the embedding, it is counted at most twice in this process, and sos≤2|EB|. Thus 4|F| ≤ 2|EB|. From this and the well-known Euler’s formula for planar graphs applied toB (namely,|V| − |EB| + |F| ≥2; observe thatBmay be a disconnected graph) we get
|EB| ≤2|V| −4=2(|V1| + |V2|)−4. By Claim2each vertex inV2has degree at least 3 inB, and so|EB| ≥3|V2|. Combining these we get|V2| ≤2|V1| −4≤4k−4,
and so|V| = |V1| + |V2| ≤6k−4.
We now argue that all executions of the rules can be performed in polynomial time. By Proposition4, a minimal clique separator is a clique separator in every minimal triangulation of the given graph. A minimal triangulation can be constructed inO(nm)time [28] and the minimal separators of the triangulation which are also cliques inGcan be enumerated inO(nm)time [4]. As a consequence Rule1can be executed in polynomial time. For the remaining three rules it is not hard to see that we can check, find an instance, and execute the rule in polynomial time.
The rules are applied exhaustively in the order they are described. Rule1is glob- ally applied at mostn−1 times, since all minimal clique separators we split on, even across connected components, are the so called “non-crossing” minimal separators in the initial graph, and a graph onnvertices has at mostn−1 pairwise non-crossing minimal separators [25]. Each time Rule1is applied, at mostnconnected compo- nents are created, and each of them contains at mostnvertices. Thus, Rule2is applied at mostO(n3)times. Rule3is applied at mostktimes as one fill edge is added each time, and finally Rule4is applied only once. Thus we get
Theorem 1 MINIMUMFILL-INhas a planar kernel of sizeO(k)in planar graphs.
4 A Subquadratic Kernel for d-Degenerate Graphs
We now describe two reduction rules ford-degenerate graphs. The second among these is in fact an algorithm which specifies how to apply Rule2and the first rule of this section in tandem. Given a problem instance(G, k)whereGis ad-degenerate graph, the second rule outputs an equivalent instance(G, k)such thatk≤kand
|V (G)| =O(k3/2). However, these rules do not guarantee that the resulting graph G is d-degenerate. We will later show how to obtain an equivalent d-degenerate graph fromGwhile keeping the size bounded byO(k3/2).
The next reduction rule says that if two non-adjacent vertices in ad-degenerate graphG have many common neighbours, then the missing edge between the two vertices belongs to every small fill-in ofG.
Reduction Rule 5 Let(G, k)be an instance whereGisd-degenerate. Letu, w be two non-adjacent vertices inG, and letb= |N (u, w)|. If(b/2)(b−1−2d) > k, then setG←(V (G), E(G)∪ {{u, w}}), k←k−1.
Lemma 6 Rule5is safe.
Proof LetF be a fill-in ofGof size at most k. We claim that {u, w} ∈F. For, if {u, w}∈/F, then letH be the chordal graph obtained by adding the edges inF to the graphG. Sinceuandware non-adjacent inH, there exists anu, w-separator inH, and every minimalu, w-separator inH contains all the vertices inN (u, w). Since H is chordal, every minimal separator inH is a clique [10], and so the vertex set N (u, w)induces a clique inH. Hence the subgraphH[N (u, w)]contains(b−1)b/2 edges, whereb= |N (u, w)|. SinceGisd-degenerate, the subgraphG[N (u, w)]con- tains at mostdbedges. Thus|F| ≥(b−1)b/2−db=(b/2)(b−1−2d) > k, a con- tradiction, and so{u, w} ∈F. It immediately follows thatF \ {{u, w}}is a fill-in of Gof size at mostk−1.
Conversely, ifGhas a fill-inFof size at mostk−1, thenF∪ {{u, w}}is a fill-in
ofGof size at mostk.
Reduction Rule 6 Let(G, k)be an instance whereGisd-degenerate. Set(G, k) to be the instance output by Algorithm1.
Lemma 7 Rule6is safe.
Proof By Rule2 it is safe to delete vertexu in Line3. Lete1, e2, . . . , e|F 0| be the set of edges inF0. By Rule5 it is safe to add edgee1toGand decrementk. Let our induction hypothesis be that it is safe to add edges e1, e2, . . . , ei−1 toG and reducekbyi−1, and let us argue that it is also safe to add edgese1, e2, . . . , ei and reducek byi. Letki−1=k−(i−1). Edgeei= {x, y}was added toF0 because (b/2)(b−1−2d) > k where b= |NG(x, y)|. In the extreme case, all the edges e1, e2, . . . , ei−1 are added between vertices inNG(x, y), but(b/2)(b−1−2d)− (i−1) > k−(i−1)=ki−1 and thus it is safe to add edgeei as well and reduce ki−1by 1. We can now conclude that(G, k)in Line8is aYESinstance if and only
Algorithm 1 Reduction Rule6ford-degenerate graphs
1: procedureRU L E6(G,k) Gis assumed to bed-degenerate.
2: while (Rule2applies to(G, k)and a vertexu∈V (G)) do
3: G←G\ {u}
4: F0← ∅
5: for (each nonadjacent pairx, y∈V (G)) do
6: if (Rule5applies to(G, k)and the non-adjacent verticesx, y) then
7: F0←F0∪ {{x, y}}
8: G←(V (G), E(G)∪F0), k←k− |F0|
9: D0← ∅
10: while (Rule2applies to(G, k)and a vertexu∈V (G)) do
11: G←G\ {u},D0=D0∪ {u}
12: F0←E(G)∩F0
13: ifk<0 or|V (G)|>2k+k(2√
k+2d+1)then
14: return a trivialNOinstance.
15: else
16: return(G, k)
if(G, k)is. Finally by the safeness of Rule2, instance(G, k)at Line16is aYES instance if and only if(G, k)is.
It remains to argue that we can safely return a trivialNO instance if|V (G)|>
2k+k(2√
k+2d+1), whereGis the graph at Line13. Let us assume that(G, k) is aYESinstance and letF be a set of edges such thatH=(V (G), E(G)∪F )is chordal and|F| ≤k. LetVF be the set of vertices incident to edges ofF, and letVF0 be the set of vertices incident to edges ofF0.
By Line10in Algorithm1, Rule2is applied exhaustively, and thus by Lemma4 every vertex of V (G)\(VF ∪VF0) is contained in NG(x, y) for some edge {x, y} ∈F. From the fact thatG is reduced with respect to Rule5 (See Line6of Algorithm1), we get that|NG(x, y)| =b <2√
k+2d+1. To see this, observe that a clique onbvertices containsb(b−1)/2 edges whileG[NG(x, y)]contains at most dbedges. Thus ifb≥2√
k+2d+1 then b(b−1)/2−db=b/2(b−1−2d)≥ ((2√
k+2d+1)/2)(2√
k) > kwhich is a contradiction to the fact that{x, y} ∈F0. Notice that|VF| + |VF0| ≤2k, since(G, k)is aYESinstance. In particular, no- tice thatNG(x, y)\(VF∪VF0)⊆NG(x, y). Summing over all edges inF, we get
|V (G)| ≤ |VF∪VF0| +
{x,y}∈F|NG(x, y)| ≤2k+k(2√
k+2d+1).
Observe that Rule5—which is applicable only when the input graph isd-degenerate
—adds an edge to the graph. The graph resulting from applying Rule6—which adds the edge setF0found by applying Rule5—is thus not necessarilyd-degenerate. The graph output by Rule6can be modified to becomed-degenerate while preserving the bound on its size, and this gives anO(k3/2)kernel for MINIMUM FILL-INin d-degenerate graphs.
Theorem 2 MINIMUM FILL-IN has a d-degenerate kernel of size O(k3/2) in d-degenerate graphs.
Proof Since a 1-degenerate graph is a forest, and every forest has a fill-in of size zero—since the forest is chordal—we can assume without loss of generality thatd≥ 2. Let(G, k)be an instance of MINIMUMFILL-INwhereGis ad-degenerate graph.
The kernelization algorithm applies Reduction Rule6—Algorithm1—to(G, k)to obtain an equivalent instance(G, k). If(G, k)is the trivialNOinstance returned by Line14, then it isd-degenerate and its size is a constant, and the kernelization algorithm returns(G, k)itself as the kernel.
Now let(G, k)be a non-trivial instance returned by Line 16. Observe thatG is obtained fromGby (i) deleting some vertices—Line3,—(ii) adding edgesF0— Line6,—and (iii) deleting verticesD0—Line11. Edge setF0is defined in Line12 as the set of edges inF0 with both endpoints inV (G): these are the edges added in Line6which survive inG.
The kernelization algorithm constructs a new graph G from G by doing the following for each edge{u, v} ∈F0: remove the edge{u, v}, add two new vertices auv, buv, and make both these vertices adjacent to bothuandv. The algorithm returns (G, k)as the kernel, wherek=k+ |F0|. LetG1be the graphGwhere edge set F0is removed.
To see that(G, k)satisfies all the requirements, note thatG1isd-degenerate by the hereditary property ofd-degenerate graphs, andG=(V (G), E(G1)∪F0). The graphGisd-degenerate since it can be obtained fromG1by adding a sequence of vertices, each of degree two. Since each edge inF0corresponds to two new vertices inG,|V (G)| = |V (G1)| +2|F0| ≤4k+k(2√
k+2d+1).
It remains to argue that(G, k)is aYESinstance if and only if (G, k)is. If (G, k)is aYESinstance, then letFbe a fill-in ofGof size at mostk, and letH be the chordal graph obtained by adding the edges inFtoG. LetF=F0∪F, and letHbe the graph obtained by adding the edges inFto the graphG. Observe that H can be obtained from the chordal graphHby adding a sequence of vertices of degree two each, each of which is adjacent to the two end-points of some edge inF0. It follows thatHis chordal—any potential chordless cycle inHhas to contain one of these new vertices, but every cycle passing through such a vertex has the respective edge inF0as a chord. ThusFis a fill-in ofGof size at most|F0| +k=k.
Conversely, let(G, k)be a YES instance. Observe that for each{u, v} ∈F0, the vertex set S= {u, v}satisfies all the conditions of Proposition 2 inG—S is a minimalauv, buv-separator,G[S]is missing the one edge which will make it a clique, and the vertexauv∈V (G)\S is adjacent to every vertex in S. So there exists a minimum fill-inFofGsuch thatF0⊆F, and|F| ≤k. LetHbe the chordal graph obtained by adding the edges inFto the graphG, and letHbe the graph obtained by deleting all the vertices{auv, buv| {u, v} ∈F0}fromH. ThenH can be obtained by adding the edges inF=F\F0toG, andHis chordal by the hereditary property of chordality. ThusFis a fill-in ofGof size at mostk.
5 A Subquadratic Kernel forH-Minor Free Graphs
It is known [30] that everyH-minor free graph isd-degenerate ford≤αh√ log h, whereh= |V (H )|andα >0 is a constant. As we have already shown in Sect.4, the application of Rule6on an instance(G, k)of MINIMUMFILL-INwhereGis a d-degenerate graph results in an equivalent instance(G, k)whereG hasO(k3/2) vertices. However, thisGis not necessarilyH-minor free ord-degenerate. In Theo- rem2, we show how to transformGinto ad-degenerate graph without significantly increasing its size. In this section, we show how to transformGto anH-minor free graph, if the starting instanceGisH-minor free.
The actual transformation is somewhat involved, and so we first present an in- formal overview of the procedure. Let(G, k)be an instance of MINIMUM FILL-IN
whereGisH-minor free, and let(G, k)be the instance obtained by applying Al- gorithm1on (G, k). For simplicity of explanation, we assume that no vertices are deleted fromGby Line3of Algorithm1. Since the property of beingH-minor free is preserved when vertices are deleted, this assumption is harmless. So the graphG is obtained fromGby (i) adding the setF0 of edges, and (ii) deleting the setD0of vertices. Of these, the first operation is the only one which could possibly result in Gbeing notH-minor free. Thus, to convertGinto an equivalentH-minor free in- stance, we only need to take care of the edge setF0. More specifically, we only need to take care of the edges setF0, which is the subset ofF0which survives inGafter the deletion ofD0.
A first attempt at this would be to delete the edges inF0fromG, and to increment the parameter by|F0|. The motivation for this is that since the edges inF0are forced in any fill-in ofG(See Rule5and Line6of Algorithm1), it is sufficient to remember their count. Unfortunately, this does not work since we delete vertices fromG. Recall that the edges inF0are forced in any fill-in of Gprecisely because the end-points of each such edge has sufficiently many common neighbours. It may so happen that after deleting the setD0of vertices, this property no longer holds for some (or all) of the edges inF0, and so this naive strategy is not safe : we cannot just forget all ofF0 and remember their count instead.
To deal with this, we use a somewhat more sophisticated, multi-step strategy. To simplify the discussion, we useG˜ to denote the graph at any point during this pro- cedure, andk˜ to denote the parameter. We start by settingG˜ =G\F0, andk˜=k. Observe thatG˜ isH-minor free, but is not necessarily safe for the parameterk˜(for the reason mentioned above). First, we check if there are edges inF0which still have the above property which forces them into any fill-in ofG. These can be safely “for-˜ gotten”, and to do this we incrementk˜by the number of such edges. We also remove these edges fromF0. Observe that the graph remains unchanged by this step. After this, we check if we can find a distinct vertex inD0for each edge inF0, such that the vertex is a common neighbour of the end-points of the edge inG. If we can find such a “matching” set of vertices inD0, then we add all the edges inF0toG˜ and return (G,˜ k)˜ as the kernel. This is clearly safe, andG˜ isH-minor free because each edge inF0can be thought of as replacing a path of length two (via a vertex ofD0) which was deleted fromG.
If we cannot find such a “matching”, then by Hall’s Matching Theorem there exists a subsetXof edges of the setF0which “see” inGa strictly smaller subset—sayY— of vertices fromD0. We find such a pair of setsX, Y. We first add the vertices inY toG. Then we add to˜ G˜ all those edges ofGwhich are incident with vertices inY whose other end points are present inG. Finally, we delete the set˜ XfromF0and the setYfromD0, and setk˜= ˜k+ |X|. Observe that we restored inG˜ the neighbourhood of the edges inX. Therefore all these edges again become forced in any fill-in ofG,˜ and so this step is safe. Further,G˜ is a subgraph ofG, and so isH-minor free.
We repeat the last two steps—finding a “matching” or a small neighbourhood—
till all ofF0is exhausted. This adds at most as many vertices toG˜ as the initial size ofF0. In the end we return(G,˜ k)˜ as the kernel.
We now make this more formal.
Theorem 3 LetHbe a fixed graph. MINIMUMFILL-INhas anH-minor free kernel of sizeO(k3/2)inH-minor free graphs.
Proof Let(G, k)be an instance of MINIMUMFILL-INwhereGisH-minor free, and let(G, k0=k)be the instance obtained by applying Rule6on(G, k). If a trivial NOinstance is returned by Rule6, then we also returnNO. In the remaining part we assume that Algorithm1returns from Line16.
LetF0be the set of edges defined in Line12of Algorithm1, and letD0be the vertex set computed by the algorithm by the time it reaches Line12. Let c1 be the number|F0| − |F0|. Recall thatF0 is the set of all fill edges which would be added toGby Rule5.D0is the set of vertices which become eligibile for deletion as per Rule2 in the graph obtained by adding these fill edges (Line8).F0 is the subset of edges inF0 which survive after the deletion of the vertices inD0, and c1 is the number of edges inF0which are deleted along with the vertices ofD0.
Recall that the property of beingH-minor free is preserved by the deletion of vertices (or edges). Therefore, we assume without loss of generality that no vertex is deleted in Line3of Algorithm1. LetM0=(V0, E0)be the graph obtained from G by removing all the edges inF0. Fori≥1, we create a sequence of graphs by applying additional reduction rules, such that all the graphs in the sequence areH- minor free and when none of the reduction rules applies, the resulting graph has size O(k3/2)and so it is the desired kernel. We construct the sequence inductively, starting fromM0. To proceed, we prove that for eachi≥0 the tuple(Mi, Fi, Di, ki)has the following properties:
1. Mi=(Vi, Ei)isH-minor free;
2. |Fi| = |F0| −i;
3. |Vi| =O(k3/2);
4. V (G)=Vi∪Di;
5. graphGi=(V (G), E(G)∪Ei)isH-minor free;
6. graphTi=(Vi, Ei∪Fi)has a fill-in withki edges if and only ifGhas a fill-in of size at mostk, and
7. k=c1+ |Fi| +ki.
Let us first argue that all seven properties hold fori=0, which is the base case.
Indeed, 1: GraphM0is obtained by deleting verticesD0fromG, and thus isH-minor
free. 2:|F0| = |F0| −0. 3: SinceV0is output by Rule6we have that|V0| =O(k3/2).
4: BecauseM0=G[V \D0], we have thatV (G)=V0∪D0. 5: SinceE0⊆E(G), we get that the graphG0=(V (G), E(G)∪E0)isH-minor free. 6: Since Rule6is safe, it follows thatT0=(V0, E0∪F0)has a fill-in withk0=kedges if and only if Ghas a fill-in withkedges. 7: Since Rule6is safe we have that c1+ |F0| +k0=
|F0| − |F0| + |F0| +k0= |F0| +k0=k.
For the induction step, fori≥0, we assume that all properties hold for(Mi, Fi, Di, ki). We construct a new tuple(Mi+1, Fi+1, Di+1, ki+1)from(Mi, Fi, Di, ki)by applying the three reduction rules below in the order they are given. The first rule increments the value ofi. The second rule is applied only if the first cannot be applied, and recognizes kernels that can be returned directly. The third rule is applied only if none of the previous two can be applied, and ensures that the first rule can be applied again.
Reduction Rule 7 For each edge{u, w} ∈Fi defineb= |NMi(u, w)|. Let{u, w}be an edge inFisuch that(b/2)(b−1−2d) > k, wheredis the degeneracy of the input graphG. ThenMi+1=Mi,Fi+1=Fi\ {{u, w}},ki+1=ki+1,Di+1=Di. Claim 3 Rule7is safe; that is, it preserves all the seven properties.
Proof
1. Mi+1isH-minor free, asMi+1=Mi; 2. |Fi+1| = |F0| −(i+1), as|Fi+1| = |Fi| −1;
3. |Vi+1|isO(k3/2), asVi+1=Vi;
4. V (G)=Vi+1∪Di+1, asVi+1=Vi andDi+1=Di;
5. graphGi+1=(V (G), E(G)∪Ei+1)isH-minor free, asEi+1=Ei;
6. graphTi+1=(Vi+1, Ei+1∪Fi+1)can be triangulated by the addingki+1edges if and only ifGcan be triangulated by the addingkedges, see the arguments below, and
7. k=c1+ |Fi+1| +ki+1as|Fi+1| = |Fi| −1 andki+1=ki+1.
The remaining claim (item 6) is that there is a fill-in of graphTi+1=(Vi+1, Ei+1∪ Fi+1)withki+1edges if and only if the fill-in ofGis at mostk. Notice thatki+1≤k and by Rule5there is no triangulation ofTi+1with at mostkfill edges that do not add the edge{u, w}. ThusTi+1can be triangulated by addingki+1edges if and only ifTi can be triangulated by addingki edges and the claim holds.
Let us assume that Rule7cannot be applied to the tuple(Mi, Fi, Di, ki). Then for every edge{u, w} ∈Fi there exists at least one vertexx∈Di such thatx∈NG(u)∩ NG(w).
Construct a bipartite graphBi=(Pi, Qi, Zi), where there is a vertexvuw∈Pifor each edge{u, w} ∈Fi, there is a vertexx∈Qi for each vertexx∈Di, and there is an edge{vuw, x} ∈Zi if and only ifu, w∈NG(x).
Reduction Rule 8 If Bi has a matching saturating Pi, then return the instance (GH=(Vi, Ei∪Fi), ki).