A Polynomial Kernel for Diamond-Free Editing
Yixin Cao
Department of Computing, Hong Kong Polytechnic University, China.
yixin.cao@polyu.edu.hk
0000-0002-6927-438X

Ashutosh Rai
Department of Computing, Hong Kong Polytechnic University, China.
ashutosh.rai@polyu.edu.hk

R. B. Sandeep

arXiv:1803.03358v1 [cs.DS] 9 Mar 2018

Institute for Computer Science and Control, Hungarian Academy of Sciences, (MTA SZTAKI,)
Hungary; and Indian Institute of Technology Dharwad, India.
sandeeprb@iitdh.ac.in

Junjie Ye
Department of Computing, Hong Kong Polytechnic University, China.
junjie.ye@polyu.edu.hk
0000-0003-3924-008X

Abstract
An H-free editing problem asks whether we can edit at most k edges to make a graph contain
no induced copy of the fixed graph H. We obtain a polynomial kernel for this problem when
H is a diamond. The incompressibility dichotomy for H being a 3-connected graph [4] and the
classical complexity dichotomy [1] suggest that except for H being a complete/empty graph, Hfree editing problems admit polynomial kernels only for a few small graphs H. Therefore, we
believe that our result is an essential step toward a complete dichotomy on the compressibility
of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion
problem, which is far simpler than the previous kernel of the same size for the problem.
2012 ACM Subject Classification G.2.2 Graph Algorithms, I.1.2 Analysis of Algorithms
Keywords and phrases Kernelization, Diamond-free Graph, H-free editing
Funding Supported in part by the Hong Kong Research Grants Council (RGC) under grant
PolyU 252026/15E, the National Natural Science Foundation of China (NSFC) under grant
61572414, and the European Research Council (ERC) under grant 725978.

1

Introduction

A graph modification problem asks whether one can apply at most k modifications to a
graph to make it satisfy certain properties. By modifications we usually mean additions
and/or deletions, and they can be applied to vertices or edges. Although other modifications
are also considered, most results in literature are on vertex deletion and the following three
edge modifications: edge deletion, edge completion, and edge editing (deletion/completion).
As usual, we use n to denote the number of vertices of the input graph. For each graph
modification problem, one may ask three questions: (1) Is it NP-complete? (2) Can it be
solved in time f (k) · nO(1) for some function f , and if yes, what is the (asymptotically) best
f ? (3) Does it have a polynomial kernel? The first question concerns the classic complexity,
while the other two are about the parameterized complexity [10, 7]. With parameter k, a
problem is fixed-parameter tractable (FPT) if it can be solved in time f (k) · nO(1) for some

23:2

A Polynomial Kernel for Diamond-Free Editing

function f . On the other hand, given an instance (G, k), a kernelization algorithm produces
in polynomial time an equivalent instance (G0 , k 0 )—(G, k) is a yes-instance if and only if
(G0 , k 0 ) is a yes-instance—such that k 0 ≤ k. It is a polynomial kernel if the size of G0 is
bounded from above by a polynomial function of k.
In many senses, edge modification problems are more elusive than vertex deletion problems.
For hereditary properties, a classic result of Lewis and Yannakakis [14] states that all the
vertex deletion problems are either NP-hard or trivial. In contrast, the picture for edge
modification problems is far murkier. Earlier efforts for edge deletion problems [16, 8], though
produced fruitful concrete results, shed little light on a systematic answer, and it was noted
that such a generalization is difficult to obtain.
A basic and ostensibly simple case of graph modification problems is to make the graph
H-free, where H is a fixed graph on at least two vertices. (We say that a graph is H-free if
it does not contain H as an induced subgraph.) For this special case, all the three questions
have been satisfactorily answered for vertex deletion problems, at least in the asymptotic
sense. All of them are NP-complete and FPT,—indeed, H-free vertex deletion problems
admit simple |V (H)|k · nO(1) -time algorithms [3]. On the other hand, the reduction of Lewis
and Yannakakis [14] excludes subexponential-time algorithms (2o(k) · nO(1) -time algorithms)
assuming the exponential time hypothesis (eth) [12]. Further, as observed by Flum and
Grohe [10], the sunflower lemma of Erdős and Rado [9] can be used to produce polynomial
kernels for H-free vertex deletion problems.
Even restricted to this very simple case, a lot of questions are unanswered for edge
modification problems. Significant efforts have been devoted to an ongoing program that
tries to answer these questions in a systematic way, and promising progress has been reported
in literature. Recently, Aravind et al. [1] gave a complete answer to the first question by
fully characterizing graphs H on which the problems are NP-complete. In particular, the
H-free editing problem is NP-complete if and only if H contains at least three vertices. They
also excluded subexponential-time algorithms for the NP-complete H-free edge modification
problems, assuming eth. Noting that H-free edge modification problems can always be
solved in 2O(k) · nO(1) time [3], we are left with the third problem, the existence of polynomial
kernels.
Some of the H-free graph classes are important for their own structural reasons, e.g.,
most notably, cluster graphs and cographs, which are P3 -free graphs and P4 -free graphs
respectively; hence the edge modification problems toward them have been well-studied
[6, 11]. (Note that edge modification problems to P2 -free graphs, i.e., independent sets,
are trivial.) Given the simplicity of H-free edge modification problems, and the naive FPT
algorithms for them, it may sound shocking that many of them do not admit polynomial
kernels. Indeed, the earliest incompressibility results of graph modification problems, by
Kratsch and Wahlström [13], are on H-free edge modification problems. Guillemot et al. [11]
excluded polynomial kernels for H-free edge deletion problems when H is a path of length at
least seven or a cycle of length at least four. An influential result of Cai and Cai [4] furnishes
a dichotomy on the compressibility of H-free edge modification problems when H is a path,
a cycle, or a 3-connected graph.
We tend to believe that H-free edge modification problems admitting polynomial kernel
are the exceptions. Our exploration suggests that graphs on four vertices play the pivotal
roles if we want to fully map the territory. Let H be the complement graph of H. Then the
H-free edge deletion problem is equivalent to the H-free edge completion problem, while the
edge editing problems are the same for H-free and H-free graphs. We only need to consider
six four-vertex graphs listed in Figure 1; see Table 1 for a summary of compressibility results

Cao, Rai, Sandeep, Ye

23:3

of H-free edge modification problems when H is one of them. We conjecture that H-free
edge modification problems, when H being claw or paw, admit polynomial kernels.

(a) P4

(b) C4

(c) K4

(d) claw

(e) paw

(f) diamond

Figure 1 Graphs on four vertices (their complements are omitted).

H

deletion

completion

editing

K4
P4
diamond

O(k4 ) [5]
O(k3 ) [11]
O(k3 ) [15]

trivial
O(k3 ) [11]
trivial

O(k4 ) [5]
O(k3 ) [11]
O(k8 ) [this paper]

claw
paw

unkown
unkown

unkown
unkown

unkown
unkown

C4

no [11]

no [11]

no [11]

