Theory of Computing Systems manuscript No.
(will be inserted by the editor)

Parameterizing edge modification problems
above lower bounds

arXiv:1512.04047v3 [cs.DM] 23 Dec 2016

René van Bevern · Vincent Froese ·
Christian Komusiewicz

December 26, 2016

Abstract We study the parameterized complexity of a variant of the F-free Editing
problem: Given a graph G and a natural number k, is it possible to modify at most
k edges in G so that the resulting graph contains no induced subgraph isomorphic
to F? In our variant, the input additionally contains a vertex-disjoint packing H of
induced subgraphs of G, which provides a lower bound h(H) on the number of edge
modifications required to transform G into an F-free graph. While earlier works used
the number k as parameter or structural parameters of the input graph G, we consider
instead the parameter ` := k − h(H), that is, the number of edge modifications above
the lower bound h(H). We develop a framework of generic data reduction rules to
show fixed-parameter tractability with respect to ` for K3 -Free Editing, Feedback Arc
Set in Tournaments, and Cluster Editing when the packing H contains subgraphs
with bounded solution size. For K3 -Free Editing, we also prove NP-hardness in case
of edge-disjoint packings of K3 s and ` = 0, while for Kq -Free Editing and q ≥ 6,
NP-hardness for ` = 0 even holds for vertex-disjoint packings of Kq s. In addition, we
provide NP-hardness results for F-free Vertex Deletion, were the aim is to delete a
minimum number of vertices to make the input graph F-free.
An extended abstract of this article appeared in Proceedings of the 11th International Computer Science
Symposium in Russia, June 9–13, 2016, St. Petersburg, Russian Federation [6].
René van Bevern is supported by grant 16-31-60007 mol_a_dk of the Russian Foundation for Basic
Research.
Christian Komusiewicz is supported by grant KO 3669/4-1 of Deutsche Forschungsgemeinschaft.
René van Bevern
Novosibirsk State University, Novosibirsk, Russian Federation, E-mail: rvb@nsu.ru
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk,
Russian Federation
Vincent Froese
Technische Universität Berlin, Germany, E-mail: vincent.froese@tu-berlin.de
Christian Komusiewicz
Friedrich-Schiller-Universität Jena, Germany, E-mail: christian.komusiewicz@uni-jena.de

Keywords. NP-hard problem, fixed-parameter algorithm, subgraph packing, kernelization, graph-based clustering, feedback arc set, cluster editing

1 Introduction
Graph modification problems are a core topic of algorithmic research [10, 34, 47].
Given a graph G, the aim is to transform G by a minimum number of modifications
(like vertex deletions, edge deletions, or edge insertions) into another graph G0 fulfilling certain properties. Particularly well-studied are hereditary graph properties, which
are closed under vertex deletions and are characterized by minimal forbidden induced
subgraphs: a graph fulfills such a property if and only if it does not contain a graph F
from a property-specific family F of graphs as induced subgraph. All nontrivial vertex
deletion problems and many edge modification and deletion problems for establishing
hereditary graph properties are NP-complete [1, 3, 33, 34, 47]. One approach to cope
with the NP-hardness of these problems are fixed-parameter algorithms that solve
them in f (k) · nO(1) time for some exponential function f depending only on some
desirably small parameter k. If the desired graph property has a finite forbidden induced subgraph characterization, then the corresponding vertex deletion, edge deletion,
and edge modification problems are fixed-parameter tractable parameterized by the
number of modifications k, that is, solvable in f (k) · nO(1) time [10].
Parameterization above lower bounds. When combined with data reduction and
pruning rules, search-tree based fixed-parameter algorithms for the parameter k of
allowed modifications can yield competitive problem solvers [26, 38]. Nevertheless,
the number of modifications is often too large and smaller parameters are desirable.
A natural approach to obtain smaller parameters is “parameterization above guaranteed values” [13, 22, 36, 37]. The idea is to use a lower bound h on the solution size
and to use ` := k − h as parameter instead of k. This idea has been applied successfully
to Vertex Cover, the problem of finding at most k vertices such that their deletion
removes all edges (that is, all K2 s) from G. Since the size of a smallest vertex cover
is large in many input graphs, parameterizations above the lower bounds “size of a
maximum matching M in the input graph” and “optimum value L of the LP relaxation
of the standard ILP-formulation of Vertex Cover” have been considered. After a
series of improvements [13, 22, 36, 43], the current best running time is 3` · nO(1) ,
where ` := k − (2 · L − |M|) [22].
We extend this approach to edge modification problems, where the number k of
modifications tends to be even larger than for vertex deletion problems. For example, in the case of Cluster Editing, which asks to destroy induced paths on three
vertices by edge modifications, the number of modifications is often larger than the
number of vertices in the input graph [8]. Hence, parameterization above lower bounds
seems natural and even more relevant for edge modification problems. Somewhat
surprisingly, this approach has not been considered so far. We thus initiate research on
parameterization above lower bounds in this context. As a starting point, we focus on
edge modification problems for graph properties that are characterized by one small
forbidden induced subgraph F:
2

Problem 1.1 (F-free Editing)
Input: A graph G = (V, E) and a natural number
V  k.
Question: Is there an F-free editing set S ⊆ 2 of size at most k such that G4S :=
(V, (E \ S ) ∪ (S \ E)) does not contain F as induced subgraph?
In the context of a concrete variant of F-free Editing, we refer to an F-free editing set
as solution and call a solution optimal if it has minimum size.
Lower bounds from packings of bounded-cost induced subgraphs. Following the
approach of parameterizing Vertex Cover above the size of a maximum matching,
we can parameterize F-free Editing above a lower bound obtained from packings of
induced subgraphs containing F.
Definition 1.2 A vertex-disjoint (or edge-disjoint) packing of induced subgraphs of a
graph G is a set H = {H1 , . . . , Hz } such that each Hi is an induced subgraph of G and
such that the vertex sets (or edge sets) of the Hi are mutually disjoint.
While it is natural to consider packings of F-graphs to obtain a lower bound on the
solution size, a packing of other graphs that contain F as induced subgraph might
yield better lower bounds and thus a smaller parameter above this lower bound. For
example, a K4 contains several triangles and two edge deletions are necessary to
make it triangle-free. Thus, if a graph G has a vertex-disjoint packing of h3 triangles
and h4 K4 s, then at least h3 + 2 · h4 edge deletions are necessary to make it trianglefree.1 Moreover, when allowing arbitrary graphs for the packing, the lower bounds
provided by vertex-disjoint packings can be better than the lower bounds provided by
edge-disjoint packings of F. A disjoint union of h K4 s, for example, has h edge-disjoint
triangles but also h vertex-disjoint K4 s. Hence, the lower bound provided by packing
vertex-disjoint K4 s is twice as large as the one provided by packing edge-disjoint
triangles in this graph.
Motivated by this benefit of vertex-disjoint packings of arbitrary graphs, we mainly
consider lower bounds obtained from vertex-disjoint packings, which we assume to
receive as input. Thus, we arrive at the following problem, where τ(G) denotes the
minimum size of an F-free editing set for a graph G:
Problem 1.3 (F-free Editing with Cost-t Packing)
Input: A graph G = (V, E), a vertex-disjoint packing H of induced subgraphs of G
such that 1 ≤ τ(H) ≤ t for each H ∈ H, and
 a natural number k.
Question: Is there an F-free editing set S ⊆ V2 of size at most k such that G4S :=
(V, (E \ S ) ∪ (S \ E)) does not contain F as induced subgraph?
The special case of F-free Editing with Cost-t Packing where only F-graphs are
allowed in the packing is called F-free Editing with F-Packing.
P
From the packing H, we obtain the lower bound h(H) := H∈H τ(H) on the size
of an F-free editing set, which allows us to use the excess ` := k − h(H) over this
lower bound as parameter, as illustrated in Figure 1.1. Since F is a fixed graph, we
1 Bounds of this type are exploited, for example, in so-called cutting planes, which are used in speeding
up the running time of ILP solvers.

3

Fig. 1.1 An instance of Triangle Deletion. The packing graphs have gray background. Left: A vertexdisjoint packing of two triangles giving ` = 1. Right: A vertex-disjoint packing of a triangle and a K4
giving ` = 0. The solution consists of the three dashed edges.

can compute the bound h(H) in f (t) · |G|O(1) time using the generic algorithm [10]
mentioned in the introduction for each H ∈ H. In the same time we can also verify
whether the cost-t property is fulfilled.
Packings of forbidden induced subgraphs have been used in implementations of
fixed-parameter algorithms to prune the corresponding search trees tremendously [26].
By showing fixed-parameter algorithms for parameters above these lower bounds, we
hope to explain the fact that these packings help in obtaining fast algorithms.
Our Results. We first state the negative results since they justify the focus on concrete
problems and, to a certain extent, also the focus on parameterizing edge modification
problems above lower bounds obtained from vertex-disjoint packings. We show that
K6 -free Editing with K6 -Packing is NP-hard for ` = 0. This proves, in particular, that
a general fixed-parameter tractability result as it is known for the parameter k [10]
cannot be expected. Moreover, we show that, if F is a triangle and H is an edgedisjoint packing of h triangles in a graph G, then it is NP-hard to decide whether G
has a triangle deletion set of size h (that is, ` = 0). Thus, parameterization by ` is
hopeless for this packing lower bound. We also consider vertex deletion problems. For
these we show that extending the parameterization “above maximum matching” for
Vertex Cover to d-Hitting Set in a natural way leads to intractable problems. This is
achieved by showing that, for all q ≥ 3, Pq -free Vertex Deletion with Pq -Packing is
NP-hard even if ` = 0.
Our positive results are fixed-parameter algorithms and problem kernels (a notion
for provably effective polynomial-time data reduction, see Section 2 for a formal
definition) for three variants of F-free Editing with Cost-t Packing. Namely, these
are the variants in which F is a triangle (that is, a K3 ) or a path on three vertices (that
is, a P3 ). The first case is known as Triangle Deletion, the second one as Cluster
Editing. We also consider the case in which the input is a tournament graph and F is a
directed cycle on three vertices. This is known as Feedback Arc Set in Tournaments.
Using a general approach described in Section 3, we obtain fixed-parameter algorithms
for these variants of F-free Editing with Cost-t Packing parameterized by t and `. This
implies fixed-parameter tractability for F-free Editing with F-Packing parameterized
by `. Specifically, we obtain the following positive results:
(i) For Triangle Deletion, we show an O((2t + 3)` · (nm + n · 2.076t ))-time algorithm
and an O(t · `)-vertex problem kernel for cost-t packings.
√
(ii) For Feedback Arc Set in Tournaments, we show a 2O( (2t+1)`) · nO(1) -time algorithm and an O(t · `)-vertex problem kernel for cost-t packings.
4