Table 1 The compressibility results of H-free edge modification problems for H being four-vertex
graphs. Note that every result holds for the complement H; e.g., the answers are also no when H is
2K2 .

We show a polynomial kernel for the diamond-free editing problem. Our observations
also lead to a cubic-vertex kernel for the diamond-free edge deletion problem, which is far
simpler than the previous kernel of the same size [15]. Formally, these two problems are
defined as following.
Diamond-free editing problem: Given an input graph G, can we edit (add/delete) at
most k edges to make it diamond-free?
Diamond-free edge deletion problem: Given an input graph G, can we delete at most
k edges to make it diamond-free?
On the other hand, the completion problem to diamond-free graphs is trivial: For each
diamond, there is no choice but adding the only missing edge.
Our key observations are on the maximal cliques. A graph G is diamond-free if and only
if every two maximal cliques of G share at most one vertex. We say that a maximal clique is
of type i if it shares an edge with another maximal clique, or type ii otherwise. It is not hard
to see that to make a graph diamond-free, we should never delete edges from a sufficiently
large clique. We thus put the maximal cliques of G into three categories, small type i, big
type i, and type ii. It turns out that a vertex participates in a diamond if and only if it is in
a maximal clique of type i, and the small type-i maximal cliques are crucial for the problem.
The first phase of our algorithm comprises two routine reduction rules for edge editing
problems. If a (non-)edge participates in k + 1 or more diamonds that pairwise share only
this (non-)edge, then it has to be in a solution of size at most k. (This is exactly the reason
why no edge is deleted from a “large” clique.) If there exists such an edge/non-edge, we
delete/add it. We may henceforth assume that these two simple rules have been exhaustively
applied. We are able to show that the ends of an edge added by a minimum solution must be

CVIT 2016

23:4

A Polynomial Kernel for Diamond-Free Editing

from some small maximal cliques of type i. The situation for deleted edges is slightly more
complex. The two ends of a deleted edge are either in a small maximal clique of type i, or in
a maximal clique of type ii. In the second case, the maximal clique has to intersect some
small maximal clique of type i.
The second phase of our algorithm uses three nontrivial reduction rules to delete irrelevant
vertices. To analyze the size of the kernel, we bound the number of vertices that are (a) in
small type-i maximal cliques only, (b) in big type-i maximal cliques but not in any small
type-i maximal clique, and (c) only in type-ii maximal cliques. First, we show an upper
bound on the number of type-i maximal cliques. This immediately bounds the number of
vertices in part (a), because each small type-i maximal clique has a bounded size. For part
(b), the focus now is to bound the sizes of big maximal cliques of type i. We introduce
another reduction rule to delete certain “private vertices” from them. On the other hand, the
pattern of vertices shared by big maximal cliques is very limited. We are thus able to bound
the number of vertices in part (b), and we are left with part (c). We correlate a maximal
clique K of type ii with small maximal cliques of type i: we would touch K only because
it had become type i after some operation, and this operation has to be an edge addition.
Recall that an edge can only be added between two vertices in part (a). For each pair of
them, we can build a blocker of O(k 2 ) vertices from part (c). One more reduction rule is
introduced to remove all vertices behind the blockers. Together with the bound of vertices in
part (a), this bounds the number of vertices in part (c).
Putting everything together, we obtain the main result of this paper.
I Theorem 1. The diamond-free editing problem has a kernel of O(k 8 ) vertices.
In passing we would like to mention that the reduction rules in the second phase of our
algorithm only delete vertices, and none of the deleted vertices is from a small maximal
clique of type i. Hence, the main structure of the graph will not change, and this allows us
to run them only once, and more importantly, we do not need to re-run the reduction rules
in the first phase.
Before we conclude this section, let us have some remarks on future work. The main
purpose of this paper is to take a step toward a complete dichotomy on the compressibility
of H-free edge modification problems. Although our kernel for the diamond-free editing
problem does not seem to be tight, we do not consider obtaining a smaller kernel a pressing
issue. Instead, we would ask for the existence of polynomial kernels for the H-free editing
problem in general, and for H being claw or paw in particular.
Another question one may ask for graph modification problems is: (4) Does it admit a
constant-ratio approximation algorithm? Again, the answer is simply yes for H-free vertex
deletion problems. Once an induced copy of H is found, we delete all its vertices, which
achieves ratio |V (H)|. However, this simple algorithm breaks down for edge modification
problems: An edge added or deleted to fix an erstwhile H may introduce new one(s).
This kind of propagations are the core difficulty of these problems [4, 2]. Hence, both the
approximability and the compressibility seem to hinge on whether the propagations can be
tamed, though maybe in different senses.
Outline of the Paper. After two simple reduction rules, Section 2 studies maximal cliques in
the graph on which these two rules are not applicable, and how a minimum solution may
impact them. Section 3 presents the main reduction rules, and establishes the bounds on the
numbers of vertices in different categories, thereby proving the main theorem of the paper.
Using the properties established in previous sections, the last section briefs a very simple
kernelization algorithm for the diamond-free edge deletion problem.

Cao, Rai, Sandeep, Ye

2

23:5

Maximal cliques

All graphs discussed in this paper are undirected and simple. A graph G is given by its
vertex set V (G) and edge set E(G). For a set U ⊆ V (G) of vertices, we denote by G[U ]
the subgraph induced by U , whose vertex set is U and whose edge set comprises all edges
of G with both ends in U . We use G − v, where v is a vertex of G, as a shorthand for
G[V (G) \ {v}]. Since we are dealing with an edge editing problem, it does not make much
sense to distinguish edges and non-edges: A non-edge of the input graph may be added so it
becomes an edge of the resulting graph, and vice versa. In a diamond, we refer to the edge
between the two degree-three vertices as the cross edge, and the only non-edge the missing
edge.
For a set E+ of edges, we denoted by G + E+ the graph obtained by adding edges in E+
to G, i.e., its vertex set is still V (G) and its edge set becomes E(G) ∪ E+ . The graph G − E−
is defined analogously. Throughout the paper we always tacitly assume E+ ∩ E(G) = ∅ and
E− ⊆ E(G); hence E+ and E− are disjoint. A solution of an instance (G, k) consists of a set
E+ of added edges and a set E− of deleted edges such that G + E+ − E− is diamond-free and
|E+ ∪ E− | ≤ k. We use E± as a shorthand for E+ ∪ E− , and there should be no ambiguities:
E+ = E± \ E(G) and E− = E± ∩ E(G). We also use G4E± as a shorthand for G + E+ − E− .
We start from a routine step for edge editing problems. If an edge uv participates in k + 1
or more diamonds that pairwise share only this edge, then it has to be in any solution of size
at most k. The following two reduction rules, taking care of the cases uv being the missing
edge and being the cross edge respectively, would suffice for our purpose. The correctness of
them is straightforward: If we do not add/delete uv, then we have to delete/add at least
k + 1 edges.
I Rule 1. If there exist a non-edge uv and 2k + 2 distinct vertices x1 , y1 , . . . , xk+1 , yk+1 in
N (u) ∩ N (v) such that xi yi ∈ E(G) for all 1 ≤ i ≤ k + 1, then add uv and decrease k by one.
I Rule 2. If there exist an edge uv and 2k + 2 distinct vertices x1 , y1 , . . . , xk+1 , yk+1 in
N (u) ∩ N (v) such that xi yi 6∈ E(G) for all 1 ≤ i ≤ k + 1, then delete uv and decrease k by
one.
For a pair of nonadjacent vertices u, v, whether Rule 1 is applicable to uv can be decided
by finding a maximum matching in G[N (u) ∩ N (v)]. Likewise, for uv ∈ E(G), we can find a
maximum matching in the complement graph of G[N (u) ∩ N (v)]. Therefore, Rules 1 and 2
can be applied in polynomial time. We call an instance (G, k) reduced if neither of Rules 1
and 2 is applicable to it. In the rest, we will focus on reduced instances. A similar idea as
the two rules enables us to exclude some (non-)edges from consideration.
I Proposition 2. Let E± be a solution to a yes-instance (G, k). A (non-)edge uv cannot be
in E± if
(i) uv ∈ E(G) and there are k + 1 pairwise adjacent vertices in N (u) ∩ N (v); or
(ii) uv 6∈ E(G) and there are k + 1 pairwise nonadjacent vertices in N (u) ∩ N (v).
Proof. Suppose for contradiction to assertion (i) that uv ∈ E− . Let K be a set of k + 1
pairwise adjacent vertices in N (u) ∩ N (v), and let X ⊆ K be the set of vertices x with xu or
xv in E− . Vertices in K \ X remain adjacent to both u and v in G − E− . Since the final
graph is diamond-free, E− must contain all edges among K \ X. Therefore,
|E− | ≥ 1 + |X| + (|K \ X| − 1) = k + 1,
which is impossible because E± is a solution to (G, k). The argument for assertion (ii) is
similar and hence omitted.
J

CVIT 2016

23:6

A Polynomial Kernel for Diamond-Free Editing

I Proposition 3. Let (G, k) be a reduced yes-instance. For each (non-)edge uv in a solution
of (G, k), the cardinality of N (u) ∩ N (v) is at most 3k.
Proof. We consider only uv ∈ E− , and the argument for uv ∈ E+ is similar and omitted.
Let W = N (u) ∩ N (v); we find a maximum matching in the complement graph of G[W ],
and let W 0 be the ends of the edges in the matching. Since Rule 2 is not applicable (to uv),
|W 0 | ≤ 2k. There cannot be non-edges between vertices in W \ W 0 ; then by Proposition 2(i),
the size of W \ W 0 is at most k. Therefore, |W | ≤ 3k.
J
Our algorithm will be mostly concerned with maximal cliques. According to Proposition 2(i), a maximal clique on k + 3 or more vertices cannot be touched by a minimum
solution “from inside,” but it may be touched “from outside”—i.e., edges may be added
between it and other vertices. We call a maximal clique big if it contains at least 3k + 2
vertices, and small otherwise. The bigness will prevent a maximal clique from being touched
from outside.
I Lemma 4. Let (G, k) be a reduced instance.
(i) Two big maximal cliques of G share at most one vertex.
(ii) If (G, k) is a yes-instance, then a big maximal clique of G remains a maximal clique
after applying a solution to (G, k).
Proof. Let K1 and K2 be two big maximal cliques of G. Suppose first that some vertex
u ∈ K1 \ K2 is adjacent to more than 2k + 1 vertices in K2 . Since K2 is a maximal clique, we
can find v ∈ K2 \ K1 nonadjacent to u, but then Rule 1 would be applicable (to uv). Hence,
every vertex in K1 \ K2 has at most 2k + 1 neighbors in K2 , which implies |K1 ∩ K2 | ≤ 2k + 1.
By assumption, |K1 | ≥ 3k + 2 and |K2 | ≥ 3k + 2. For each vertex in K1 \ K2 , we can find
k + 1 non-neighbors in K2 \ K1 . Therefore, we can greedily find k + 1 pairs of distinct
vertices {x1 , y1 }, . . ., {xk+1 , yk+1 } such that for all 1 ≤ i ≤ k + 1, (a) xi ∈ K1 \ K2 and
yi ∈ K2 \ K1 ; and (b) xi yi 6∈ E(G). Rule 2 would be applicable (to any edge in G[K1 ∩ K2 ])
if |K1 ∩ K2 | ≥ 2. Therefore, |K1 ∩ K2 | ≤ 1, and this concludes the proof for assertion (i).
Let E± be a solution to (G, k) and G∗ = G4E± . By Proposition 2(i), a big maximal
clique K in G remains a clique in G∗ . Let v ∈ V (G) \ K and let u ∈ K \ NG (v). Since Rule 1
is not applicable to uv, there are at most 2k + 1 neighbors of v in K. Since |K| ≥ 3k + 2, at
least one vertex in K remains nonadjacent to v in G∗ because |E+ | ≤ k. Therefore, K is a
maximal clique in G∗ as well.
J
It is well known that a graph G is diamond-free if and only if every pair of adjacent
vertices is contained in exactly one maximal clique of G. This characterization turns out to
be fundamental for the results in this paper. We say that a maximal clique of G is of type i
if it shares two or more vertices with some other maximal clique, and type ii otherwise (its
intersection with any other maximal clique is either 0 or 1 vertex). We can then rephrase the
first sentence of this paragraph as: A graph is diamond-free if and only if it has no maximal
clique of type i.
We use Kb (G), Ks (G), and K2 (G) to denote, respectively, the set of big maximal cliques
of type i, the set of small maximal cliques of type i, and the set of maximal cliques of type ii,
of G. A maximal clique in G is in precisely one of them.
I Proposition 5. A vertex of a graph G is in a maximal clique of type i if and only if it is
contained in an induced diamond in G.

Cao, Rai, Sandeep, Ye

23:7