(iii) For Cluster Editing, we show an O(1.62(2t+1)·` + nm + n · 1.62t )-time algorithm
and an O(t · `)-vertex kernel for cost-t packings, and a 4` · nO(1) -time algorithm
for P3 -packings.
For the kernelization results, we need to assume that t ∈ O(log n) to guarantee polynomial running time of the data reduction.
Organization of this work. In Section 2, we introduce basic graph-theoretic notation
and formally define fixed-parameter algorithms and problem kernelization. In Section 3, we present the general approach used in our algorithmic and data reduction
results. In Section 4, we present our results regarding Triangle Deletion, in Section 5
regarding Feedback Arc Set in Tournaments, and in Section 6 regarding Cluster
Editing. Section 7 shows vertex and edge deletion problems that remain NP-hard
for ` = 0, where ` is the number of modifications that are allowed in addition to a
lower bound based on vertex-disjoint packings. We conclude with some open questions
in Section 8.
2 Preliminaries
In this section, we introduce basic graph-theoretic notation and formally define fixedparameter algorithms and problem kernelization.
Notation. Unless stated otherwise, we consider undirected, simple,
 finite graphs G =
(V, E), with a vertex set V(G) := V and an edge set E(G) := E ⊆ V2 := {{u, v} | u, v ∈
V ∧ u , v}. Let n := |V(G)|
denote the order of the graph and m := |E(G)| its number

of edges. A set S ⊆ V2 is an edge modification set for G. For an edge modification
set S for G, let G4S := (V, (E \ S ) ∪ (S \ E)) denote the graph obtained by applying S
to G. If S ⊆ E, then S is called an edge deletion set and we write G \ S instead of G4S .
The open neighborhood of a vertex v ∈ V is defined
as NG (v) := {u ∈ V | {u, v} ∈ E}.
0
Also, for V 0 ⊆ V, let G[V 0 ] := (V 0 , E ∩ V2 ) denote the subgraph of G induced
by V 0 . A directed graph (or digraph) G = (V, A) consists of a vertex set V(G) and
an arc set A(G) := A ⊆ {(u, v) ∈ V 2 | u , v}. A tournament on n vertices is a
directed graph (V, A) with |V| = n such that, for each pair of distinct vertices u and v,
either (u, v) ∈ A or (v, u) ∈ A.
Fixed-parameter algorithms. The idea in fixed-parameter algorithms is to accept the
exponential running time that seems to be inevitable when exactly solving NP-hard
problems, yet to confine it to some small problem-specific parameter. A problem is
fixed-parameter tractable with respect to some parameter k if there is a fixed-parameter
algorithm solving any instance of size n in f (k) · nO(1) time. We will also say that a
problem is fixed-parameter tractable with respect to some combined parameter “k and `”
or “(k, `)” if it is fixed-parameter tractable parameterized by k + `.
Fixed-parameter algorithms can efficiently solve instances in which the parameter k
is small, even if the input size n is large. All vertex deletion, edge deletion, and
edge modification problems for graph properties characterized by finite forbidden
induced subgraphs are fixed-parameter tractable parameterized by the number of
modifications k [10].
5

Problem kernelization. An important technique in fixed-parameter algorithmics is
(problem) kernelization [31]—a formal approach of describing efficient and correct
data reduction. A kernelization is an algorithm that given an instance x with parameter k, yields an instance x0 with parameter k0 in time polynomial in |x| + k such that
(x, k) is a yes-instance if and only if (x0 , k0 ) is a yes-instance, and if both |x0 | and k0
are bounded by some functions g and g0 in k, respectively. The function g is referred
to as the size of the problem kernel (x0 , k0 ). Kernelizations are commonly described
by giving a set of data reduction rules which when applied to an instance x of a
problem yield an instance x0 . We say that a data reduction rule is correct if x and x0
are equivalent.
All vertex deletion problems for establishing graph properties characterized by a
finite number of forbidden induced subgraphs have a problem kernel of size polynomial
in the parameter k of allowed modifications [30]. In contrast, many variants of F-free
Editing do not admit a problem kernel whose size is polynomial in k [11, 24, 32].

3 General Approach
In this section, we describe the general approach of our fixed-parameter algorithms.
Recall that τ(H) is the minimum number of edge modifications required to transform
a graph H into an F-free graph. We present fixed-parameter algorithms for three
variants of F-free Editing with Cost-t Packing parameterized by the combination of t
P
and ` := k − h(H), where h(H) := H∈H τ(H). The idea behind the algorithms is to
arrive at a classic win-win scenario [17] where we can either apply data reduction or
show that the packing size |H| is bounded. This will allow us to bound k in t · ` for
yes-instances and, thus, to apply known fixed-parameter algorithms for the parameter k
to obtain fixed-parameter tractability results for (t, `).
More precisely, we show that, for each induced subgraph H of G in a given
packing H, we face essentially two situations. If there is an optimal solution for H
that is a subset of an optimal solution for G, then we can apply a data reduction rule.
Otherwise, we find a certificate witnessing that H itself needs to be solved suboptimally
or that a vertex pair containing exactly one vertex from H needs to be modified. We
use the following terminology for these pairs.
Definition 3.1 (External vertex pairs and edges) A vertex pair {u, v} is an external
pair for a packing graph H ∈ H if exactly one of u or v is in V(H), an edge is an
external edge for H ∈ H if exactly one of its endpoints is in H.
Observe that every pair or edge is an external pair or edge for at most two packing
graphs since the packing graphs are vertex-disjoint. Therefore, the modification of an
external vertex pair can destroy at most two certificates. This is the main fact used in
the proof of the following bound on `.
Lemma 3.2 Let (G, H, k) be an instance of F-free Editing with Cost-t Packing and
let S be a size-k solution that contains, for each H = (W, F) ∈ H,
 
(a) at least τ(H) + 1 vertex pairs from W2 , or
(b) at least one external vertex pair {v, w} for H.
6

Then, |H| ≤ 2` and thus, k ≤ (2t + 1)`.
Proof Denote by Ha ⊆ H the set of all graphs in H that fulfill property (a) and let
pa := |Ha |. Let Hb := H \ Ha denote the set containing the remaining packing graphs
(fulfilling property (b)) and let pb := |Hb |. Thus, |H| = pa + pb . Furthermore, let
P
ha := H∈Ha τ(H) denote the lower bound obtained from the graphs in Ha and let
hb := h(H) − ha denote the part of the lower bound obtained by the remaining graphs.
The packing graphs in Ha cause ha + pa edge modifications inside of them.
Similarly, the packing graphs in Hb cause at least hb edge modifications inside of
them, and each packing graph H ∈ Hb additionally causes modification of at least
one external vertex pair for H. Since every vertex pair is an external pair for at most
two different packing graphs, at least hb + pb /2 edge modifications are caused by the
graphs in Hb . This implies that
k ≥ ha + hb + pa + pb /2
⇔
⇔

k − h(H) ≥ pa + pb /2
2` ≥ 2pa + pb ≥ |H|.

Consequently, k = ` + h(H) ≤ ` + t · |H| ≤ ` + t · 2` = (2t + 1)` .

t
u

4 Triangle Deletion
In this section, we study Triangle Deletion, the problem of destroying all triangles (K3 s) in a graph by at most k edge deletions. In Section 4.1, we apply our
framework from Section 3 to show that Triangle Deletion is fixed-parameter tractable
parameterized above the lower bound given by a cost-t packing. In Section 4.2, we
then show that parameterization above a lower bound given by edge-disjoint packings
of triangles does not lead to fixed-parameter algorithms unless P = NP.
4.1 A fixed-parameter algorithm for vertex-disjoint cost-t packings
Before presenting our new fixed-parameter tractability results for Triangle Deletion,
let us first summarize the known results concerning the (parameterized) complexity
of Triangle Deletion. Triangle Deletion is NP-complete [47]. It allows for a trivial
reduction to 3-Hitting Set since edge deletions do not create new triangles [23].
Combining this approach with the currently fastest known algorithms for 3-Hitting
Set [5, 46] gives an algorithm for Triangle Deletion with running time O(2.076k +nm).
Finally, Triangle Deletion admits a problem kernel with at most 6k vertices [9]. We
show that Triangle Deletion with Cost-t Packing is fixed-parameter tractable with
respect to the combination of t and ` := k − h(H). More precisely, we obtain a
kernelization and a search tree algorithm. Both make crucial use of the following
generic reduction rule for Triangle Deletion with Cost-t Packing.
Reduction Rule 4.1 If there is an induced subgraph H ∈ H and a set T ⊆ E(H)
of τ(H) edges such that deleting T destroys all triangles of G that contain edges of H,
then delete T from G, H from H and decrease k by τ(H).
7

Lemma 4.2 Reduction Rule 4.1 is correct.
Proof Let (G, H, k) be the instance to which Reduction Rule 4.1 is applied and let
(G0 , H \ {H}, k − τ(H)) with G0 := G \ T be the result. We show that (G, H, k) is a
yes-instance if and only if (G0 , H \ {H}, k − τ(H)) is.
First, let S be a solution of size at most k for (G, H, k). Let S H := S ∩ E(H)
denote the set of edges of S that destroy all triangles in H. By definition, |S H | ≥ τ(H).
Since S H ⊆ E(H), only triangles containing at least one edge of H are destroyed by
deleting S H . It follows that the set of triangles destroyed by S H is a subset of the
triangles destroyed by T . Hence, (S \ S H ) ∪ T has size at most k and clearly is a
solution for (G, H, k) that contains all edges of T . Thus, (S \ S H ) is a solution of
size k − τ(H) for G \ T = G0 and (G0 , H \ {H}, k − τ(H)) is a yes-instance.
For the converse direction, let S 0 be a solution of size at most k − τ(H) for (G0 , H \
{H}, k − τ(H)). Since T ⊆ E(H), it holds that every triangle contained in G that does
not contain any edge of H is also a triangle in G0 . Thus, S 0 is a set of edges whose
deletion in G destroys all triangles that do not contain any edge of H. Since T destroys
all triangles containing an edge of H, we have that T ∪ S 0 is a solution for G. Its size
is k.
t
u
We now show that, if Reduction Rule 4.1 is not applicable to H, then we can find a
certificate for this, which will allow us later to branch efficiently on the destruction of
triangles:
Definition 4.3 (Certificate) A certificate for inapplicability of Reduction Rule 4.1 to
an induced subgraph H ∈ H is a set T of triangles in G, each containing exactly one
distinct edge of H, such that |T | = τ(H) + 1 or |T | ≤ τ(H) and τ(H 0 ) > τ(H) − |T |,
where H 0 is the subgraph obtained from H by deleting, for each triangle in T , its edge
shared with H.
Lemma 4.4 Let Γ(G, k) be the time needed to compute a triangle-free deletion set of
size at most k in a graph G if it exists.
P
In O(nm + H∈H Γ(H, t)) time, we can apply Reduction Rule 4.1 to all H ∈ H
and output a certificate T if Reduction Rule 4.1 is inapplicable to some H ∈ H.
In the statement of the lemma, we assume that Γ is monotonically nondecreasing in
the size of G and in k. As described above, currently O(2.076k + |V(G)| · |E(G)|) is the
best known bound for Γ(G, k).
Proof (of Lemma 4.4) First, in O(nm) time, we compute for all H ∈ H all triangles T
that contain exactly one edge e ∈ E(H). These edges are labeled in each H ∈ H. Then,
for each H ∈ H, in Γ(H, t) time we determine the size τ(H) of an optimal triangle-free
deletion set for H. Let t0 denote the number of labeled edges of H.
Case 1: t0 > τ(H). In this case, we return as certificate τ(H) + 1 triangles of T ,
each containing a distinct of τ(H) + 1 arbitrary labeled edges.
Case 2: t0 ≤ τ(H). Let H 0 denote the graph obtained from H by deleting the
labeled edges. All triangles of G that contain at least one edge of H either contain a
labeled edge or they are contained in H 0 . Thus, we now determine in Γ(H 0 , τ(H) − t0 )
time whether H 0 can be made triangle-free by τ(H) − t0 edge deletions. If this is the
8

case, then the rule applies and the set T consists of the solution for H 0 plus the deleted
labeled edges. Otherwise, destroying all triangles that contain exactly one edge from H
leads to a solution which needs more than τ(H) edge deletions and thus the rule does
not apply. In this case, we return the certificate T for this H ∈ H.
The overall running time now follows from the monotonicity of f , from the fact
that |H| ≤ n, and from the fact that one pass over H is sufficient since deleting
edges in each H does not produce new triangles and does not destroy triangles in
any H 0 , H.
t
u
Observe that Reduction Rule 4.1 never increases the parameter ` since we decrease
both k as well as the lower bound h(H) by τ(H). After application of Reduction
Rule 4.1, we can upper-bound the solution size k in terms of t and `, which allows
us to transfer parameterized complexity results for the parameter k to the combined
parameter (t, `).
Lemma 4.5 Let (G, H, k) be a yes-instance of Triangle Deletion with Cost-t Packing
such that Reduction Rule 4.1 is inapplicable. Then, k ≤ (2t + 1)`.
Proof Since (G, H, k) is reduced with respect to Reduction Rule 4.1, for each graph H =
(W, F) in H, there is a set of edges between W and V \ W witnessing that every optimal
solution for H does not destroy all triangles containing at least one edge from H.
Consider any optimal solution S . For each graph H ∈ H, there are two possibilities:
Either at least τ(H) + 1 edges inside H are deleted by S , or at least one external
edge of H is deleted by S . Therefore, S fulfills the condition of Lemma 3.2 and
thus k ≤ (2t + 1)`.
t
u
Theorem 4.6 Let Γ(G, k) be the time used for computing a triangle-free deletion set
of size at most k in a graph G if it exists. Then, Triangle Deletion with Cost-t Packing
P
(i) can be solved in O((2t + 3)` · (nm + H∈H Γ(H, t))) time, and
(ii) admits a problem kernel with at most (12t + 6)` vertices that can be computed in
P
O(nm + H∈H Γ(H, t)) time.
Proof We first prove (ii). To this end, let (G = (V, E), H, k) be the input instance.
P
First, compute in O(nm + H∈H Γ(H, t)) time an instance that is reduced with respect
to Reduction Rule 4.1. Afterwards, by Lemma 4.5, we can reject if k > (2t + 1)`.
Otherwise, we apply the known kernelization algorithm for Triangle Deletion
√ to
the instance (G, k) (that is, without H). This kernelization produces in O(m m) =
O(nm) time a problem kernel (G0 , k0 ) with at most 6k ≤ (12t + 6)` vertices and
with k0 ≤ k [9]. Adding an empty packing gives an equivalent instance (G0 , ∅, k0 ) with
parameter `0 = k0 ≤ (2t + 1)` of Triangle Deletion with Cost-t Packing.
It remains to prove (i). To this end, first apply Reduction Rule 4.1 exhaustively
in O(nm + n · Γ(H, t)) time. Now, consider a reduced instance. If ` < 0, then we can
reject the instance. Otherwise, consider the following two cases.
Case 1: H = ∅. If G is triangle-free, then we are done. Otherwise, pick an arbitrary
triangle in G and add it to H.
Case 2: H contains a graph H. Since Reduction Rule 4.1 does not apply to H,
there is a certificate T of t0 ≤ τ(H) + 1 triangles, each containing exactly one distinct
9

edge of H such that deleting the edges of these triangles contained in H produces a
subgraph H 0 of H that cannot be made triangle-free by τ(H) − t0 edge deletions. Thus,
branch into the following (2t0 + 1) cases: First, for each triangle T ∈ T , create two
cases, in each deleting a different one of the two edges of T that are not in H. In the
remaining case, delete the t0 edges of H and replace H by H 0 in H.
It remains to show the running time by bounding the search tree size. In Case 1,
no branching is performed and the parameter is decreased by at least one. In Case 2,
the parameter value is decreased by one in each branch: in the first 2t0 cases, an edge
that is not contained in any packing graph is deleted. Thus, k decreases by one while
h(H) remains unchanged. In the final case, the value of k decreases by t0 since this
many edge deletions are performed. However, τ(H 0 ) ≥ τ(H) − t0 + 1. Hence, the lower
bound h(H) decreases by at most t0 − 1 and thus the parameter ` decreases by at least
one. Note that applying Reduction Rule 4.1 never increases the parameter. Hence, the
depth of the search tree is at most `.
t
u
Corollary 4.7 Triangle Deletion with Cost-t Packing
(i) can be solved in O((2t + 3)` · (nm + n · 2.076t ) time, and
(ii) admits a problem kernel with at most (12t + 6)` vertices that can be computed
in O(nm + n · 2.076t ) time.
For the natural special case t = 1, that is, for triangle packings, Theorem 4.6(i)
immediately yields the following running time.
Corollary 4.8 Triangle Deletion with Triangle Packing is solvable in O(5` nm) time.
4.2 Hardness for edge-disjoint packing
We complement the positive results of Theorem 4.6 by the following hardness result
for the case of edge-disjoint triangle packings:
Theorem 4.9 Triangle Deletion is NP-hard even for ` := k − |H| = 0 if H is an
edge-disjoint packing of triangles.
Theorem 4.9 shows that parameterizing Triangle Deletion over a lower bound given
by edge-disjoint packings cannot lead to fixed-parameter algorithms unless P = NP.
We prove Theorem 4.9 using a reduction from 3-SAT.
Problem 4.10 (3-SAT)
Input: A Boolean formula φ = C1 ∧ . . . ∧ Cm in conjunctive normal form over
variables x1 , . . . , xn with at most three variables per clause.
Question: Does φ have a satisfying assignment?
Construction 4.11 Given a Boolean formula φ, we create a graph G and an edgedisjoint packing H of triangles such that G can be made triangle-free by exactly
|H| edge deletions if and only if there is a satisfying assignment for φ. We assume that
each clause of φ contains exactly three pairwise distinct variables. The construction is
illustrated in Figure 4.1.
10

x3`

x1`

x2k

xT
xF
`
`

xT
k

x1k

xF
k

c3j

x2`

x3k
Yj
c1j

x2i

c2j

xT
i
xF
i

x1i

x3i
Fig. 4.1 Construction for a clause C j = (xi ∨ ¬xk ∨ ¬x` ). The triangles on a gray background are contained
in the mutually edge-disjoint triangle packing H. Deleting the dashed edges corresponds to setting xi and x`
to false and xk to true, thus satisfying C j . Note that it is impossible to destroy triangle Y j by |H| edge
deletions if we delete xiF , xkT , and x`T , which corresponds to the fact that clause C j cannot be satisfied by this
variable assignment.

For each variable xi of φ, create a triangle Xi on the vertex set {xi1 , xi2 , xi3 } with
two distinguished edges xiT := {xi1 , xi2 } and xiF := {xi2 , xi3 } and add Xi to H. For each
clause C j = (l1 , l2 , l3 ) of φ, create a triangle Y j on the vertex set {c1j , c2j , c3j } with three
edges clj1 , clj2 , and clj3 . Connect the clause gadget Y j to the variable gadgets as follows:
If lt = xi , then connect the edge cljt =: {u, v} to the edge xiT = {xi1 , xi2 } via two adjacent
triangles Ai j := {u, v, xi1 } and Bi j := {v, xi1 , xi2 } sharing the edge {v, xi1 }. The triangle Ai j
is added to H. If lt = ¬xi , then connect the edge cljt =: {u, v} to the edge xiF = {xi2 , xi3 }
via two adjacent triangles Ai j := {u, v, xi3 } and Bi j := {v, xi2 , xi3 } sharing the edge {v, xi3 }.
The triangle Ai j is added to H.
Proof (of Theorem 4.9) First, observe that Construction 4.11 introduces no edges
between distinct clause gadgets or distinct variable gadgets. Thus, under the assumption that each clause contains each variable at most once, the only triangles in the
constructed graph are the Xi , the Y j , the Ai j and Bi j for all variables xi and the incident
clauses C j .
Now, assume that φ allows for a satisfying assignment. We construct a set of
edges S of size |H| such that G0 := (V, E \ S ) is triangle-free. For each variable xi that
11

is true, add xiT to S . For each variable xi that is false, add xiF to S . By this choice, the
triangle Xi is destroyed in G0 for each variable xi . Additionally, for each clause C j and
its true literals l ∈ {xi , ¬xi }, the triangle Bi j is destroyed. To destroy Ai j , we add to S
the edge of Ai j shared with Y j , which also destroys the triangle Y j . For each clause C j
containing a false literal l ∈ {xi , ¬xi }, we destroy Bi j and simultaneously Ai j by adding
to S the edge of Ai j shared with Bi j .
Conversely, assume that there is a set S of size |H| such that G0 = (V, E \ S ) is
triangle-free. We construct a satisfying assignment for φ. First, observe that, since the
triangles in H are pairwise edge-disjoint, S contains exactly one edge of each triangle
in H. Thus, of each triangle Xi , at most one of the two edges xiF and xiT is contained
in S . The set S contains at least one edge e of each Y j . This edge is shared with a
triangle Ai j . Since Ai j ∈ H and, with e, S already contains one edge of Ai j , S does not
contain the edge shared between Ai j and Bi j . Since Bi j < H, S has to contain an edge
of Bi j shared with another triangle in H. If the clause C j contains xi , then the only
such edge is xiT and we set xi to true. If the clause C j contains ¬xi , then the only such
edge is xiF and we set xi to false. In both cases, clause C j is satisfied. Since at most
one of xiT and xiF is in S , the value of each variable xi is well-defined.
t
u
5 Feedback Arc Set in Tournaments
In this section, we present a fixed-parameter algorithm and a problem kernel for Feedback Arc Set in Tournaments parameterized above lower bounds of cost-t packings.
In Feedback Arc Set in Tournaments, we are given a directed tournament graph G
as input and want to delete a minimum number of arcs to make the graph acyclic, that
is, to destroy all directed cycles in G. Due to a well-known observation, one can also
view Feedback Arc Set in Tournaments as an arc reversal problem: After deleting a
minimum set of arcs to make the graph acyclic, adding the arc (u, v) for every deleted
arc (v, u) does not create any cycle. Since, in tournaments, every pair of vertices is
connected by exactly one arc, it follows that that destroying cycles by edge deletions is
equivalent to destroying them by arc reversals. Altogether, we arrive at the following
problem definition.
Problem 5.1 (Feedback Arc Set in Tournaments (FAST))
Input: An n-vertex tournament G = (V, A) and a natural number k.
Question: Does G have a feedback arc set S ⊆ A, that is, a set S such that reversing
all arcs in S yields an acyclic tournament, of size at most k?
FAST is NP-complete [1] but fixed-parameter tractable with respect to k [2, 14,
16, 20,
√
27, 42]. The running time of the current best fixed-parameter algorithm is 2c· k + nO(1)
where c ≤ 5.24 [20]. Moreover, a problem kernel with (2 + )k vertices for each
constant  > 0 is known [4] as well as a simpler 4k-vertex kernel [40]. It is wellknown that a tournament is acyclic if and only if it does not contain a directed triangle
(a cycle on 3 vertices). Hence, the problem is to find a set of arcs whose reversal leaves
no directed triangle in the tournament.
We show fixed-parameter tractability of FAST with Cost-t Packing parameterized
P
by the combination of t and ` := k − h(H). Recall that h(H) := H∈H τ(H) ≥ |H|,
12

where τ(G) is the size of a minimum feedback arc set for a directed graph G. The
approach is the same as for Triangle Deletion in Section 4, that is, we upper-bound the
solution size k in t and ` and apply the fixed-parameter algorithm for k [27]. Observe
in this context that Lemma 3.2 is also correct if the input graphs are directed and if
a solution contains arc reversals, since we observed arc reversals and deletions to be
equivalent in the context of FAST.2 We use the following reduction rule for FAST
analogous to Reduction Rule 4.1 for Triangle Deletion.
Reduction Rule 5.2 If there is a subtournament H ∈ H and a feedback arc set T ⊆
A(H) of size τ(H) such that reversing the arcs in T leaves no directed triangles in G
containing arcs of H, then reverse the arcs in T , remove H from H, and decrease k
by τ(H).
Although Reduction Rule 5.2 is strikingly similar to Reduction Rule 4.1, its correctness
proof is significantly more involved.
Lemma 5.3 Reduction
Rule 5.2 is correct
and, given the tournaments G and H it can
 

be applied in O q2 (n − q) + Γ(H, t) time, where q := |V(H)| and Γ(H, t) denotes the
running time needed to compute a feedback arc set of size at most t in H if it exists.
Proof We first show correctness. Let I 0 := (G0 , H \ {H}, k − τ(H)) be the instance
created by Reduction Rule 5.2 from I := (G, H, k) by reversing a subset T of arcs of a
subtournament H ∈ H of G. If I 0 is a yes-instance, then so is I since G0 is the graph G
with the τ(H) arcs in T reversed and, thus, adding these arcs to a feedback arc set of
size k − τ(H) for G0 gives a feedback arc set of size k for G. It remains to prove that if
I is a yes-instance, then so is I 0 . To this end, we show that there is a minimum-size
feedback arc set S for G with T ⊆ S .
Let S be a minimum-size feedback arc set for G = (V, E). This implies the
existence of a linear ordering σS = v1 , . . . , vn of the vertices V such that there are |S |
backward arcs, that is, arcs (vi , v j ) ∈ A such that i > j. Now, let σT = w1 , . . . , w|W|
be the ordering of the vertices of H = (W, F) corresponding to the local solution T
for H with τ(H) backward arcs. Let N + (w) := {(w, v) ∈ A | v ∈ V \ W} denote the
out-neighbors in V \ W of a vertex w ∈ W. Analogously, N − (w) := {(v, w) ∈ A | v ∈
V \ W} denotes the set of in-neighbors. By the assumption of the rule, for all i < j,
N + (w j ) ⊆ N + (wi ) and N − (wi ) ⊆ N − (w j )

(5.1)

holds since otherwise, after reversing the arcs in T , there exists a directed cycle
containing an arc of H (because the arc (wi , w j ) is present).
If the vertices of W appear in σS in the same relative order as in σT , then we
have T ⊆ S and we are done. Otherwise, we show that we can swap the positions of
vertices of W in σS so that their relative order is the same as in σT without increasing
the number of backward arcs.
First, note that the number of backward arcs between vertices in V \ W does not
change when only swapping positions of vertices in W. Also, by assumption, the
number of backward arcs between vertices in W in any ordering is at least τ(H),
2

For directed input graphs, we use the term external arc instead of external edge.

13

whereas it is exactly τ(H) when ordering them according to σT . Thus, it remains
to show that the number of backward arcs between vertices in W and V \ W is not
increased. To this end, consider a series of swaps of pairs of vertices w j and wi such
that i < j, where w j appears before wi in σS , reordering the vertices in W according
to σT . Let Y denote the set of all vertices that lie between w j and wi in σS . Note that
swapping w j and wi removes the backward arcs from wi to the vertices in N + (wi ) ∩ Y
and the backward arcs from vertices in N − (w j ) ∩ Y to w j , whereas it introduces
new backward arcs from w j to N + (w j ) ∩ Y and from N − (wi ) ∩ Y to wi . However, by
the inclusions in (1), it follows that the overall number of backward arcs does not
increase in each swap. Hence, the overall number of backward arcs is not increased
by repositioning the vertices in W according to σT . It follows that there is an optimal
solution containing T .
It remains to show the running time. First, in Γ(H, τ(H)) time, we compute the
size τ(H) of an optimal feedback arc set for H = (W, F). Now, for each arc (u, v) ∈ F,
we check whether there is a vertex w ∈ V \W that forms a directed triangle with u and v.
If such a vertex exists, then we reverse the arc (u, v). If this arc reversal introduces a
new directed triangle with another vertex from V \ W, then the rule does not apply.

Overall, this procedure requires O |F| · (n − |W|) time. Let T ∗ denote the set of arcs
that are reversed in this process. Clearly, if |T ∗ | > τ(H), then the rule does not apply.
Otherwise, let H 0 denote the graph obtained from H by reversing the arcs in T ∗ and
observe that each remaining directed triangle of G that contains at least one arc of H 0
is contained in H 0 . Thus, we now compute whether H 0 has a feedback arc set T 0 of
size τ(H) − |T ∗ | in Γ(H 0 , τ(H) − |T ∗ |) time. If this is the case, then the rule applies and
we set T := T 0 ∪ T ∗ (note that T 0 ∩ T ∗ = ∅, since otherwise |T | < τ(H), which is not
possible by definition of τ(H)). Otherwise, removing all directed triangles that contain
at least one arc from H requires more than τ(H) arc reversals and thus the rule does
not apply.
t
u
Exhaustive application of Reduction Rule 5.2 allows us to show that k ≤ (2t + 1)`
holds for any yes-instance (analogous to Lemma 4.5).
Lemma 5.4 Let (G, H, k) be a yes-instance of Feedback Arc Set in Tournaments
with Cost-t Packing such that Reduction Rule 5.2 cannot be applied to any tournament
in H. Then, k ≤ (2t + 1)`.
Proof Since Reduction Rule 5.2 cannot be applied to any tournament in H, for each
tournament H = (W, F) in H, there is a set of arcs between W and V \ W that witness
that no optimal feedback arc set for H removes all directed triangles containing at
least one arc from F.
Now, for any optimal solution, there are two possibilities for each packing tournament H ∈ H:
(a) at least τ(H) + 1 arcs in H are reversed, or
(b) at least one external arc of H is reversed.
Therefore, S fulfills the condition of Lemma 3.2 and, thus, |H| ≤ 2`.
The bound on k yields the following two fixed-parameter tractability results.
14

t
u

Theorem 5.5 Let Γ(G, k) be the running time used for finding a minimum feedback
arc set of size at most k for a given tournament G if it exists. Then, Feedback Arc Set
in Tournaments with Cost-t Packing
P
(i) is solvable in Γ(G, (2t + 1)`) + nO(1) + H∈H Γ(H, t) time, and
(ii) admits a problem kernel with at most (8t + 4)` vertices computable in nO(1) +
P
H∈H Γ(H, t) time.
Proof (i) Given (G, H, k), we first apply Reduction Rule 5.2 for each H ∈ H.
P
This application can be performed in O(|H|n3 + H∈H Γ(H, t)) time by Lemma 5.3
since |H| ≤ n. One pass of this rule is sufficient to obtain an instance that is reduced:
reversing arcs in some H ∈ H does not remove any directed triangles containing arcs
of any other H 0 ∈ H with H 0 , H. By Lemma 5.4, we can then reject the instance
if k > (2t + 1)`. Otherwise, we can find a solution in Γ(G, (2t + 1)`) time.
(ii) First, we apply Reduction Rule 5.2 once for each H ∈ H in O(|H|n3 +
P
H∈H Γ(H, t)) time. After one pass of this rule, the instance is reduced since reversing
arcs in some H ∈ H does not remove any directed triangles containing arcs of any
other H 0 ∈ H with H 0 , H. Afterwards, by Lemma 5.4, we can reject if k > (2t + 1)`.
Otherwise, we apply the kernelization algorithm for FAST by Paul et al [40] to the
instance (G, k) to obtain an equivalent instance (G0 , k0 ) with at most 4k ≤ (8t + 4)`
vertices and a solution size k0 ≤ k. Hence, (G0 , ∅, k0 ) is our problem kernel with
parameter `0 = k0 ≤ (2t + 1)` of Feedback Arc Set in Tournaments with Cost-t
Packing.
t
u
In Theorem 5.5, we again assume that Γ is √monotonically nondecreasing in both the
size of G and in k. As mentioned earlier, 2O( k) + |V(G)|O(1) is the currently best known
running time for Γ(G, k) [27].
Corollary 5.6 Feedback Arc Set in Tournaments with Cost-t Packing
√

√

(i) can be solved in 2O( (2t+1)`) + nO(1) + n2O( t) time, and
O(1)
+
(ii) admits
√ a problem kernel with at most (8t + 4)` vertices computable in n
O( t)
n2
time.

6 Cluster Editing
We finally apply our framework from Section 3 to Cluster Editing, a well-studied
edge modification problem in parameterized complexity [7, 12, 21, 28].
Problem 6.1 (Cluster Editing)
Input: A graph G = (V, E) and a natural number k.
 
Question: Is there an edge modification set S ⊆ V2 of size at most k such that G4S
is a cluster graph, that is, a disjoint union of cliques?
A graph is a cluster graph if and only if it is P3 -free [45]. Thus, Cluster Editing is
the problem of destroying all P3 s by few edge modifications. For brevity, we refer to
the connected components of a cluster graph (which are cliques) and to their vertex
sets as clusters. The currently fastest algorithm for Cluster Editing parameterized by
15

Fig. 6.1 An illustration of Reduction Rule 6.2. Left: An induced subgraph H (highlighted by the gray
background) fulfilling the conditions of Reduction Rule 6.2. Right: The result of applying Reduction
Rule 6.2. The two clusters in G[W] produced by the optimal solution for H are highlighted by a gray
background.

the solution size k runs in O(1.62k + n + m) time [7]. Assuming the exponential-time
hypothesis, Cluster Editing cannot be solved in 2o(k) · nO(1) time [21, 28]. Cluster
Editing admits a problem kernel with at most 2k vertices [12].
First, in Section 6.1, we present a fixed-parameter algorithm and problem kernel
for Cluster Editing parameterized above lower bounds given by cost-t packings. Then,
in Section 6.2, we present a faster fixed-parameter algorithm for lower bounds given
by vertex-disjoint packings of P3 s.

6.1 A fixed-parameter algorithm for vertex-disjoint cost-t packings
Several kernelizations for Cluster Editing are based on the following observation:
If G contains a clique such that all vertices in this clique have the same closed
neighborhood, then there is an optimal solution that puts these vertices into the same
cluster [12, 25, 41]. This implies that the edges of this clique are never deleted. The
following rule is based on a generalization of this observation.
Reduction Rule 6.2 If G = (V, E) contains an induced subgraph H = (W, F) having
an optimal solution S of size τ(H) such that, for all vertices u, v ∈ W,
– NG (v) \ W = NG (u) \ W if u and v are in the same cluster of H4S , and
– NG (v) ∩ NG (u) ⊆ W otherwise,
then replace G by G4S , remove H from H, and decrease k by τ(H).
An example of Reduction Rule 6.2 is presented in Figure 6.1.
Lemma 6.3 Reduction Rule 6.2 is correct.
Proof Let I 0 := (G4S , H 0 , k − τ(H)) be the instance obtained by applying Reduction
Rule 6.2 to I := (G, H, k) for some induced subgraph H = (W, F) of G = (V, E). If
I 0 is a yes-instance, then so is I: adding the τ(H) edges in S to any solution S 0 of
size k − τ(H) for G4S gives a solution of size k for G since S ∩ S 0 = ∅ and, thus,
G4(S ∪ S 0 ) = (G4S )4S 0 . It remains to prove that if I is a yes-instance, then so is I 0 .
To this end, we show that (G, H, k) has an optimal solution S 0 such that S ⊆ S 0 .
For convenience, let X := V \ W denote the set of vertices not in W. Let S ∗ be
any optimal solution for G, and denote by G∗ := G4S ∗ the cluster graph produced
by S ∗ . We show how to transform S ∗ into an optimal solution S 0 ⊇ S . To this end,
partition S ∗ as follows:
16

– S 1∗ := {{u, v} ∈ S ∗ | u, v ∈ X} containing all edge modifications outside of H,
– S 2∗ := {{u, v} ∈ S ∗ | u ∈ X ∧ v ∈ W} containing the edge modifications between H
and the rest of G, and
– S 3∗ := {{u, v} ∈ S ∗ | u, v ∈ W}.
Moreover, let Wext be the vertices of W that have at least one neighbor in X and
let Wint := W \ Wext . Consider the following equivalence relation ∼ on Wext : two
vertices u, v ∈ Wext are equivalent with respect to ∼ if and only if NG (u)∩X = NG (v)∩X.
For each vertex u ∈ Wext , let [u] denote the equivalence class of u in ∼.
Fix within each equivalence class [u] of ∼ an arbitrary vertex that is incident to a
minimum number of edge modifications in S 2∗ and, for each vertex u, denote this vertex
by ũ. Furthermore, for each cluster K of G∗ containing some vertices of X and some
vertices of Wext , fix an arbitrary vertex of Wext that has in G a maximum number of
neighbors in K∩X; denote this vertex by uK . Finally, call a vertex u ∈ Wext good if there
is a cluster K such that ũ = uK . Now consider the edge modification set S 0 := S 1∗ ∪S̃ ∪S ,
where
n
o
S̃ := {u, v} | u is good and {ũ, v} ∈ S 2∗ ∪
n
o
∪ {u, v} | u is not good and v ∈ NG (u) ∩ X .
Informally, the modifications in S̃ consider ũ to determine how to treat all vertices in
the equivalence class [u]. If, among the vertices of Wext , ũ has the most neighbors in
its cluster in G∗ , then all vertices of [u] are treated like ũ. Otherwise, all edges between
vertices in [u] and X are deleted.
We first show that S 0 is a solution, that is, G0 := G4S 0 is a cluster graph: First,
0
G [X] = G∗ [X] is a cluster graph. Second, G0 [W] = H4S and thus it is a cluster graph.
Third, every vertex u ∈ Wint is contained in a cluster that is a subset of Wint in G0 : In G,
there are no edges between Wint and X, no edges between Wint and X are added by S̃ ,
and by the first condition on S , no vertex of Wint is in the same cluster of H4S as a
vertex from Wext . This implies that the connected component of each vertex u ∈ Wint
is completely contained in W and thus it is a clique since G0 [W] is a cluster graph.
Finally, consider any equivalence class [u] of Wext . By the condition of Reduction
Rule 6.2, [u] is contained in a cluster in H4S . Now, if all vertices of [u] are good,
then there is a cluster K in G0 [X] such that in G0 all vertices of [u] are adjacent to all
vertices of K. Otherwise, no vertex of [u] is good and thus, no vertex of [u] is adjacent
to any vertex of X in G0 . Finally, if a cluster K of G0 [X] has neighbors in W, then these
edges are only to the vertex set [uK ]. Thus, every vertex in K has neighbors in at most
one cluster of H4S . Altogether this shows that G0 is a cluster graph.
It remains to show that |S 0 | ≤ |S ∗ |. First, S 1∗ is a subset of S ∗ and of S 0 . Second,
|S | ≤ |S 3∗ | since S is an optimal solution for H. Thus, it remains to show |S̃ | ≤ |S 2∗ |.
Since the vertices of Wint are not incident to any edge modifications in S̃ , we may
prove this inequality by showing, for each vertex u ∈ Wext , that
|{e ∈ S̃ | u ∈ e}| ≤ |{e ∈ S 2∗ | u ∈ e}|.
If u is good, then the number of edge modifications incident with u in S̃ is the same
as the number of edge modifications incident with ũ in S 2∗ , because u and ũ have the
17

same neighborhood in X by the condition of the rule. By the choice of ũ, this is at
most as large as the number of edge modifications incident with u in S 2∗ and the claim
holds.
Otherwise, all edges between u and X are deleted by S̃ . Let K denote the cluster
in G4S ∗ containing ũ. Since u is not good, there is a vertex w that is not in [u] such
that w has at least as many neighbors in K ∩ X as ũ. By the condition of Reduction
Rule 6.2 and since [ũ] , [w], the neighborhoods of these two vertices in X are disjoint,
that is, (NG (ũ) ∩ X) ∩ (NG (w) ∩ X) = ∅. Since w has at least as many neighbors in K ∩ X
as ũ, this means that
|NG (ũ) ∩ K ∩ X| ≤ |K ∩ X|/2.
Now, observe that S 2∗ contains an edge insertion between ũ and each nonneighbor
of ũ in K ∩ X. Thus, at least |K ∩ X|/2 edges between ũ and K ∩ X are inserted by S 2∗ .
Moreover, S 2∗ contains an edge deletion between ũ and each neighbor of ũ in X \ K.
Altogether, this implies
|{e ∈ S 2∗ : ũ ∈ e}| ≥ |K ∩ X|/2 + |NG (ũ) ∩ (X \ K)| ≥ |NG (ũ) ∩ X|.
Therefore, the number of edge modifications incident with u in S̃ (this is exactly
the number of edges between u and X) is at most as large as the number of edge
modifications incident with ũ in S 2∗ . By the choice of ũ, this implies the claim.
t
u
It remains to analyze the running time for applying Reduction Rule 6.2.
Lemma 6.4 Let Γ(G, k) be the running time used for finding an optimal solution of
size at most k in a graph G if it exists.
P
Then, in O(m + H∈H Γ(H, t)) time, we can apply Reduction Rule 6.2 to all graphs
in H.
Here, we assume that Γ is monotonically nondecreasing in k and polynomial in the
size of G. Currently, O(1.62k + |V(G)| + |E(G)|) is the best known bound for Γ(G, k) [7].
P
Proof We first show that the rule can be applied in O(|W|+ w∈W degG (w)+Γ(H, t)) time
to an arbitrary graph H = (W, F) ∈ H. For convenience, denote X := V \ W.
First, observe that a necessary condition for the rule is that, for each pair of
vertices u and v in H, their neighborhoods in X are the same or disjoint. This can be
P
checked in O(|W| + w∈W degG (w)) time as follows. First, build the bipartite graph
with parts W and N(W) and those edges between the vertex sets that are also edges
of G (equivalently, G[W ∪ N(W)] minus the edges with both endpoints in W or both
endpoints in N(W)). This bipartite graph is a disjoint union of complete bipartite graphs
if and only if above condition is fulfilled. Thus, we check in O(|W| + |F|) time, whether
the graph is a disjoint union of complete bipartite graphs. If not, then the rule does not
apply. Otherwise, in the created bipartite graph, we compute in O(|W| + |F|) time the
groups of vertices of W whose neighborhood is the same. Afterwards, we can check in
O(1) time whether u and v have the same neighborhood in X in G by checking whether
they belong to the same group. We now compute the set S 0 of edge modifications
that is already determined by the conditions of the rule: If v and w are nonadjacent
and have the same nonempty neighborhood in X, then the edge {v, w} needs to be
18

inserted and is thus added to S 0 . Similarly, if v and w are adjacent and have different
neighborhoods in X, then {v, w} needs to be deleted and is thus added to S 0 . Observe
that if S 0 is a subset of an optimal solution S for H, then |S | ≤ |F|. Hence, at most |F|
edges are added to S 0 . Since we already computed the groups of vertices that have the
same or disjoint neighborhoods, we can thus compute S 0 in O(|W| + |F|) time.
Let Wext denote the vertices of W that have at least one neighbor in N(W) and
let Wint := W \ Wext . Note that after applying S 0 , that is, in H4S 0 , the vertices
of Wext are in separate clusters: (H4S 0 )[Wext ] is a cluster graph and there are no edges
between Wext and Wint in H4S 0 . Thus, to determine whether S 0 can be extended to
an optimal solution S for H that fulfills the condition of the rule, we compute an
optimal solution of H[Wint ] in Γ(H[Wint ], τ(H) − |S 0 |) time. Since |H[Wint ]| ≤ |H| and
τ(H) − |S 0 | < t, this can be done in Γ(H, t) time. The size of the resulting solution S is
compared with the size of an optimal solution of H, which can also be computed in
Γ(H, t) time.
It remains to show that Reduction Rule 6.2 can be applied to all graphs within
the claimed running time. For each graph H = (W, F) ∈ H, we can check in O(|W| +
P
w∈W degG (w) + Γ(H, t)) time whether Reduction Rule 6.2 applies. If yes, then we
can apply the rule in O(|F|) time by modifying at most |F| edges. Summing up over
all graphs in H gives the claimed running time.
t
u
Observe that since k is decreased by τ(H), the parameter ` does not increase when
Reduction Rule 6.2 is applied. As for the previous problems, applying the rule to
each H ∈ H is sufficient for bounding k in t and ` and thus, for transferring known
fixed-parameter tractability results for the parameter k to the combined parameter (t, `).
Lemma 6.5 Let (G, H, k) be a yes-instance of Cluster Editing with Cost-t Packing
such that Reduction Rule 6.2 does not apply to any H ∈ H. Then, k ≤ (2t + 1)`.
Proof Since the instance is reduced with respect to Reduction Rule 6.2, for each H =
(W, F) in H and each size-τ(H) solution S for H, either the vertices of some cluster
have different neighborhoods in V \ W or two vertices of two distinct clusters have a
common neighbor outside of W.
Now, fix an arbitrary optimal solution S for G. By the observation above, there are
the following two possibilities for how S modifies each H ∈ H:
(a) more than τ(H) vertex pairs of H are modified by S , or
(b) at least one external vertex pair for H is modified.
Therefore, S fulfills the condition of Lemma 3.2 and thus k ≤ (2t + 1)`.

t
u

Theorem 6.6 Let Γ(G, k) be the running time used for finding an optimal solution of
size at most k in a graph G if it exists. Then, Cluster Editing with Cost-t Packing
P
(i) is solvable in O(Γ(G, (2t + 1)`) + nm + H∈H Γ(H, t)) time and
(ii) admits a problem kernel with at most (4t + 2)` vertices, which can be computed
P
in O(nm + H∈H Γ(H, t)) time.
P
Proof (ii) First, apply Reduction Rule 6.2 exhaustively in O(m + H∈H Γ(H, t)) time.
Then, by Lemma 6.5, we can either return “no” or have k ≤ (2t + 1)`. In the latter
19

case, we apply a kernelization algorithm for Cluster Editing to the instance (G, k)
(that is, without H), which produces, in O(nm) time, a problem kernel (G0 , k0 ) with at
most 2k ≤ (4t + 2)` vertices and with k0 ≤ k [12]. Adding an empty packing gives an
equivalent instance (G0 , ∅, k0 ) with parameter `0 = k0 of Cluster Editing with Cost-t
Packing.
(i) First, apply the kernelization. Then, by Lemma 6.5, we can either return “no”
or have k ≤ (2t + 1)`. We can now apply the algorithm for Cluster Editing that runs
in Γ(G, (2t + 1)`) time.
t
u
By plugging in the best known bound for Γ(G, k), we obtain the following.
Corollary 6.7 Cluster Editing with Cost-t Packing
(i) can be solved in O(1.62(2t+1)·` + nm + n · 1.62t ) time, and
(ii) admits a problem kernel with at most (4t + 2)` vertices that can be computed
in O(nm + n · 1.62t ) time.
6.2 A Search Tree Algorithm for P3 -Packings
For Cluster Editing with P3 -Packing, the generic algorithm based on Reduction
Rule 6.2 (with t = 1) using the currently best running time for Cluster Editing
leads to a running time of O(4.26` + n + m). We now show an algorithm that runs in
O(4` · `3 + n + m) time. The algorithm is based on two special cases of Reduction
Rule 6.2, one further reduction rule and a corresponding branching algorithm.
The analysis of the search tree size is done by considering branching vectors
and their corresponding branching number. The components of a branching vector
denote the decrease of the parameter in each recursive branch. The branching number
depends only on the branching vector, the largest branching number gives the base
in the upper bound on the search tree size; for further details refer to the relevant
monographs [19, 39].
We use the following special cases of Reduction Rule 6.2. In both cases, H is a P3 ;
the correctness is directly implied by Lemma 6.4. In the first rule, adding an edge is
a solution which fulfills the condition of Reduction Rule 6.2. For convenience, we
denote by uvw a P3 on the vertices u, v, and w, where v is the degree-two vertex.
Reduction Rule 6.8 If G contains a P3 uvw such that N(u) \ {u, v, w} = N(v) \
{u, v, w} = N(w) \ {u, v, w}, then insert {u, w} and decrease k by one.
In the second rule, deleting an edge gives such a solution.
Reduction Rule 6.9 If G contains a P3 uvw such that N(u) \ {u, v, w} = N(v) \ {u, v, w}
and N(u) ∩ N(w) = {v}, then delete {v, w} and decrease k by one.
The third rule is crucial for showing an improved running time.
Reduction Rule 6.10 If G contains a clique K on at least three vertices such that
– every vertex in K has at most one neighbor in N(K) and
– every vertex in N(K) has exactly one neighbor in K,
20

then delete all edges between K and N(K) and decrement k by q := |N(K)|.
Lemma 6.11 Reduction Rule 6.10 is correct and can be exhaustively applied in
O(nm) time.
Proof First, enumerate the set of all maximal cliques K on at least three vertices
such that every vertex of K has at most one neighbor in N(K). This can be done in
O(m) time [29]. Note that every vertex is contained in at most one such clique. Now,
by scanning through the adjacency lists of all vertices in an enumerated clique, we
can identify a vertex that has more than one neighbor in the clique. If there is such a
vertex, then the clique can be discarded. Otherwise, the clique fulfills the conditions of
the rule and the rule can be applied. Thus, one application of the rule takes O(m) time.
Since the rule decreases the number of vertices in G, it can be applied O(n) times.
Since q ≤ |K| and |K| ≥ 3, one can construct q P3 s, each containing two vertices
from K and one vertex from N(K), such that no two of them share more than one
vertex. Thus, at least q edge modifications are needed to destroy all P3 s that contain
at least one vertex v ∈ K. Deleting all q edges between K and N(K) destroys all
P3 s that contain at least one vertex of K. Moreover, since these edge deletions cut K
from the rest of the graph, one can safely combine any optimal solution for G[V \ K]
with these q edge deletions, which are necessary and sufficient to destroy all P3 s that
contain at least one vertex of K, to obtain an optimal solution that deletes all q edges
between K and N(K).
t
u
The final rule simply removes isolated clusters from G.
Reduction Rule 6.12 If G contains a connected component K that is a clique, then
remove K from G.
We can now show our improved algorithm for Cluster Editing with P3 -Packing.
Theorem 6.13 Cluster Editing with P3 -Packing can be solved in O(4` · `3 + m +
n) time.
Proof We prove the theorem using a branching algorithm, which applies several
branching rules. Herein, we assume that H contains at least one P3 uvw. Otherwise,
the graph is either P3 -free (in this case we are done) or we can add a P3 to H, which
increases |H| by one and thus reduces the parameter. Furthermore, we assume that
Reduction Rules 6.8 to 6.10 and 6.12 do not apply. First, we take care of P3 s that do
not share an edge with a packing P3 .
Branching Rule 1: If there is an induced P3 that contains at most one vertex of
each P3 in H, then branch into the three cases to destroy this P3 .
None of the cases destroys a P3 of H. Thus, the parameter is decreased by one in
each case; the branching number is 3.
The three further rules deal with packing P3 s uvw.
Branching Rule 2: If there is a vertex x that is adjacent to u and w but not to v,
then branch into four cases: delete {u, x}; delete {w, x}; add {v, x}; or delete {u, v}
and {v, w} and add {u, w}.
In each of the first three branches, k is reduced by one without destroying any P3
of H. If none of the first three cases applies, then u, w, and x are in the same cluster
21

(no edge deletions between u or w and x) and v is not in this cluster. This makes the
three edge modifications in G[{u, v, w}] necessary. Thus, k is reduced by three and |H|
is reduced by one in this case. The resulting branching vector is (1, 1, 1, 2), which
gives the branching number 3.31.
Branching Rule 3: If there are vertices x and y such that
– x is adjacent to u and v, and
– y is adjacent to exactly one vertex of {u, v},
then branch into four cases: delete {u, x}; delete {v, x}; delete the edge between y and
its neighbor in {u, v}; or add the edge between y and its nonneighbor in {u, v}.
In each case, an edge is modified without destroying any P3 of H. If none of the
first three cases applies, then u, v, x, and y are in the same cluster, which means that
the missing edge between y and either u or v has to be added. Since the parameter is
reduced by one in each branch, the branching number is 4.
Branching Rule 4: If there is a vertex x that is adjacent to v and not adjacent to u
and w, then branch into four cases: delete {v, x}; add {u, x}; add {w, x}; or delete {u, v}
and {u, w}.
If none of the first three cases applies, then any cluster containing v contains
neither u nor w, thus the branching is correct. The parameter is reduced by one in
each branch, as the last branch destroys a P3 of H but reduces k by two. Thus, the
branching number is 4.
These are the only branching rules that are performed. We now show, by a case
distinction, the following: If none of the branching rules and reduction rules applies,
then the remaining graph has maximum degree two and we can solve the problem in
polynomial time.
Case I: H contains a P3 uvw such that u and w have a common neighbor x , v.
Since Branching Rule 2 does not apply, x is also a neighbor of v. Since Branching Rule 3 does not apply, we have that every other vertex y that is adjacent to u is
also adjacent to v and vice versa. Similarly, every other vertex y that is adjacent to w
is also adjacent to v. Thus, u, v, and w have the same neighbors in V \ {u, v, w}. This
contradicts our assumption that Reduction Rule 6.8 does not apply.
Case II: H contains a P3 uvw such that v has degree at least three. Since Branching Rule 4 does not apply, each vertex x ∈ N(v)\{u, w} is a neighbor of u or w and, since
Case I does not apply, it is not a neighbor of both. Moreover, since Branching Rule 3
does not apply, v can have common neighbors with at most one of u and w. Thus,
without loss of generality, u and v have the same neighborhood in V \ {u, v, w} and v
and w have no common neighbors. This contradicts our assumption that Reduction
Rule 6.9 does not apply.
Case III: H contains a P3 uvw such that u has degree at least three. Consider p
and q from N(u) \ {v}. Since Case II does not apply, p and q are not middle vertices of
a P3 in H. Moreover, since Case I does not apply, p and q are not from the same P3
of H. Consequently, if G[{u, p, q}] is a P3 , then Branching Rule 1 applies. This implies
that G[N[u] \ {v}] is a clique K of size at least three. We now show the following claim,
which contradicts our assumption that Reduction Rule 6.10 does not apply.
Claim: Each vertex of K has at most one neighbor in V \ K and every vertex
in N(K) has at most one neighbor in K.
22

First, observe that no vertices from K are middle vertices of a P3 in H. Thus, K contains at most one vertex x from each P3 of H and this vertex x is not a middle vertex.
For each such x ∈ K from a packing P3 xyz, the same conditions apply as to u,
thus G[N[x] \ {y}] is a clique K 0 . This implies K = K 0 : Since G[N[u] \ {v}] is a clique,
x is adjacent to every vertex in N[u] \ {v} and since G[N[x] \ {y}] is a clique, u is
adjacent to every vertex in N[x] \ {y}. Summarizing, each vertex from K that is in a P3
of H has exactly one neighbor outside of K, this neighbor is a middle vertex of the
packing P3 containing x. These middle vertices have only one neighbor in K since
they have degree two and K contains only one vertex from each packing P3 .
Now let x denote a vertex of K that is not contained in any P3 of H. We show
that N[x] = K, which implies the claim. Since the middle vertices of each P3 of H
have no neighbors outside of this P3 and since Branching Rule 2 does not apply, we
have that x is adjacent to at most one vertex of each packing P3 . Thus, G[N[x]] is a
clique K 0 as otherwise, Branching Rule 1 applies. Again, K 0 = K as G[N[u] \ {v}]
being a clique implies that x is adjacent to every vertex in N[u] \ {v} and G[N[x]]
being a clique implies that u is adjacent to every vertex in N[x].
Case IV: otherwise. We show that every vertex has degree at most two. This is
true for the middle vertices of P3 s in H as Case II does not apply. This also holds for
the endpoints of P3 s in H as Case III does not apply. We now argue that every other
vertex x cannot have two neighbors.
The vertex x has at least one neighbor u from some P3 uvw of H: x is contained
in at least one P3 because the instance is reduced with respect to Reduction Rule 6.12
and this P3 contains at least two vertices of some P3 of the packing because Branching Rule 1 does not apply. If x has a further neighbor y, then y , v (since Case II does
not apply) and v , w since (Case I) does not apply. Consequently, u, x, and y form a
triangle (since Branching Rule 1 does not apply). Thus, u has two neighbors outside
of his P3 of H, which means that Case III applies.
Thus, G has maximum degree two and does not contain isolated triangles because
the instance is reduced with respect to Reduction Rule 6.12. In this case, an optimal
solution can be obtained by computing a maximum matching M and then deleting all
edges of G that are not in M.
Altogether, the above considerations imply a search tree algorithm with search
tree size O(4` ). After an initial kernelization, which, due to Corollary 6.7, runs in
O(m + n) time for t = 1, the instance has O(`) vertices. Thus, the steps at each search
tree node including the reduction rules can be performed in O(`3 ) time.
t
u

7 Hardness Results for Edge Deletion and Vertex Deletion Problems
In this section, we show edge modification problems and vertex deletion problems that
are NP-hard even for small forbidden induced subgraphs and if ` = k − |H|, where
H is a vertex-disjoint packing of forbidden induced subgraphs. We also show that
algorithms for Vertex Cover parameterized above lower bounds do not generalize to
d-Hitting Set—the natural generalization of Vertex Cover to hypergraphs.
23

7.1 Hard edge deletion problems
Theorem 7.1 For every fixed q ≥ 6, Kq -free Deletion with Kq -Packing is NP-hard
for ` = 0.
We prove Theorem 7.1 by giving a reduction from 3-SAT (Problem 4.10).
Construction 7.2 Let φ be a Boolean formula with variables x1 , . . . , xn and clauses C1 ,
. . . , Cm . We assume that each clause C j contains exactly three pairwise distinct variables. We create a graph G and a vertex-disjoint Kq -packing H as follows.
For each variable xi , add a clique Xi on q vertices to G that has two distinguished
disjoint edges xiF and xiT . For each clause C j = (l1 ∧ l2 ∧ l3 ) with literals l1 , l2 , and l3 ,
add a clique Y j on q vertices to G that has three distinguished and pairwise disjoint
edges el1 , el2 , and el3 (which exist since q ≥ 6). Finally, if lt = xi , then identify the
edge elt with xiT and if lt = ¬xi , then identify the edge elt with xiF . The packing H
consists of all Xi introduced for the variables xi of φ.
Lemma 7.3 Let G be the graph output by Construction 7.2 and let H be an induced
Kq in G. Then, H is either one of the Xi or one of the Y j .
Proof First, note that the Xi are pairwise vertex-disjoint since Construction 7.2 only
identifies edges of Y j s with edges of Xi s and no edge in any Y j is identified with edges
in different Xi . For any Xi and Y j , the vertices in V(Xi ) \ V(Y j ) are nonadjacent to those
in V(Y j ) \ V(Xi ). Similarly, for Yi and Y j , the vertices in V(Yi ) \ V(Y j ) are nonadjacent
to those in V(Y j ) \ V(Yi ) for i , j. Thus, every clique in G is entirely contained in one
of the Xi or Y j .
t
u
Lemma 7.3 allows us to prove Theorem 7.1.
Proof (of Theorem 7.1) We show that φ is satisfiable if and only if G can be made
Kq -free by k = |H| edge deletions (that is, ` = 0).
First, assume that there is an assignment that satisfies φ. We construct a Kq -free
deletion set S for G as follows: if the variable xi is set to true, then put xiT into S . If the
variable xi is set to false, then add xiF to S . Thus, for each Xi , we add exactly one edge
to S . Since H consists of the Xi , we have |S | = |H|. Moreover, since each clause C j
contains a true literal, at least one edge of each Y j is contained in S . Thus, G \ S is
Kq -free, since, by Lemma 7.3, the only Kq s in G are the Xi and Y j and, for each of
them, S contains at least one edge.
Now, assume that G can be made Kq -free by deleting a set S of |H| edges. Then,
S deletes exactly one edge of each Xi and at least one edge of each Y j . We can assume
without loss of generality that S contains either the edge xiT or xiF for each Xi since
deleting one of these edges instead of another edge in Xi always yields a solution
by Construction 7.2. Thus, the deletion set S corresponds to a satisfying assignment
for φ.
t
u
24

j00 ,F

vs

j+1,F

vi

j+1,T

vi

j0 ,T

j,F

vi

vr
j,T

vi

j−1,F

vi

j−1,T

vi

Fig. 7.1 An illustration of Construction 7.6 for q = 3. The figure shows parts of the variable cycles for
three variables xi , xr , x s that occur in the clause Ct = (xi ∨ xr ∨ ¬x s ). The packing P3 s are highlighted by a
gray background.

7.2 Hard vertex deletion problems
In this section, we show NP-hardness of the problem of destroying all induced paths Pq
on q ≥ 3 vertices by at most |H| vertex deletions if a packing H vertex-disjoint
induced Pq s in the input graph G is provided as input.
Problem 7.4 (P q -free Vertex Deletion with P q -Packing)
Input: A graph G = (V, E), a vertex-disjoint packing H of induced Pq s, and a natural
number k.
Question: Is there a vertex set S ⊆ V of size at most k such that G[V \ S ] does not
contain Pq as induced subgraph?
Theorem 7.5 For every fixed q ≥ 3, Pq -free Vertex Deletion with Pq -Packing is
NP-hard even if ` = 0.
The reduction is from q-SAT:
Construction 7.6 Let φ be a Boolean formula with variables x1 , . . . , xn and clauses C1 ,
. . . , Cm . We assume that each clause C j contains exactly q pairwise distinct variables.
We construct a graph G and a maximal vertex-disjoint packing H of Pq s as follows;
an illustration of the construction is given in Figure 7.1.
First, we introduce variable gadgets, which will ensure that a solution to Pq -free
Vertex Deletion with Pq -Packing corresponds to an assignment of φ. In the following,
let α(i) denote the number of occurrences of xi and ¬xi in clauses of φ. For each
variable xi , add 4α(i) vertices: vij,T and vij,F , where 1 ≤ j ≤ 2α(i). Call vij,T a true vertex
25

and vij,F a false vertex. Create an induced cycle on the true and false vertices by adding
the edge set
n
o n
o n
o
Ei := {vij,T , vij,F } | 1 ≤ j ≤ 2α(i) ∪ {vij,F , vij+1,T } | 1 ≤ j < 2α(i) ∪ {v2α(i),F
, v1,T
i
i } .
Call this cycle the variable cycle of xi .
Then, for each even j, attach to vij,T an induced Pq−2 , that is, make one of its
degree-one vertices adjacent to vij,T . Then, again for each even j, attach to vij,F an
induced Pq−2 in the same fashion. These paths are called the attachment paths of the
jth segment of the variable cycle of xi .
Now, for each variable xi , assign to each clause Ct containing xi or ¬xi a unique
number p ∈ {1, . . . , α(i)}. Consider the number j = 2p − 1. We will use vertex vij,T
or vij,F to build the clause gadget for clause Ct . If Ct contains the literal xi , then attach
an induced Pq−2 to vij,F . Otherwise, attach an induced Pq−2 to vij,T . As above, call
the path the attachment path of the jth segment of the cycle. Now, let γit := vij,T if
Ct contains xi , and let γit := vij,F if Ct contains ¬xi . Call these vertices the literal
vertices of clause Ct , denoted Πt . The construction of G is completed as follows. For
each Πt add an arbitrary set of edges to G such that G[Πt ] is an induced Pq . The
Pq -packing H contains one (arbitrary) attachment path plus the two segment vertices
from each segment of each variable cycle.
Proof (of Theorem 7.5) Let G be the graph output by Construction 7.6 and let H be
the Pq -packing. We show that φ has a satisfying assignment if and only if G can be
made Pq -free by exactly |H| vertex deletions (that is, ` = 0).
Assume that φ has a satisfying assignment. For each true variable xi in this
assignment, delete all true vertices in its variable gadget, that is, vij,T for 1 ≤ j ≤ 2α(i).
For each false variable xi in this assignment, delete all false vertices in its variable
gadget, that is, vij,F for 1 ≤ j ≤ 2α(i). Denote this vertex set by S and observe that
|S | = |H|. Moreover, observe that each vertex on the variable cycle for xi is either
deleted or both of its neighbors on the cycle are deleted. Every Pq in G contains at least
one vertex from a variable cycle as the attachment paths are too short to induce Pq s.
Thus, to show Pq -freeness of G[V \ S ] it is sufficient to show that no vertex from a
variable cycle is in a Pq .
Consider an undeleted vertex in the variable cycle for xi . Assume, without loss
of generality, that this is a true vertex vij,T . If j is even, then vij,T is not in a Pq as its
neighbors on the cycle are deleted and its only other neighbor is in an attachment path.
If j is odd and the clause Ct corresponding to the jth segment of the cycle contains ¬xi ,
then the only neighbor of vij,T in G[V \ S ] is in an attachment path. It remains to show
that vij,T is not in a Pq if Ct contains xi . The only neighbors of vij,T in G[V \ S ] are
in Πt . Observe that G[Πt ] is an induced Pq and that, in G[V \ S ], every vertex on this
path is deleted or its neighbors in V \ Πt are deleted. Hence, the connected component
of G[V \ S ] containing vij,T is an induced subgraph of G[Πt ]. Since the assignment is
satisfying, at least one vertex of Πt is deleted. Thus, this connected component has at
most q − 1 vertices and does not contain a Pq .
Conversely, let S ⊆ V be a size-|H| vertex set such that G[V \ S ] is Pq -free. First,
observe that, without loss of generality, for each variable cycle either all true or all
26

false vertices are deleted: No vertex in an attachment path P is deleted since it is
always as good to delete the vertex in the variable cycle that has a neighbor in P.
Hence, at least one vertex of each segment is deleted since, otherwise, one of the Pq ’s
in H is not destroyed. This already requires |H| vertex deletions and thus exactly one
vertex for each segment of each variable cycle is deleted. Finally, by construction,
every adjacent pair of vertices in the variable cycle forms a Pq with some attachment
path. Therefore, one of the two vertices is deleted, which implies that either every
even or every odd vertex of the cycle is deleted.
Hence, the vertex deletions in the variable cycle define a truth assignment β
to x1 , . . . , xn : If all true vertices of the variable cycle of xi are deleted, then set β(xi ) :=
true; otherwise, set β(xi ) := false. This assignment is satisfying: Since G[V \ S ] is
Pq -free, for each clause Ct , at least one vertex γit of Πt is deleted. Without loss of
generality, let γit = vij,T , that is, Ct contains the literal xi . Then, β(xi ) = true and thus
β satisfies clause Ct .
t
u
Theorem 7.5 easily transfers to a hardness result for the generalization of Vertex
Cover to d-uniform hypergraphs:
Problem 7.7 (d-Uniform Hitting Set with Packing)
Input: A hypergraph H = (V, E) with |e| = d for all e ∈ E, a set H ⊆ E of pairwise
vertex-disjoint hyperedges, and an integer k.
Question: Is there a vertex set V 0 ⊆ V of size at most k such that ∀e ∈ E : V 0 ∩ e , ∅?
An instance (G, H, k) of Pq -free Vertex Deletion with Pq -Packing can easily be
transformed into an equivalent instance (H, H, k) of q-Uniform Hitting Set with
Packing by taking the hypergraph H on the same vertex set as G having a hyperedge e
if and only if G[e] is a Pq . The packing H and k stay unchanged, and so does `. Thus,
we obtain the following result:
Corollary 7.8 For every d ≥ 3, d-Uniform Hitting Set with Packing is NP-hard even
if ` = 0.
Corollary 7.8 shows that the known above-guarantee fixed-parameter algorithms for
Vertex Cover [13, 22, 36, 43] do not generalize to d-Uniform Hitting Set.

8 Conclusion
It is open to extend our framework to further problems. The most natural candidates appear to be problems where the forbidden induced subgraph has four vertices. Examples
are Cograph Editing [35] which is the problem of destroying all induced P4 s, K4 -free
Editing, Claw-free Editing, and Diamond-free Deletion [18, 44]. Another direction
could be to investigate edge completion problems that allow for subexponential-time
algorithms [15]. In the case of vertex-deletion problems, Triangle Vertex Deletion
appears to be the most natural open case. Furthermore, it would be nice to obtain more
general theorems separating the tractable from the hard cases for this parameterization.
For Cluster Editing and Triangle Deletion improved running times are desirable.
27

Maybe more importantly, it is open to determine the complexity of Cluster Editing
and Feedback Arc Set in Tournaments parameterized above the size of edge-disjoint
packings of forbidden induced subgraphs. Finally, our framework offers an interesting
tradeoff between running time and power of generic data reduction rules. Exploring
such tradeoffs seems to be a rewarding topic for the future. The generic rules presented
in this work can be easily implemented, which asks for subsequent experiments to
evaluate their effectiveness.

References
1. Alon N (2006) Ranking tournaments. SIAM Journal on Discrete Mathematics
20(1):137–142
2. Alon N, Lokshtanov D, Saurabh S (2009) Fast FAST. In: Proceedings of the
36th International Colloquium on Automata, Languages, and Programming
(ICALP ’09), Springer, Lecture Notes in Computer Science, vol 5555, pp 49–58
3. Aravind NR, Sandeep RB, Sivadasan N (2016) Parameterized lower bounds
and dichotomy results for the NP-completeness of H-free edge modification
problems. In: Proceedings of the 12th Latin American Symposium on Theoretical
Informatics, (LATIN ’16), vol 9644, pp 82–95
4. Bessy S, Fomin FV, Gaspers S, Paul C, Perez A, Saurabh S, Thomassé S (2011)
Kernels for feedback arc set in tournaments. Journal of Computer and System
Sciences 77(6):1071–1078
5. van Bevern R (2014) Towards optimal and expressive kernelization for d-Hitting
Set. Algorithmica 70(1):129–147
6. van Bevern R, Froese V, Komusiewicz C (2016) Parameterizing edge modification
problems above lower bounds. In: Proceedings of the 11th International Computer
Science Symposium in Russia (CSR’16), Springer, Lecture Notes in Computer
Science, vol 9691, pp 57–72
7. Böcker S (2012) A golden ratio parameterized algorithm for cluster editing.
Journal of Discrete Algorithms 16:79–89
8. Böcker S, Briesemeister S, Bui QBA, Truß A (2009) Going weighted: Parameterized algorithms for cluster editing. Theoretical Computer Science 410(52):5467–
5480
9. Brügmann D, Komusiewicz C, Moser H (2009) On generating triangle-free
graphs. In: Proceedings of the DIMAP Workshop on Algorithmic Graph Theory
(AGT ’09), Elsevier, ENDM, pp 51–58
10. Cai L (1996) Fixed-parameter tractability of graph modification problems for
hereditary properties. Information Processing Letters 58(4):171–176
11. Cai L, Cai Y (2015) Incompressibility of H-free edge modification problems.
Algorithmica 71(3):731–757
12. Chen J, Meng J (2012) A 2k kernel for the cluster editing problem. Journal of
Computer and System Sciences 78(1):211–220
13. Cygan M, Pilipczuk M, Pilipczuk M, Wojtaszczyk JO (2013) On multiway cut
parameterized above lower bounds. ACM Transactions on Computation Theory
5(1):3
28

14. Dom M, Guo J, Hüffner F, Niedermeier R, TrußA (2006) Fixed-parameter tractability results for feedback set problems in tournaments. In: Proceedings of the 6th
International Conference on Algorithms and Complexity (CIAC ’06), Springer,
Lecture Notes in Computer Science, vol 3998, pp 320–331
15. Drange PG, Fomin FV, Pilipczuk M, Villanger Y (2015) Exploring the subexponential complexity of completion problems. ACM Transactions on Computation
Theory 7(4):14
16. Feige U (2009) Faster FAST (feedback arc set in tournaments). CoRR
abs/0911.5094, URL http://arxiv.org/abs/0911.5094
17. Fellows MR (2003) Blow-ups, win/win’s, and crown rules: Some new directions
in FPT. In: Proceedings of the 29th International Workshop on Graph-Theoretic
Concepts in Computer Science (WG ’03), Lecture Notes in Computer Science,
vol 2880, pp 1–12
18. Fellows MR, Guo J, Komusiewicz C, Niedermeier R, Uhlmann J (2011) Graphbased data clustering with overlaps. Discrete Optimization 8(1):2–17
19. Fomin FV, Kratsch D (2010) Exact Exponential Algorithms. Texts in Theoretical
Computer Science. An EATCS Series, Springer
20. Fomin FV, Pilipczuk M (2013) Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In: Proceedings of the 21st
Annual European Symposium (ESA ’13), Springer, Lecture Notes in Computer
Science, vol 8125, pp 505–516
21. Fomin FV, Kratsch S, Pilipczuk M, Pilipczuk M, Villanger Y (2011) Subexponential fixed-parameter tractability of cluster editing. CoRR abs/1112.4419, URL
http://arxiv.org/abs/1112.4419
22. Garg S, Philip G (2016) Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. In: Proceedings of the 27th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA ’16), SIAM, pp 1152–1166
23. Gramm J, Guo J, Hüffner F, Niedermeier R (2004) Automated generation of search
tree algorithms for hard graph modification problems. Algorithmica 39(4):321–
347
24. Guillemot S, Havet F, Paul C, Perez A (2013) On the (non-)existence of polynomial kernels for P` -free edge modification problems. Algorithmica 65(4):900–926
25. Guo J (2009) A more effective linear kernelization for cluster editing. Theoretical
Computer Science 410(8-10):718–726
26. Hartung S, Hoos HH (2015) Programming by optimisation meets parameterised
algorithmics: A case study for cluster editing. In: Proceedings of the 9th International Conference on Learning and Intelligent Optimization (LION ’15), Springer,
Lecture Notes in Computer Science, vol 8994, pp 43–58
27. Karpinski M, Schudy W (2010) Faster algorithms for feedback arc set tournament,
kemeny rank aggregation and betweenness tournament. In: Proceedings of the
21st International Symposium on Algorithms and Computation (ISAAC ’10),
Springer, Lecture Notes in Computer Science, vol 6506, pp 3–14
28. Komusiewicz C, Uhlmann J (2012) Cluster editing with locally bounded modifications. Discrete Applied Mathematics 160(15):2259–2270
29. Komusiewicz C, Hüffner F, Moser H, Niedermeier R (2009) Isolation concepts for
efficiently enumerating dense subgraphs. Theoretical Computer Science 410(3829

40):3640–3654
30. Kratsch S (2012) Polynomial kernelizations for MIN F+ Π1 and MAX NP. Algorithmica 63(1-2):532–550
31. Kratsch S (2014) Recent developments in kernelization: A survey. Bulletin of the
EATCS 113
32. Kratsch S, Wahlström M (2013) Two edge modification problems without polynomial kernels. Discrete Optimization 10(3):193–199
33. Křivánek M, Morávek J (1986) NP-hard problems in hierarchical-tree clustering.
Acta Informatica 23(3):311–323
34. Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences 20(2):219–230
35. Liu Y, Wang J, Guo J, Chen J (2012) Complexity and parameterized algorithms
for Cograph Editing. Theoretical Computer Science 461:45–54
36. Lokshtanov D, Narayanaswamy NS, Raman V, Ramanujan MS, Saurabh S (2014)
Faster parameterized algorithms using linear programming. ACM Transactions
on Algorithms 11(2):15:1–15:31
37. Mahajan M, Raman V (1999) Parameterizing above guaranteed values: MaxSat
and MaxCut. Journal of Algorithms 31(2):335–354
38. Moser H, Niedermeier R, Sorge M (2012) Exact combinatorial algorithms and experiments for finding maximum k-plexes. Journal of Combinatorial Optimization
24(3):347–373
39. Niedermeier R (2006) Invitation to Fixed-Parameter Algorithms. Oxford University Press
40. Paul C, Perez A, Thomassé S (2016) Linear kernel for rooted triplet inconsistency
and other problems based on conflict packing technique. Journal of Computer and
System Sciences 82(2):366–379
41. Protti F, da Silva MD, Szwarcfiter JL (2009) Applying modular decomposition to
parameterized cluster editing problems. Theory of Computing Systems 44(1):91–
104
42. Raman V, Saurabh S (2006) Parameterized algorithms for feedback set problems
and their duals in tournaments. Theoretical Computer Science 351(3):446–458
43. Razgon I, O’Sullivan B (2009) Almost 2-sat is fixed-parameter tractable. Journal
of Computer and System Sciences 75(8):435–450
44. Sandeep RB, Sivadasan N (2015) Parameterized lower bound and improved kernel
for diamond-free edge deletion. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC ’15), Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, LIPIcs, vol 43, pp 365–376
45. Shamir R, Sharan R, Tsur D (2004) Cluster graph modification problems. Discrete
Applied Mathematics 144(1-2):173–182
46. Wahlström M (2007) Algorithms, measures and upper bounds for satisfiability
and related problems. PhD thesis, Linköpings universitet
47. Yannakakis M (1981) Edge-deletion problems. SIAM Journal on Computing
10(2):297–309

30