Proof. Let u, v, x, y be four vertices inducing a diamond in G with cross edge uv. We can
find a maximal clique K1 containing u, v, x and a maximal clique K2 containing u, v, y. They
are different because x ∈ K1 \ K2 and y ∈ K2 \ K1 , hence both of type i.
We now consider the “only if” direction. Let K1 be a maximal clique of type i; by
definition, there is another maximal clique K2 such that K1 ∩ K2 ≥ 2. For any vertex
x ∈ K1 \ K2 and any vertex u ∈ K1 ∩ K2 , we can find another vertex v ∈ K1 ∩ K2 different
from u and a vertex y ∈ K2 \ K1 not adjacent to x (because K2 is maximal). Clearly, these
four vertices induce a diamond with cross edge uv.
J
The following two statements help us understand edges added by a minimum solution.
I Proposition 6. Let G be a diamond-free graph, and let U ⊆ V (G) such that every vertex
in V (G) \ U is adjacent to at most one vertex of U . If G[U ]4E± is diamond-free for a set
E+ of non-edges in G[U ] and a set E− of edges in G[U ], then so is G4E± .
Proof. Suppose for contradiction that G∗ = G4E± contains a diamond; let D be a set of
vertices inducing a diamond in G∗ . Since G[D] is not a diamond, at least one (non-)edge of
this diamond belongs to E± , and is between vertices of U . On the other hand, G[U ]4E±
remains diamond-free, hence D 6⊆ U . Therefore, |D ∩ U | is either two or three, but then a
vertex in D \ U is adjacent to at least two vertices of D ∩ U in G, a contradiction.
J
I Lemma 7. Let E± be a minimum solution to a reduced instance (G, k). Every vertex
incident to some edge in E+ is contained in some small maximal clique of type i in G.
Proof. Let uv be an edge in E+ , and let U be a maximal clique of G∗ containing u, v, where
G∗ = G4E± . We argue first that v is in some induced diamond in G[U ].
Suppose for contradiction that v participates in no diamond in G[U ]. Let X = NG (v) ∩ U .
The subgraph G[X] is a disjoint union of cliques: An induced path of length two would
make a diamond with v. Let {A1 , . . . , Ap } be those nontrivial cliques (containing more
than one vertex) in G[X]; let B be the other vertices of X; and let C = U \ NG [v]. Then
{A1 , . . . , Ap , B, C} is a partition of the set U \ {v}. Note that p or |B| may be 0, but |C| > 0
0
because u ∈ C. We construct a solution E±
for G[U ] whose size is smaller than the number of
0
0
non-edges in G[U ]. Let G be the graph obtained from G∗ by replacing G∗ [U ] with G[U ]4E±
.
Note that U is a type-ii maximal clique of G∗ ; by definition, |NG∗ (x) ∩ U | ≤ 1 for each
x ∈ V (G) \ U . By Proposition 6, G0 is diamond-free. This would however imply a strictly
smaller solution than E± , contradicting that E± is a minimum solution of (G, k).
0
0
0
Case 1, |B| ≥ |C|. We set E+
= ∅ and E−
the set of edges in G[C]. No edge in E−
is incident to v or N (v), and hence N (v) ∩ U is still a disjoint union of cliques in G0 . On
the other hand, no vertex x ∈ C is in any diamond in G0 [U ] because NG0 (x) ∩ U is an
independent set. Thus, G0 [U ] is diamond-free. Since B is an independent set of G, and v is
nonadjacent to C, we have
 
 
|B|
|C|
0
0
0
|E+ ∩ U 2 | ≥
+ |C| ≥
+ |C| > |E−
| = |E+
∪ E−
|.
2
2
0
0
Case 2, |B| < |C|. We set E+
to be the set of non-edges in G[B ∪ C], and E−
the set
0
of edges between B ∪ C and U \ (B ∪ C). To see that G [U ] is diamond-free, note that its
maximal cliques are B ∪ C and {v} ∪ Ai for 1 ≤ i ≤ p, whose intersection is either {v} or
empty. We then calculate the cardinality of E+ ∩ U 2 , which comprises three parts, those
0
among B ∪ C, which is exactly E+
, those between C and v, and those between C and Ai ’s.
Since v does not participate in any diamond in G, a vertex in C is adjacent to at most one

CVIT 2016

23:8

A Polynomial Kernel for Diamond-Free Editing

vertex of Ai , 1 ≤ i ≤ p. In other words, for each x ∈ C and each 1 ≤ i ≤ p, the number of
non-edges between x and Ai is at least one. Therefore
0
0
0
0
|E+ ∩ U 2 | ≥ |E+
| + |C| + |C| × p > |E+
| + |B| + |C| × p ≥ |E+
| + |E−
|.

Now that v is in some induced diamond in G[U ], we can find a maximal clique K of G
containing three of its vertices. Since K 6= U and |K ∩ U | ≥ 3, it cannot induce a maximal
clique of G∗ . Hence by Lemma 4(ii), it is small. This concludes the proof of the lemma. J
After delimiting the ends of the edges added by a minimum solution, we then turn to the
ends of those edges deleted by a minimum solution.
I Lemma 8. Let E± be a minimum solution to a reduced instance (G, k), and let K be a
maximal clique of type ii in G. If E+ contains neither (i) an edge between K and a neighbor
of K, nor (ii) two edges between K and the same vertex in V (G) \ K, then K remains a
maximal clique (of type ii) in G4E± .
Proof. Let G∗ = G4E± . Since K is a type-ii maximal clique of G, each vertex v ∈ V (G) \ K
has at most one neighbor in K. By the assumption that E+ contains neither (i) nor (ii),
this remains true in G + E+ and G∗ . On the other hand, E− cannot contain edges of G[K];
otherwise, by Proposition 6, G∗ remains diamond-free after replacing G∗ [K] by G[K], which
implies a strictly smaller solution than E± . Therefore, K is a maximal clique in G∗ .
J
The next corollary follows from Lemma 7 and Lemma 8.
I Corollary 9. Let E± be a minimum solution to a reduced instance (G, k), and let K be
a maximal clique of G containing both ends of an edge in E− . Then either K ∈ Ks (G), or
K ∈ K2 (G) and K intersects one clique in Ks (G).

v0

v1

v2

v7
v4

u1

u3
u2

v5

v8
v9

v3
u4

v6

Figure 2 An example with k = 4, of which a minimum solution is {+u2 v2 , −u1 v2 , −v0 v1 , −u3 v9 }.
(Note that u1 v2 and v0 v1 are not in any diamond of G.) It has six maximal cliques, K1 =
{v0 , v1 , v2 , u1 }, K2 = {v2 , v3 , v4 , v5 , v6 }, K3 = {u2 , v3 , v4 , v5 , v6 }, K4 = {u3 , v7 , v8 }, K5 =
{u3 , u4 , v9 }, while K6 comprises of u1 , u2 , u3 , u4 and other ten unlabeled vertices. Four of these
maximal cliques, K2 , K3 , K5 , and K6 , are of type i, of which only K6 is big, the other two of type
ii. All 14 labeled vertices are vulnerable, and the other 8 unlabeled vertices are guarded.

Lemma 7 and Corollary 9 motivate the following definition. We say that a vertex v is
vulnerable in graph G if (1) there exists some K ∈ Ks (G) containing v; or (2) there are
intersecting maximal cliques K1 ∈ Ks (G) and K2 ∈ K2 (G) such that v ∈ K2 . A vertex
is guarded if it is not vulnerable. Lemma 7 and Corollary 9 can be summarized as: No
(non-)edge in a minimum solution can be incident to a guarded vertex. See Figure 2 for an
illustration.

Cao, Rai, Sandeep, Ye

3

23:9

The kernel

We partition the vertex set of a reduced graph into five parts, and deal with them separately.
(i) vertices in small maximal cliques of type i (all of them are vulnerable);
(ii) vulnerable vertices in big maximal cliques of type i but not in the previous part;
(iii) other vulnerable vertices (not in any maximal cliques of type i);
(iv) guarded vertices in (big) maximal cliques of type i; and
(v) other guarded vertices (not in any maximal cliques of type i).
Note that for this purpose we do not need to enumerate the maximal cliques. The key
observation is that we can easily find all cross edges by enumeration, from which we can
identify all vertices and edges in maximal cliques of type i. We use the procedure partition
presented in Figure 3, which computes this partition in three steps: It first finds all vertices
in a maximal clique of type i, from which it identifies those in a small maximal clique of type
i, and finally use them to get all vulnerable vertices.
Input: a reduced instance (G, k).
Output: vertices in the five parts have (i) mark “small,” (ii) marks “vulnerable” and
“type i,” (iii) mark “vulnerable,” (iv) mark “type i,” and (v) no mark, respectively.
1. for each edge uv ∈ E(G) where N (u) ∩ N (v) does not induce a clique do
1.1. mark uv “cross edge”;
1.2. mark u, v and all vertices in N (u) ∩ N (v) as “type i”;
1.3. mark all edges between these vertices as “type i”;
\\a vertex is in a maximal clique of type i if and only if it’s marked “type i.”
2. for each marked vertex v do
2.1. if N (v) does not induce a cluster (a disjoint union of cliques) do mark v as “small”;
2.2. else if a clique in N (v) of size ≤ 3k contains a cross edge do mark v as “small”;
3. for each unmarked edge uv ∈ E(G) do
3.1. find the maximal clique K containing u and v;
3.2. if K contains any vertex marked “small” then mark all vertices in K “vulnerable”;
3.3. mark every edge in K “checked.”

Figure 3 The procedure parittion.

It is easy to check that procedure partition runs in polynomial time. We now show its
correctness.
I Lemma 10. Procedure partition is correct.
Proof. We start from proving a simple property:
A maximal clique K is of type i if and only if it contains
both ends of the cross edge of a diamond.

(\)

Consider first the “only if” direction. By definition, there exists another maximal clique
K 0 such that |K ∩ K 0 | ≥ 2. We can find two vertices u, v ∈ K ∩ K 0 ; while by the maximality
of K and K 0 , we can find x ∈ K \ K 0 and y ∈ K 0 \ K. These four vertices induce a diamond
with cross edge uv. Consider then the “if” direction. Let uv be a cross edge of a diamond
such that u, v ∈ K, and let x, y be the other vertices of the diamond. We can find two
maximal cliques containing u, v, x and u, v, y respectively. They are different and hence at
least one is different from K. Therefore, K is of type i.

CVIT 2016

23:10

A Polynomial Kernel for Diamond-Free Editing

An edge uv ∈ E(G) is a cross edge if and only if N (u) ∩ N (v) does not induce a clique;
this justifies step 1.1. Steps 1.2 and 1.3 follow from property (\).
Step 2 considers all vertices in maximal cliques of type i. If some component of G[N (v)]
is not a clique, we can find a path xyz of length two. There are two different maximal cliques
containing v, x, y and v, y, z respectively. Both are of type i, and hence by Lemma 4(i), at
least one of them is small. Step 2.2 also follows from property (\). If a vertex v is not marked
in step 2, then every maximal clique containing v is either big or of type ii. Therefore, all
vertices in maximal cliques of type i have been correctly identified in step 2.
Step 3 finds other vulnerable vertices. By definition, such a vertex is in some maximal
clique of type ii. If a type-ii maximal clique consists of an isolated vertex, it is guarded and
not marked in step 3. We may hence consider only nontrivial maximal cliques. All edges in
a type-ii maximal clique remain unmarked. Note that any two vertices of a type-ii maximal
clique determines this clique: It is the only maximal clique that contains these two vertices.
Vertices in the clique are vulnerable if and only if it contains a vertex marked “small.” We
only need to check the clique K once, so we mark them to avoid unnecessary repetition in
step 3.3. After step 3, all type-ii maximal cliques have been checked, and the algorithm is
complete.
J

3.1

Maximal cliques of type i

We start from the vertices that are in some small type-i maximal cliques of G; let them
S
be denoted by S(G), i.e., S(G) =
K. Noting that the final graph has no small
K∈Ks (G)

type-i maximal cliques, we can bound the size of S(G) by the number of decrements of S(G)
induced by each edge addition or deletion.
I Lemma 11. Let (G, k) be a reduced yes-instance. For any added edge uv in a solution of
(G, k), at most 3k + 2 vertices in some induced diamond of G become vertices in no induced
diamond of G + uv.
Proof. Let x be such a vertex, i.e., a vertex in some diamond of G but not in any diamond of
G + uv. Then uv is the missing edge of all diamonds containing x in G. Hence x is either one
of u, v or in N (u) ∩ N (v). By Proposition 3, we have |N (u) ∩ N (v)| ≤ 3k, which concludes
the proof.
J
I Lemma 12. Let (G, k) be a reduced yes-instance. For any deleted edge uv in a solution of
(G, k),
(i) at most 6k type-i maximal cliques of G become type-ii maximal cliques of G − uv, and
(ii) |S(G)| − |S(G − uv)| ≤ 18k 2 + 2.
Proof. Let K be the set of type-i maximal cliques of G that become type-ii maximal cliques
of G − uv. Consider any clique K ∈ K. By definition, there is another (type-i) maximal
clique K 0 of G such that |K ∩ K 0 | ≥ 2. Clearly, both u, v ∈ K 0 , and precisely one of them is
in K. Assume without loss of generality u ∈ K. Note that both K 0 \ {u} and K 0 \ {v} are
(not necessarily maximal) cliques of G − uv. Since K becomes a type-ii maximal clique in
G − uv, we must have |K 0 | = 3 and |K ∩ K 0 | = 2. By Proposition 3, |N (u) ∩ N (v)| ≤ 3k.
Every clique in K contains one of u and v, and one vertex from N (u) ∩ N (v). Therefore,
|K| ≤ 6k.
Now we prove the second assertion. From assertion (i) it can be inferred that there are
at most 6k · (3k − 1) = 18k 2 − 6k vertices in S(G) \ S(G − uv) which are not part of any
maximal clique containig uv in G. If a vertex x is part of maximal clique containing uv such

Cao, Rai, Sandeep, Ye

23:11

that x ∈ S(G) \ S(G − uv), then x must be either u, or v or a common neighbor of u and v.
Since |N (u) ∩ N (v)| ≤ 3k by Proposition 3, we obtain that there are at most 3k + 2 such
vertices. It follows that S(G) \ S(G − uv) ≤ 18k 2 − 6k + 3k + 2 ≤ 18k 2 + 2.
J
Since there are at most k edges added or deleted, by Lemma 11 and Lemma 12, we have
an upper bound for |S(G)|.
I Corollary 13. If (G, k) is a reduced yes-instance, then |S(G)| ≤ 18k 3 + 2k.
The next are the big maximal cliques of type i. By Lemma 4(ii), a clique in Kb (G)
remains a maximal clique after a minimum solution is applied to G. We bound first the
number of big type-i maximal cliques.
I Lemma 14. If (G, k) is a reduced yes-instance, then Kb (G) ≤ 6k 2 .
Proof. By Lemma 4, the only way to make a big maximal clique of type i become type ii is
deleting edges outside it. Together with Lemma 12(i), Kb (G) has at most 6k 2 cliques.
J
To bound the number of vertices in big type-i maximal cliques, it suffices to bound their
sizes, for which we introduce another reduction rule.
I Rule 3. Let K ∈ Kb (G) with |K| ≥ 3k + 3. If K contains a guarded vertex x that does
not occur in any other type-i maximal clique of G, delete it.
I Lemma 15. Rule 3 is safe: (G, k) is a yes-instance if and only if (G−x, k) is a yes-instance.
Proof. Every solution of (G, k) confined to G − x is a solution of (G − x, k). For the “if”
direction, let E± be a minimum solution of (G − x, k), and let G∗ = G4E± . Note that
(G − x)4E± = G∗ − x, and it is diamond-free. No edge in E± is incident to x, and hence
NG (x) = NG∗ (x), which we simply denote by N (x). By Proposition 5, it suffices to prove
that each maximal clique of G∗ containing x is of type ii. For this purpose, we show that
each component of G[N (x)] is either a single vertex or a type-ii maximal clique in G∗ − x.
Note that K \ {x} is a big maximal clique in G − x: It is a clique of size at least 3k + 2,
and its maximality follows from Lemma 4(i). Hence, by Lemma 4(ii), K \ {x} is a maximal
clique (of type ii) in G∗ − x. Since x is a guarded vertex that does not occur in any other
type-i maximal clique, every other maximal clique K 0 containing x in G is of type ii, and it
cannot intersect any small type-i maximal clique. Therefore, by Lemma 7, no edge added by
E+ can be incident to any vertex in N (x). From Lemma 8 we can conclude that K 0 \ {x}
either contains only a vertex or is a maximal clique (of type ii) in G∗ − x.
Since no edge added by E+ is between two vertices in N (x) and since x is a guarded
vertex, each component of G[N (x)] is either K \ {x} or K 0 \ {x}, hence is either a single
vertex or a type-ii maximal clique in G∗ − x. This concludes the proof.
J
I Lemma 16. Let (G, k) be a reduced yes-instance. If Rule 3 is not applicable, then for each
K ∈ Kb (G), we have that |K| = O(k 3 ).
Proof. Without loss of generality, assume that |K| ≥ 3k + 3. Since Rule 3 is not applicable,
K does not contain any guarded vertex shared by other big type-i maximal cliques. Thus,
every vertex in K is either a vulnerable vertex, or a guarded vertex in more than one big
type-i maximal clique. Let U1 and U2 be the set of vulnerable vertices in K ∩ S(G) and
K \ S(G) respectively. By the definition, each vertex in U2 is adjacent to some vertex
in S(G) \ U1 by an edge of type-ii maximal clique. For each vertex v ∈ S(G) \ U1 , the
cardinality of U2 ∩ N (v) is at most one; otherwise, there is a type-i maximal clique containing

CVIT 2016

23:12

A Polynomial Kernel for Diamond-Free Editing

U2 ∩ N (v) and v which by Lemma 4(i) is small, contradicting to U2 ⊆ K \ S(G). Therefore,
|U2 | ≤ |S(G) \ U1 |, and by Corollary 13, K contains at most 18k 3 + 2k vulnerable vertices.
By Lemma 4(i), every pair of big type-i maximal cliques shares at most one vertex. Hence, by
Lemma 14, K contains at most 6k 2 guarded vertices that appear in some other big maximal
cliques of type i. Putting them together we get |K| ≤ 18k 3 + 2k + 6k 2 .
J
The next corollary follows immediately from Lemmas 14 and 16.
I Corollary 17. Let (G, k) be a reduced yes-instance. If Rule 3 is not applicable, then the
number of vertices that are contained in some cliques in Kb (G) is O(k 5 ).

3.2

Maximal cliques of type ii

We have bounded the number of vertices in all maximal cliques of type i, and it remains
to bound the number of vertices that occur only in maximal cliques of type ii. Let T (G)
S
denote these vertices, i.e., T (G) = V (G) \
K. It may not be surprising that
K∈Ks (G)∪Kb (G)

we can delete all the guarded vertices in them.
I Rule 4. If there is a guarded vertex x not in any type-i maximal clique of G, delete it.
I Lemma 18. Rule 4 is safe: (G, k) is a yes-instance if and only if (G−x, k) is a yes-instance.
Proof. It is easy to see that every solution of (G, k) confined to G − x is a solution of
(G − x, k). For the other direction, let E± be a minimum solution of (G − x, k), and it is
sufficient to show that x is not part of any diamond in G∗ = G4E± . Note that x is a vertex
which is part of only type-ii maximal cliques in G and not adjacent to any vertex in small
type-i maximal cliques in G. Therefore, by Lemma 7, none of the vertices in N (x) is incident
to any edges of E+ . If x is part of a diamond in G∗ , then it is formed by a deletion of an
edge in G[N [x]] by E− . But this is not possible by Corollary 9, as none of the edges in
G[N [x]] is part of any type-ii maximal clique which intersects with a small type-i maximal
clique in G − x.
J
If Rule 4 is not applicable, then all vertices in T (G) are vulnerable. As demonstrated
in Figure 2, an edge may be deleted from a maximal clique of type ii. In that example,
neither end of the deleted edge v0 v1 is in any maximal clique of type i. This can happen
only after some modification happens in the neighborhood of this vertex—u2 v2 added in the
example. Indeed, we may consider the added/deleted edges stepwise, then there is an order
such that each edge is added/deleted only if it is in some diamond. One modification may
introduce new diamond(s) not in the original graph. For example, neither v0 v1 nor u1 v2 is
in a diamond of G, but the addition of u2 v2 jeopardizes u1 v2 , whose deletion consequently
brings v0 v1 down.
This example is actually exemplary: The only way to bring an edge in a maximal clique
K of type ii to a diamond is through adding edge(s) between K and other vertices. According
to Proposition 2, however, this would not happen when |K| ≥ k + 3. In other words, to make
sure a large clique in K2 (G) is immutable to future modifications, it suffices to keep k + 3 of
its vertices. This motivates the following reduction rule, whose statement is however more
complex than previous ones. The main trouble here is that we are not allowed to delete all
but k + 3 guarded vertices from a clique in K2 (G), because it may be required for another
clique in K2 (G).
For a pair of vertices u, v, we denote by N (u, v) the set of common neighbors of u and v
not in S(G), i.e., N (u, v) = (N (u) ∩ N (v)) \ S(G).

Cao, Rai, Sandeep, Ye

23:13

I Proposition 19. Let u, v be two vertices in G. If uv 6∈ E(G), then N (u, v) form an
independent set. Moreover, if uv ∈ E+ for a solution E± of (G, k), then |N (u, v)| ≤ k.
Proof. If G[N (u, v)] has an edge, say xy, then {u, v, x, y} forms a diamond. There are two
type-i maximal cliques containing {x, y, u} and {x, y, v} respectively. By Lemma 4(i), at
least one of them is small, contradicting to x, y ∈
/ S(G). The second claim follows from
Proposition 2.
J
Our last rule would keep at most k + 1 from such sets. To avoid unnecessary clutters, we
simply say we mark k + 1 vertices in N (u, v), even if its size is smaller than k + 1; in which
case, we mark all of them.
I Rule 5. For each pair of vertices u, v ∈ S(G), arbitrarily mark k + 1 vertices in N (u, v). If
|N (u, v)| ≤ k, then for each vertex w ∈ N (u, v), arbitrarily mark k + 1 vertices in N (u, w)
and k + 1 vertices in N (v, w). If there is an unmarked vertex x in T (G), delete it.
I Lemma 20. Rule 5 is safe: (G, k) is a yes-instance if and only if (G−x, k) is a yes-instance.
Proof. Any solution of (G, k) confined to G − x is a solution of (G − x, k). For the “if”
direction, let E± be a minimum solution of (G − x, k), and let G∗ = G4E± . We show that
each maximal clique of G∗ containing x is a maximal clique of G and is of type ii in G∗ . Since
deleting a vertex not in any type-i maximal clique does not alter type-i maximal cliques, we
have S(G0 ) = S(G).
Let K be a maximal clique of G containing x; note that K is a maximal clique of type ii
in G, as x ∈ T (G). We argue that |NG∗ (y) ∩ K| ≤ 1 for every y ∈ V (G) \ K. Since K is a
maximal clique of type ii in G, we have (1) |NG (y) ∩ K| is either 0 or 1; and (2) for every
pair of vertices u, v ∈ K,
N (u, v) ⊆ NG (u) ∩ NG (v) = K.
Suppose first that there are at least two edges between y and K in E+ . Let u, v ∈ K be
two vertices such that yu, yv ∈ E+ . Then by Lemma 7, u, v ∈ S(G0 ), and hence u, v ∈ S(G).
Clearly, x 6= u, x 6= v and x is an unmarked vertex in N (u, v). Further, there are k + 1
marked vertices in N (u, v). It follows that |K \ {x}| ≥ k + 3, and E− does not have any edge
in G0 [K \ {x}] by Proposition 2(i). Therefore, for each marked vertex z ∈ N (u, v) that is not
adjacent to y, the set {u, v, y, z} induces a diamond in G0 + {yu, yv}. The only edge we can
edit is yz, but |NG (y) ∩ K| ≤ 1, and there are at least k + 2 edges between y and K, which
is impossible.
Hence, at most one edge can be added between y and K by E+ . If |NG (y) ∩ K| = 0, or
|NG (y) ∩ K| = 1 but the only edge between y and K is deleted, then it is trivial that y is
adjacent to at most one vertex of K in G∗ . Suppose that NG∗ (y) ∩ K = {u, v} while only u
is in NG (y); note that yu 6∈ E− and yv ∈ E+ . By Lemma 7, y, v ∈ S(G0 ), and hence in S(G).
According to Proposition 19, there are at most k vertices in N (v, y) in G0 . If u ∈
/ S(G), then
it has been marked; hence x 6= u. Also, x 6= v as x ∈ T (G). By the rule, no matter whether
u is in S(G) or not, we should have marked vertices in N (u, v). Since x ∈ N (u, v) but is not
marked, we have |N (u, v)| > k + 1. Let z be any marked vertex in N (u, v); it is not in NG (y)
by assumption. But then {u, v, y, z} induces a diamond in G0 + yv, in which we have to add
the missing edge yz, which requires |E+ | > k, a contradiction.
We have thus concluded |NG∗ (y)∩K| ≤ 1 for each vertex y in V (G)\K. By Proposition 6,
K \ {x} remains a clique in G∗ − x, otherwise we can find a strictly smaller solution. Then
K is a maximal clique of type ii in G∗ . On the other hand, according to Proposition 19, no

CVIT 2016

23:14

A Polynomial Kernel for Diamond-Free Editing

edge is added between two vertices of NG (x). Therefore, N (x) induces exactly the same
subgraph in G and G∗ . Hence, any maximal clique of G∗ containing x is a maximal clique of
G as well, hence of type ii in G∗ . This concludes the proof of the lemma.
J
Now Theorem 1 follows by counting numbers of different kinds of vertices.
Proof of Theorem 1. We show first that Rules 3–5 can be applied in polynomial time. For
a guarded vertex x, N (x) induces a cluster graph and each maximal clique in the cluster
graph together with x forms the maximal cliques of G containing x. Recall that a maximal
clique is of type i if and only if it contains both ends of a cross edge. Since the procedure
partition finds all guarded vertices (no mark) and cross edges, we can find for each guarded
vertex all type-i maximal cliques and type-ii maximal cliques containing it in polynomial
time. Therefore, both Rules 3 and Rule 4 can be applied in polynomial time. Moreover, the
procedure partition finds all vertices in S(G) (mark “small”) and T (G) (no mark “type
i”), and hence Rule 5 can be applied in polynomial time.
We claim that if none of Rules 3–5 is applicable to a reduced yes-instance (G, k), then
|V (G)| = O(k 8 ). By Corollary 13, the number of vertices in small type-i maximal cliques is
|S(G)| = O(k 3 ). By Corollary 17, we have O(k 5 ) vertices in big type-i maximal cliques. For
each pair of vertices u, v in S(G), we mark at most k + 1 common neighbors of them. And for
each common neighbor w of u, v, we mark at most 2k + 2 vertices: k + 1 vertices in N (u, w)
and k + 1 vertices in N (v, w). Hence |T (G)| = O(k 8 ), and |V (G)| = O(k 3 ) + O(k 5 ) + O(k 8 ) =
O(k 8 )
J

4

A cubic kernel for diamond-free edge deletion

We now present a cubic-vertex kernel for the diamond-free edge deletion problem. Note that
if G − E− is diamond-free, then E− can be viewed as a solution to the diamond-free editing
problem as well, where E+ = ∅. Therefore, most statements, except those on minimum
solutions, also hold for E− . We will need Rule 2 from page 5; for the sake of completeness,
we include it here.
I Rule 1. If there exist an edge uv and 2k + 2 distinct vertices x1 , y1 , . . . , xk+1 , yk+1 in
N (u) ∩ N (v) such that xi yi 6∈ E(G) for all 1 ≤ i ≤ k + 1, then delete uv and decrease k by
one.
The correctness of the following rule is also straightforward.
I Rule 2. Mark an edge uv “permanent” if there are 2k+2 distinct vertices x1 , y1 , . . . , xk+1 , yk+1
in N (u) ∩ N (v) such that xi yi ∈ E(G) for all 1 ≤ i ≤ k + 1. If there exists a diamond
consisting of only permanent edges, return a trivial no-instance.
An instance of the diamond-free edge deletion problem is reduced if neither of Rules 1
and 2 is applicable. Henceforth we are concerned exclusively with reduced instances.
I Proposition 21. Two big maximal cliques of a reduced instance (G, k) share at most one
vertex.
Proof. Each edge in a maximal clique would be marked permanent by Rule 2. Therefore, if
two big maximal cliques share more then one vertex, there is a diamond in them, consisting
of only permanent edges.
J
Again, given any minimal solution E− , we can view the edges as deleted in a sequence,
such each edge is in a diamond when it is deleted. According to Lemma 8, a type-ii maximal
clique would remain so during the course. If a vertex is not in any type-i maximal clique of

Cao, Rai, Sandeep, Ye

23:15

G, then by Proposition 5, no edge incident to it will be deleted. These vertices and edges are
thus irrelevant to the problem; we can actually delete them from the graph.
I Rule 3. Delete all edges and vertices not in any maximal clique of type i.
I Lemma 22. Rule 3 is safe.
Proof. Let G0 be the graph obtained by deleting all edges in type-ii maximal cliques. Note
that a vertex is not in any type-i maximal clique of G if and only if it is isolated in G0 .
Therefore, to show the safeness of Rule 3, it suffices to prove that (G, k) is a yes-instance if
and only if (G0 , k) is a yes-instance.
0
Let E− be a minimum solution of (G, k), and let E−
= E− ∩ E(G0 ). We claim that
0
0
0
G − E− is diamond-free. Suppose for contradiction that G0 − E−
contains a diamond on
0
{x, u, v, y} with cross edge uv. Then xy ∈ E(G)\E(G ), and {x, u, v, y} is a clique in G−E− ,
also in G. The edge xy is not in any type-i maximal clique of G, and hence {x, u, v, y} is a
clique of G, and part of a type-ii maximal clique of G. Hence all edges of this diamond are
in E(G) \ E(G0 ), a contradiction.
0
0
For the other direction, let E−
be a minimum solution of (G0 , k). We claim that G − E−
is
0
diamond-free. Suppose for contradiction that G − E−
contains a diamond on {x, u, v, y} with
cross edge uv. Then at least one of the five edges of the diamond, i.e., {ux, vx, uv, uy, vy}, is
in E(G) \ E(G0 ). Assume without loss of generality that one edge in the triangle on {u, v, x}
belongs to E(G) \ E(G0 ). Then the maximal clique K of G containing u, v, x is of type ii.
Now y is adjacent to at least two vertices of K in G, hence y must be in K as well. But
0
then xy would be in E(G) \ E(G0 ), and hence not in E−
; in other words, xy is an edge in
0
G − E− , a contradiction. This concludes the proof.
J
After the application of Rule 3, all the maximal cliques in the graph are of type i.
I Rule 4. If there is a vertex x not in any small type-i maximal clique, delete it.
I Lemma 23. Rule 4 is safe.
Proof. Let E− be a minimum solution of (G − x, k). We show that G∗ = G − E− is also
diamond-free. Suppose for contradiction that there are maximal cliques K1 and K2 in G∗
such that |K1 ∩ K2 | ≥ 2. At least one of them contains x; assume without loss of generality
x ∈ K1 . Let K be a maximal clique of G containing K1 . By the assumption (x is not in any
small maximal clique), K is big. By Proposition 2(i), no edge in the clique K \ {x} can be
deleted by E− . Hence K = K1 and K2 6⊆ K. By Proposition 21, K2 is small, and x ∈
/ K2 .
We can find a pair of nonadjacent vertices x0 ∈ K \ {{x} ∪ K2 } and y ∈ K2 \ K. If no such
pair of vertices exists, then K2 contains all vertices in K \ {x} and is big, a contradiction.
Let u, v be two vertices in K ∩ K2 . Then {x0 , u, v, y} induces a diamond in G − x and one
of uy, vy has to be deleted by E− , contradicting that K2 is a maximal clique of G∗ . This
concludes the proof of this lemma.
J
It is clear that all the four rules can be applied in polynomial time. Indeed, a simplified
version of procedure partition would suffice.
I Lemma 24. Let (G, k) be a yes-instance of the diamond-free edge deletion problem. If
none of Rules 1–4 is applicable, then |V (G)| = O(k 3 ).
Proof. We claim that if neither of Rules 3 and 4 is applicable to a reduced yes-instance
(G, k), then |V (G)| = O(k 3 ). By Lemma 12, there are at most O(k 3 ) vertices in small type-i
maximal cliques in G. After the exhaustive application of Rule 4, every vertex is in some
small type-i maximal clique. Therefore, G contains O(k 3 ) vertices.
J

CVIT 2016

23:16

A Polynomial Kernel for Diamond-Free Editing

References
1

2

3
4
5

6
7
8
9
10
11

12
13
14
15

16

N. R. Aravind, R. B. Sandeep, and Naveen Sivadasan. Dichotomy results on the hardness of
H-free edge modification problems. SIAM Journal on Discrete Mathematics, 31(1):542–561,
2017.
Ivan Bliznets, Marek Cygan, Pawel Komosa, and Michal Pilipczuk. Hardness of approximation for H-free edge modification problems. In Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, volume 60 of LIPIcs, pages 3:1–3:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2016.
Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary
properties. Information Processing Letter, 58(4):171–176, 1996.
Leizhen Cai and Yufei Cai. Incompressibility of H-free edge modification problems. Algorithmica, 71(3):731–757, 2015.
Yufei Cai. Polynomial kernelisation of H-free edge modification problems. Mphil thesis,
Department of Computer Science and Engineering, The Chinese University of Hong Kong,
Hong Kong SAR, China, 2012.
Yixin Cao and Jianer Chen. Cluster editing: Kernelization based on edge cuts. Algorithmica,
64(1):152–169, 2012.
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.
Undergraduate texts in computer science. Springer, 2013.
Ehab S. El-Mallah and Charles J. Colbourn. The complexity of some edge deletion problems.
IEEE Transactions on Circuits and Systems, 35(3):354–362, 1988.
Paul Erdős and Richard Rado. Intersection theorems for systems of sets. Journal of the
London Mathematical Society, 35(1):85–90, 1960.
Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer, 2006.
Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. On the (non) existence of polynomial kernels for Pl -free edge modification problems. Algorithmica,
65(4):900–926, 2013.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of
Computer and System Sciences, 62(2):367–375, 2001.
Stefan Kratsch and Magnus Wahlström. Two edge modification problems without polynomial kernels. Discrete Optimization, 10(3):193–199, 2013.
John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219–230, 1980.
R. B. Sandeep and Naveen Sivadasan. Parameterized Lower Bound and Improved Kernel for
Diamond-free Edge Deletion. In 10th International Symposium on Parameterized and Exact
Computation, volume 43 of LIPIcs, pages 365–376. Schloss Dagstuhl–Leibniz-Zentrum fuer
Informatik, 2015.
Mihalis Yannakakis. Edge-deletion problems. SIAM Journal on Computing, 10(2):297–309,
1981.

