Deleting edges to restrict the size of an epidemic: a new
application for treewidth
Jessica Enright∗

Kitty Meeks†

arXiv:1504.05773v5 [] 19 Apr 2017

April 2017

Abstract
Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small
treewidth) so that the resulting graph avoids a set F of forbidden subgraphs; of particular
interest is the problem of determining whether it is possible to delete at most k edges so that
the resulting graph has no connected component of more than h vertices, as this bounds the
worst-case size of an epidemic. While even this special case of the problem is NP-complete
in general (even when h = 3), we provide evidence that many of the real-world networks of
interest are likely to have small treewidth, and we describe an algorithm which solves the
r
general problem in time 2O(|F |w ) n on an input graph having n vertices and whose treewidth
is bounded by a fixed constant w, if each of the subgraphs we wish to avoid has at most r
vertices. For the special case in which we wish only to ensure that no component has more
than h vertices, we improve on this to give an algorithm running in time O((wh)2w n), which
we have implemented and tested on real datasets based on cattle movements.

1

Introduction

Network epidemiology seeks to understand the dynamics of disease spreading over a network
or graph, and is an increasingly popular method of modelling real-world diseases. The rise
of network epidemiology corresponds to a rapid increase in the availability of contact network
datasets that can be encoded as networks or graphs: typically, the vertices of the graph represent
agents that can be infected and infectious, such as individual humans or animals, or appropriate
groupings of these, such as cities, households, or farms. The edges are then the potentially
infectious contacts between those agents. Considering the contacts within a population as the
edges of a graph can give a large improvement in disease modelling accuracy over mass action
models, which assume that a population is homogeneously mixing. For example, if we consider
a sexual contact network in which the vertices are people and the edges are sexual contacts,
the heterogeneity in contacts is very important for explaining the pattern and magnitude of an
AIDS epidemic [1].
Our work has been especially motivated by the idea of controlling diseases of livestock
by preventing disease spread over livestock trading networks. As required by European law,
individual cattle movements between agricultural holdings in Great Britain are recorded by
the British Cattle Movement Service (BCMS) [23]; in early 2014, this dataset contained just
under 300 million trades and just over 133,000 agricultural holdings. For modelling disease
spread across the British cattle industry, it is common to create vertices from farms, and edges
∗
†

Computing Science and Mathematics, University of Stirling jae@cs.stir.ac.uk
School of Computing Science, University of Glasgow kitty.meeks@glasgow.ac.uk

1

from trades of cattle between those farms: a disease incursion starting at a single farm could
spread across this graph through animal trades, as is thought to have happened during the
economically-damaging 2001 British foot-and-mouth disease crisis [18].
We are interested in controlling or limiting the spread of disease on this sort of network, and
so have focussed our attention on edge deletion, which might correspond to forbidden trade patterns or, more reasonably, extra vaccination or disease surveillance along certain trade routes.
Introducing extra controls of this kind is costly, so it is important to ensure that this is done
as effectively as possible. Many properties that might be desirable from the point of view of
restricting the spread of disease can be expressed in terms of forbidden subgraphs: edge-deletion
to achieve a maximum degree of at most d is equivalent to edge-deletion to a graph avoiding
the star K1,d+1 , and edge-deletion to maximum component size at most h is equivalent to edgedeletion to a graph avoiding all trees on h + 1 vertices. Clearly we can also combine criteria of
this kind, for example edge-deletion to a graph which has maximum component size at most h
and maximum degree at most d. We are therefore concerned with the following general problem.
F-Free Edge Deletion
Input: A graph G = (V, E) and an integer k.
Question: Does there exist E ′ ⊆ E with |E ′ | = k such that G \ E ′ does not contain any
F ∈ F as a subgraph?
This is in fact a special case of the more general problem in which we seek to avoid a set
F of graphs as induced subgraphs (which corresponds to edge-deletion to a hereditary class of
graphs). We have chosen to focus on the special case of edge-deletion to a monotone class of
graphs (that is, a class closed under deletion of vertices and edges) as it is reasonable to assume
in epidemiological applications that if we wish to avoid some subgraph F then we also wish to
avoid any graph F ′ obtained from F by adding edges. Moreover, this assumption improves the
running time of the algorithm by decreasing the size of the family F we wish to avoid, compared
with expressing our target class in terms of forbidden induced subgraphs (for example, only one
forbidden subgraph is required to define the class of graphs with maximum degree at most d, but
to express this in terms of forbidden induced subgraphs we would have to forbid every induced
subgraph on d + 2 vertices that contains a vertex of degree d + 1). However, it is straightforward
to adapt the algorithm described in Section 3 to consider induced subgraphs. The algorithm
can also easily be adapted to deal with different costs associated with the deletion of different
edges (so as to decide whether it is possible to delete edges with a total cost of at most k to
remove all copies of subgraphs from F).
A special case of particular interest is the situation in which F is the set of all trees on
h + 1 vertices, so that we are deleting edges in order to obtain a graph in which every connected
component contains at most h vertices; h is then an upper bound on the number of vertices
which may, in the worst case, be infected from a single initially infected vertex. We denote by
Th+1 the set of all trees on h + 1 vertices, so this special case is the problem Th+1 -Free Edge
Deletion. For this case, we also consider two straightforward extensions of the problem that
are relevant for real-world applications:
• assigning different weights to different vertices (e.g. corresponding to the number of
animals in a particular animal holding), and seeking to bound the total weight of each
connected component;
• imposing different limits on the size of components containing individual vertices (for
example, we might want to enforce a smaller size limit for components containing certain
vertices considered to be of particularly high risk).
2

Even the special case Th+1 -Free Edge Deletion of our general problem is intractable in
general for constant h, as demonstrated in the following proposition. The reduction relies on
the observation that the maximum number of edges in a graph having maximum component
size h is obtained if the graph is a disjoint union of h-cliques.
Proposition 1.1. Th+1 -Free Edge Deletion is NP-complete for every h ≥ 3.
Proof. First, observe that an edge set of size k to be deleted suffices as a certificate for this
problem, therefore Th+1 -Free Edge Deletion is in NP. We prove NP-hardness by means of
a reduction from the following problem, shown to be NP-hard in [11]:
Perfect Triangle Cover
Input: A graph G = (V, E).
Question: Does there exist a set of vertex-disjoint triangles that cover all vertices in the
graph?
Starting with an instance G = (V, E) of Perfect Triangle Cover (where G has n
vertices), we will produce an instance of Th+1 -Free Edge Deletion for arbitrary h ≥ 3 that
is a yes instance if and only if G is a yes instance of Perfect Triangle Cover.
We do this via an intermediate problem, which is a generalisation of Perfect Triangle
Cover to perfect arbitrarily-sized clique covers:
Perfect Kh Cover
Input: A graph G = (V, E).
Question: Does there exist a set of vertex-disjoint cliques of size h that cover all vertices in
the graph?
Note that this problem is in NP: a set of covering cliques constitutes a certificate. In all
instances of Perfect Kh Cover, we will assume the graph has a number of vertices divisible
by h: otherwise this is trivially a no instance.
We show how to transform an instance of Perfect Kh Cover to Perfect Kh+1 Cover:
let G = (V, E) be an instance of Perfect Kh Cover: produce graph G′ by adding to G an
independent set of size |Vh | , with every element of the independent set adjacent to all vertices
in V . We claim that G′ is a yes instance of Perfect Kh+1 Cover if and only if G is a yes
instance of Perfect Kh Cover. First, suppose that G′ is a yes instance of Perfect Kh+1
Cover: then the intersection with V of the Kh+1 that perfectly cover the vertices of G′ are a
set of Kh that perfectly cover the vertices of G. Conversely, suppose that G is a yes instance of
Perfect Kh Cover, then if we extend each of the Kh that perfectly cover the vertices of G
by exactly one of the vertices in the new independent set, we have a set of Kh+1 that perfectly
cover the vertices of G′ .
Note that Perfect Triangle Cover is exactly Perfect K3 Cover: then by iteration
we have that Perfect Kh Cover is NP-complete for any i ≥ 3.
We now reduce Perfect Kh Cover to Th+1 -Free Edge Deletion. If G = (V, E) is an
instance of Perfect Kh Cover, let G = (V, E) and k = |E| − 12 (h − 1)n be an instance of
Th+1 -Free Edge Deletion; we claim that G is a yes instance of Perfect Kh Cover if and
only if (G, k) is a yes instance of Th+1 -Free Edge Deletion.
Suppose first that G = (V, E) is a yes instance of Perfect Kh Cover, so there exists
a set of vertex-disjoint Kh that cover all vertices
of G; let E ′ be the set of edges induced by

n h
′
those Kh . Note that E contains exactly h 2 = 21 (h − 1)n edges, so the edge-set E\E ′ is of
size |E| − 12 (h − 1)n = k; moreover, as there are no edges in E ′ between distinct Kh , the graph
3

G\(E\E ′ ) contains no connected component on more than h vertices. Thus (G, k) is a yes
instance of Th+1 -Free Edge Deletion.
Conversely, suppose that (G, k) is a yes instance of Th+1 -Free Edge Deletion. Then
there exists an edge set F such that |F | = k = |E| − 12 (h − 1)n and every connected component
of G\F is of size h or less; by a pigeonhole argument, these components must all be Kh .
Therefore G is a yes instance of Perfect Kh Cover, as claimed.
In order to develop useful algorithms for real-world applications, we therefore need to exploit
structural properties of the input network. In Section 2 we provide evidence that many animal
trade networks of interest are likely to have small treewidth, and in Section 3 we describe
an algorithm to solve F-Free Edge Deletion whose running time on an n-vertex graph of
r
treewidth w is bounded by 2O(|F |w ) n, if every graph in F has at most r vertices; this algorithm
is easily adapted to output an optimal solution. In Section 4 we then improve on this for the
special case of Th+1 -Free Edge Deletion, describing an algorithm to solve this problem in
time O((wh)2w n) on an n-vertex graph of treewidth w. Many problems that are thought to be
intractable in general are known to admit polynomial-time algorithms when restricted to graphs
of bounded treewidth, often by means of a dynamic programming strategy similar to that used
to attack the problem considered here; however, to the best of the authors’ knowledge, the
usefulness of such algorithms for solving real-world network problems has yet to be investigated
thoroughly.
In reality, policy decisions about where to introduce controls are likely to be influenced by a
range of factors, which cannot all be captured adequately in a network model. Thus, the main
application of our algorithm will be in comparing any proposed strategy with the theoretical
optimum: a policy-maker can determine whether there is a solution with the same total cost
that results in a smaller maximum component size. We provide an example of an experimental
application of our algorithm to cattle trading networks in Section 4.5.
In the remainder of this section, we begin by reviewing previous related work in Section 1.1
before introducing some important notation in Section 1.2 and reviewing the key features of
tree decompositions in Section 1.3.

1.1

Review of previous work

From a combinatorial perspective, we are concerned here with edge-deletion problems. An edgedeletion problem asks if there is a set of at most k edges that can be deleted from an input
graph to produce a graph in some target class. In contrast to the related well-characterised
vertex-deletion problems [20], there is not yet a complete characterisation of the hardness of
edge-deletion problems by target graph class.
Yannakakis [31] gave early results in edge-deletion problems, showing that edge-deletion
to planar graphs, outer-planar graphs, line graphs, and transitive digraphs is NP-complete.
Subsequently, Watanabe, Ae and Nakamura [30] showed that edge-deletion problems are NPcomplete if the target graph class can be finitely characterised by 3-connected graphs. There
are a number of further hardness results known for edge-deletion to well-studied graph classes,
including for interval and unit interval graphs [14], cographs [9], and threshold graphs [22] and,
as noted in [24], hardness of edge-deletion to bipartite graphs follows from the hardness of a
MAX-CUT problem. Natanzon, Shamir and Sharan [24] further showed NP-completeness of
edge-deletion to disjoint unions of cliques, and perfect, chain, chordal, split, and asteroidaltriple-free graphs, but also give polynomial-time algorithms, in the special case of the input
graph having bounded degree, for edge-deletion to chain, split, and threshold graphs.

4

Given the large number of hardness results in the literature, it is natural to consider the
parameterised complexity of these problems. Cai [5] initiated this investigation, showing that
edge-deletion to a graph class characterisable by a finite set of forbidden induced subgraphs is
fixed-parameter tractable when parameterised by k (the number of edges to delete): he gave an
algorithm to solve the problem in time O(r 2k · nr+1 ), where n is the number of vertices in the
input graph and r is the maximum number of vertices in a forbidden induced subgraph. Further
fpt-algorithms have been obtained for edge-deletion to split graphs [13] and to chain, split,
threshold, and co-trivially perfect graphs [17]. When considering graphs of small treewidth,
our algorithm for F-Free Edge Deletion (and indeed its adaptation to deal with forbidden
induced subgraphs) represents a significant improvement on Cai’s algorithm, with our running
r
time of 2O(|F |w ) n. While the fixed parameter tractability of this problem (parameterised by r,
the maximum number of vertices in any element of F) restricted to graphs of bounded treewidth
does follow from the optimization version of Courcelle’s Theorem [3, 6], this does not lead to a
practical algorithm for addressing real-world problems. Note that Proposition 1.1 implies that
parameterisation by r alone will not be sufficient to give an fpt-algorithm.
The specific problem of modifying a graph to bound the maximum component size has
previously been studied both in the setting of epidemiology [21] and in the study of network
vulnerability [16, 8]. The edge-modification version we consider here appears in the literature
under various names, including the component order edge connectivity problem [16] and the
minimum worst contamination problem [21]. Li and Tang [21] show that it is NP-hard to
approximate the minimisation version of the problem to within 2 − ǫ, while Gross et. al.[16]
describe a polynomial-time algorithm to solve the problem when the input graph is a tree.

1.2

Notation and definitions

Unless otherwise stated, all graphs are simple, undirected, and loopless. For graph G = (V, E),
V = V (G) is the vertex set of G, and E = E(G) the edge set of G. We denote the sizes of
the edge and vertex sets of G as e(G) = |E(G)| and v(G) = |V (G)|. For a vertex v ∈ V (G),
we say that vertex u ∈ V (G) is a neighbour of v if (u, v) ∈ E(G), and write NG (v) for the set
of neighbours of v in G. If U ⊆ V (G), we write G[U ] for the subgraph of G induced by the
vertex-set U . Given a graph G = (V, E) and a vertex v ∈ V (G), we write G \ v for the graph
G[V \ {v}]. Given a set of edges E ′ ⊆ E(G) and a vertex v ∈ V (G), we write E ′ \ v for the set
of edges in E ′ that are not incident with v. For any vertex v ∈ V (G), we write dG (v) for the
degree of v in G; when the graph G is clear from the context we may omit the subscript. For
further general graph notation, we direct the reader to [15].
Given two graphs H1 and H2 with v(H1 ) ≤ v(H2 ), an embedding of H1 into H2 is an
injective function θ : V (H1 ) → V (H2 ) such that θ(u)θ(v) ∈ E(H2 ) whenever uv ∈ E(H1 ).
Thus the graph G contains the graph F as a subgraph if and only if there is an embedding
of F into G. We say that the embedding θ is a strong embedding (or induced embedding) if
we have θ(u)θ(v) ∈ E(H2 ) if and only if uv ∈ E(H1 ) (so θ preserves non-adjacency, as well as
adjacency).
Given a function θ which maps a subset of X to a subset of Y , we write Dom(θ) and Im(θ)
for the domain and image of θ respectively. Given a subset X ′ ⊆ Dom(θ), we write θ|X ′ for the
restriction of θ to X ′ .
A partition P of a set X is a collection of disjoint, non-empty sets whose union is X. We call
each set in the partition a block of the partition, and every partition corresponds to a unique
equivalence relation on X where x ∼ y if and only if x and y belong to the same block of X.
If P and P ′ are partitions of X, we say that P ′ refines P if every block of P ′ is contained in
a single block of P. If P is a partition of X, and y ∈ X, we write P \ y for the partition of

5

X \ {y} obtained by removing the occurrence of y from P (and, if this results in an empty set
in the partition, also removing this empty set).

1.3

Tree decompositions

In this section we review the concept of a tree decomposition (introduced by Robertson and
Seymour in [27]) and introduce some of the key notation we will use throughout the rest of the
paper.
Given any tree T , we will assume that it contains some distinguished vertex r(T ), which we
will call the root of T . For any vertex v ∈ V (T ) \ r(T ), the parent of v is the neighbour of v on
the unique path from v to r(T ); the set of children of v is the set of all vertices u ∈ V (T ) such
that v is the parent of u. The leaves of T are the vertices of T whose set of children is empty.
We say that a vertex u is a descendant of the vertex v if v lies somewhere on the unique path
from u to r(T ) (note therefore that every vertex is a descendant of the root). Additionally, for
any vertex v, we will denote by Tv the subtree induced by v together with the descendants of v.
We say that (T, D) is a tree decomposition of G if T is a tree and D = {D(t) : t ∈ V (T )} is
a collection of non-empty subsets of V (G) (or bags), indexed by the nodes of T , satisfying:
S
1. V (G) = t∈V (T ) D(t),
2. for every e = uv ∈ E(G), there exists t ∈ V (T ) such that u, v ∈ D(t),

3. for every v ∈ V (G), if T (v) is defined to be the subgraph of T induced by nodes t with
v ∈ D(t), then T (v) is connected.
The width of the tree decomposition (T, D) is defined to be maxt∈V (T ) |D(t)| − 1, and the
treewidth of G is the minimum width over all tree decompositions of G.
We will denote by S
Vt the set of vertices in G that occur in bags indexed by the descendants
of t in T . Thus, Vt = t′ ∈V (Tt ) D(t′ ).
Later in this paper, we will exploit two useful properties that follow from the definition of
a tree decomposition:
1. If v ∈ D(t) and t′ is a child of t with v ∈
/ D(t′ ), then any path in G from v to a vertex
w ∈ Vt′ must include at least one vertex of D(t) \ {v}.
2. If t ∈ T and t1 , t2 are children of t, then any path in G from a vertex v1 ∈ Vt1 to a vertex
v2 ∈ Vt2 must contain at least one vertex from D(t).
Although it is NP-hard to determine the treewidth of an arbitrary graph [2], it is shown in [4]
that the problem of determining whether a graph has treewidth at most w, and if so computing
a tree-decomposition of width at most w, can be solved in linear time for any constant w
(although the running time depends exponentially on w).
Theorem 1.2 (Bodlaender [4]). For each w ∈ N , there exists a linear-time algorithm, that
tests whether a given graph G = (V, E) has treewidth at most w, and if so, outputs a tree
decomposition of G with treewidth at most w.
A special kind of tree decomposition, known as a nice tree decomposition, was introduced
by Kloks [19]. The nodes in such a decomposition can be partitioned into four types (examples
in Figure 1):
Leaf nodes: t is a leaf in T .
Introduce nodes: t has one child t′ , such that D(t′ ) ⊂ D(t) and |D(t)| = |D(t′ )| + 1.
6

Forget nodes: t has one child t′ , such that D(t′ ) ⊃ D(t) and |D(t)| = |D(t′ )| − 1.
Join nodes: t has two children, t1 and t2 , with D(t1 ) = D(t2 ) = D(t).
t

u,v
leaf

u,v,w

u,w
t’
introduce

t

t

u,w

u,v,w

u,v,w
t’
forget

t1

u,v,w

t2
join

u,v,w

Figure 1: The four types of node in a nice tree decomposition. From left to right: a leaf, an
introduce node, a forget node, and a join node.
Any tree decomposition can be transformed into a nice tree decomposition in linear time:
Lemma 1.3 ([19]). For constant k, given a tree decomposition of a graph G of width w and
O(n) nodes, where n is the number of vertices of G, one can find a nice tree decomposition of
G of width w and with at most 4n nodes in O(n) time.

2

Treewidth of real networks

While the overall graph of cattle trades in Great Britain from 2001 to 2014 is fairly dense, many
of the edges are repeated or parallel trades: that is, a farm sending animals over time to the same
place, or many individual animals being moved at the same time; if we restrict our attention
to a limited time frame, and ignore movements that would generate multiple edges (that is, we
require our graph to be simple), the graph is quite sparse: for example, the aggregated graph
of cattle trades in Scotland in 2009 has an edge-to-vertex ratio of approximately 1.15 when
aggregating over January alone, and approximately 1.34 when aggregating over the entire year.
When considering an epidemic, it is much more relevant only to consider trades occurring within
some restricted time frame (whose precise duration depends on the disease under consideration).
We have investigated the treewidth of real networks arising from two kinds of cattle trade
data. First of all, for years between 2009 and 2014, we generated a graph from a type of
persistent trade link recorded by BCMS in Scotland. The largest of these is derived from the
trades in 2013, and includes approximately 7,000 nodes and 6,000 edges (this lower density is
typical when considering only persistent trade links, or trades over a restricted time period).
None of these graphs has treewidth more than fifteen, with most having treewidth less than
four. Secondly, in addition to these persistent trade links, we have computed an upper bound
of the treewidth of the largest component of an aggregated, undirected version of the overall
network of cattle trades in Scotland in 2009 over a variety of time windows, as illustrated in
Figure 2. The treewidths of these components remains low even for large time windows: for
an aggregation of all movements in a 200-day window the treewidth is below 10, and for all
movements over the year it is below 18. It is unlikely to be necessary to include a full year of
movements in the analysis of any single epidemic, as the time scale of most exotic epidemics is
much shorter.
When modelling disease processes on graphs, it is common to model contact networks with
any of a variety of random graph models, including Erdős-Rényi random graphs or random
graphs with scale-free degree distributions. The cattle trading graphs considered here exhibit
much lower treewidth than we would expect from an Erdős-Rényi graph with the same density:
Gao [10] has shown that Erdős-Rényi graphs with an edge-to-vertex ratio of at least 1.073
7

18

Upper bound on treewidth

16
14
12
10
8
6
4
2

0

50

100
150
200
250
300
Days included in aggregate graph

350

400

Figure 2: A plot of an upper bound treewidth of the largest component in an aggregated, undirected version of the cattle movement graph in Scotland in 2009 over a number of different days
included: all day sets start on January 1, 2009. Treewidths below eight are exact, treewidths
over eight are upper bounds of the true treewidth.
(which our graphs satisfy), have treewidth linear in the number of vertices with high probability.
Scale-free random graphs have also been shown to have high treewidth: Gao also shows that
scale-free graphs produced by preferential attachment with at least 11 edges added at each step
have treewidth linear in the number of vertices with high probability; however, our graphs have
lower density than this.
We have excluded markets from the data used above (so that if animals are sold from farm
A to farm B via a market, this is considered as a direct trade from A to B), so the low treewidth
cannot be explained simply by the fact that most trades take place through a relatively small
number of markets. One possible explanation for the low treewidth is the structure of the
industry: farms can sometimes be characterised by “type”, with breeders producing calves who
then might be grown at one or two other farms before eventual slaughter, meaning that cycles
are unlikely to occur frequently in the network. A more thorough investigation of underlying
processes that lead to trade networks of low treewidth, and their influence on other graph
parameters, seems a fruitful direction for future research.
While we have by no means completed an exhaustive study of the structural properties of
real-world livestock trade networks, the evidence given here seems sufficient to suggest that
algorithms which achieve a good running time on graphs of bounded treewidth will be useful
for this application in practice. Indeed, the benefits of exploiting the treewidth of the input
graph are demonstrated by our initial experimental results in Section 4.5.

3

The general algorithm

In this section, we describe an algorithm which, given a graph G together with a nice tree
decomposition (T, D) of G of width at most w, solves F-Free Edge Deletion on input G in
r
time 2O(|F |w ) n. Since there exist linear-time algorithms both to compute a tree-decomposition
8

of any graph G of fixed treewidth w, and to transform an arbitrary tree decomposition into a
nice tree decomposition, this in fact gives an algorithm which takes as input just a graph G of
treewidth at most w. Thus, we prove the following theorem.
r

Theorem 3.1. There exists an algorithm to solve F-Free Edge Deletion in time 2O(|F |w ) n on
an input graph with n vertices whose treewidth is at most w, if every element of F has at most
r vertices.
As with many algorithms that use tree decompositions, our algorithm works by recursively
carrying out computations for each node of the tree, using the results of the same computation
carried out on any children of the node in question. In this case, we recursively compute the
signature of each node: we define the signature of a node in Section 3.1. It is then possible to
determine whether we have a yes- or no-instance to the problem by examining the signature of
the root of T .
We may assume, without loss of generality, that every element of F contains at least one
edge: if some F ∈ F has no edges, then any graph on at least v(F ) vertices will contain a copy
of F (no matter how many edges we delete) so there cannot be a yes-instance with r or more
vertices, and a brute-force approach will achieve the desired time bound on input graphs having
fewer than r vertices.
In Section 3.2, we describe how we compute the signature of a bag indexed by a given
node from the signatures of its children, before discussing the running time and a number of
extensions in Section 3.3.

3.1

The signature of a node

In this section we describe the information we must compute for each node, and define the signature of a node. Throughout the algorithm, we need to record the possible states corresponding
to a given bag. A valid state of a bag D(t) is a pair consisting of:
1. a spanning subgraph H of G[D(t)] which does not contain any F ∈ F as a subgraph, and
2. a function φ : XF ,H → {0, 1} (where XF ,H consists of all pairs (F ′ , θ) such that F ′ is an
induced subgraph of some F ∈ F and θ is an embedding into H of some induced subgraph
F ′′ of F ′ ) which satisfies the following conditions:
(a) φ(F ′ , θ) = 1 whenever θ is an embedding of F ′ into H;
(b) if φ(F1 , θ) = 1 and F2 is an induced subgraph of F1 then φ(F2 , θ|V (F2 ) ) = 1;
(c) if φ(F1 , θ) = 1 (where F1 is an induced subgraph of F ∈ F and θ is an embedding of
F1′ into H) then, if there exist v ∈ V (H) \ Im(θ) and u ∈ V (F ) \ V (F1 ) such that,
for every w ∈ V (F1 ) with uw ∈ E(F ),
• w ∈ F1′ , and
• θ(w)v ∈ E(H),
b = 1, where θb extends θ by mapping u to v.
then φ(F [V (F1 ) ∪ {u}], θ)

(d) for every F ∈ F and every θ, φ(F, θ) = 0.

Intuitively, the state of a node tells us which forbidden subgraphs appear in G[Vt ] (and
where these appear), so we know which partial forbidden subgraphs we must avoid extending
to full copies of these graphs. Conditions 2(b) and 2(c) are to ensure consistency, so that if a
particular partial embedding of a forbidden subgraph is present then the appropriate extensions
and restrictions of this embedding are also present.
9

For any bag D(t), we denote by st(t) the set of possible states of D(t). Note that there
2
are at most 2w possible spanning subgraphs H, since |D(t)| ≤ w + 1 (as the treewidth of
w+1
2
G is w) and 2( 2 ) ≤ 2w . For any given spanning subgraph H and any F ′′ which is an
induced subgraph of some F ∈ F (with v(F ′′ ) ≤ v(H)), the number of embeddings of F ′′
into H is at most the number of injective functions from V (F ′′ ) to V (H), which is equal to
v(H)!
v(F ′′ ) ≤ (w +1)v(F ′′ ) ; summing over all possibilities for F ′′ , we have that the
(v(H)−v(F ′′ ))! < v(H)
total number of pairs (F ′ , θ) such that F ′′ is an induced subgraph of F ′ and θ is a an embedding
of F ′′ into H is at most
X

F ∈F

X

F ′ an induced
subgraph of F

X

(w + 1)v(F

′′ )

=

F ′′ an induced
subgraph of F ′

 
i 
X) X
X v(F
v(F )
i

F ∈F i=1 j=1

i

j

(w + 1)j

X v(F
X) v(F )
≤
(w + 2)i
i
F ∈F i=1
X
≤
(w + 3)v(F )
F ∈F

≤ |F|(w + 3)r .

Not all such pairs will belong to XF ,H , as they may not obey the condition on edges, but this
certainly provides an upper bound on |XF ,H |. The number of possibilities for the function φ is
2
r
r
therefore at most 2|F |(w+3) . Overall, this gives an upper bound of 2w +|F |(w+3) on the number
of valid states for each bag. Note that, since every element of F has at most r vertices, the
i
P
2
cardinality of F is at most ri=2 2(2) < 2r , so we can bound the number of valid states by
2w

2 +2r 2 (w+3)r

.
Given any state, we make the following definition.

Definition 1. Let σ = (H, φ) ∈ st(t). Then E(t, σ) is be the set of edge-sets E ′ ⊂ E(G[Vt ])
ft = G[Vt ] \ E ′ has the following properties:
such that G
ft [D(t)] = H,
1. G

ft does not contain any F ∈ F as a subgraph, and
2. G

ft and
3. for every F ∈ F and every subgraph F ′ of F , if θ is an embedding of F ′ into G
′
′
θ(V (F )) ∩ D(t) 6= ∅ then φ(F , θ|D(t) ) = 1.

Note that, whenever σ is a valid state for t, the set E(t, σ) will be non-empty: setting
E ′ = E(G[Vt ]) will always satisfy all three conditions, since every F ∈ F contains at least one
edge.
Since we are interested in determining whether it is possible to delete at most k edges to
obtain a graph that does not contain any element of F as a subgraph, we will primarily be
interested in a subset of E(t, σ): for any node t and σ ∈ st(t) we define this subset as
Ek (t, σ) = {E ′ ∈ E(t, σ) : |E ′ | ≤ k}.
We then define
delk (t, σ) =

min

E ′ ∈Ek (t,σ)

|E ′ |,

adopting again the convention that the minimum, taken over an empty set, is equal to infinity.
To simplify notation, given any a, b ∈ N, we define [a]≤b to be equal to a if a ≤ b, and equal
10

to ∞ otherwise. Finally, we define the signature of a node t to be the function sigt : st(t) →
{0, 1, . . . , k, ∞} such that sigt (σ) = delk (t, σ).
Our input graph is then a yes-instance to F-Free Edge Deletion if and only if there
exists some σ ∈ st(tr ) such that sigtr (σ) ≤ k, where tr is the root of the tree indexing the
decomposition.

3.2

Computing signatures recursively

In this section we describe how the signature of any given node in a nice tree decomposition can
be determined from the signatures of its children (if any). This relationship depends on the type
of node under consideration, and we will again discuss each type of node in turn, describing
how to compute delk (t, σ) for an arbitrary state σ.
Leaf nodes
ft
Note that, in this case, we have Vt = D(t), and hence for any state σ = (H, φ) a graph G
ft . Thus
satisfies the conditions of Definition 1 if and only if H = G
h
i
ft ) − e(H)
delk (t, σ) = e(G
.
≤k

Introduce nodes

Suppose that the introduce node t has child t′ , and that D(t) \ D(t′ ) = {v}. Given a state σ ∈
st(t), we define the introduce-inherited state of t′ with respect to σ to be the state σ ′ = (H ′ , φ′ ),
where H ′ = H \ v and for all (F ′ , θ) ∈ XF ,H ′ we have φ′ (F ′ , θ) = φ(F ′ , θ). It is clear that σ ′
does indeed belong to st(t′ ).
We make the following claim concerning the signatures of t and t′ ; recall that dG (v) denotes
the degree of the vertex v in the graph G.
Lemma 3.2. Let t be an introduce node with child t′ , and let σ = (H, φ) ∈ st(t). Then


delk (t, σ) = delk (t′ , σ ′ ) + dG[D(t)] (v) − dH (v) ≤k ,

where σ ′ is the introduce-inherited state of t′ with respect to ω.

Proof. Observe first that the edges incident with v in any set E ′ ∈ E(t, σ) must be precisely the
set Ev = {uv ∈ G[Vt ] : uv ∈
/ E(H)}. We shall in fact demonstrate that

E(t, σ) = Ev ∪ E ′ : E ′ ∈ E(t′ , σ ′ ) ,

and hence that


Ek (t, σ) = Ev ∪ E ′ : E ′ ∈ Ek (t′ , σ ′ ), and |Ev ∪ E ′ | ≤ k .

The result will then follow immediately by taking the minimum cardinality of an element in
this set, using the observation that Ev is disjoint from every E ′ ∈ Ek (t′ , σ ′ ).
b ∈ E(t, σ): we claim E
b\
We first show that E(t, σ) ⊆ {Ev ∪ E ′ : E ′ ∈ E(t′ , σ ′ )}. Let E
′
′
′
′
′
′
Ev ∈ E(t , σ ), where σ = (H , φ ) is the introduce-inherited state of t with respect to σ. Set
ft = G[Vt ] \ E.
b It suffices to check that G
ft [Vt′ ] satisfies the three conditions of Definition 1.
G
The first condition is trivially satisfied, by definition of σ ′ , and the second follows immediately
b ∈ E(t, σ) and hence G
ft does not contain any F ∈ F as a subgraph.
from the fact that E
For the third condition, suppose that F ′ is an induced subgraph of some F ∈ F and that θ
11

ft and
ft [Vt′ ]. In this case θ is also an embedding of F ′ into G
is an embedding of F ′ into G
′
′
b
so (since E ∈ E(t, σ)) we must have φ(F , θ) = 1; hence, by definition of σ , we see that
ft [Vt′ ] satisfies the conditions of Definition 1 and we conclude
φ′ (F ′ , θ) = 1, as required. Thus G
′
′
that E(t, σ) ⊆ {Ev ∪ E : E ∈ E(t′ , σ ′ )}, as required.
Conversely, we now show that {Ev ∪ E ′ : E ′ ∈ E(t′ , σ ′ )} ⊆ E(t, σ). Let E ′ ∈ E(t′ , σ ′ ),
where σ ′ = (H ′ , φ′ ) is the introduce-inherited state of t′ with respect to σ; we claim that
ft = G[Vt ] \ (E ′ ∪ Ev ). It suffices to demonstrate
ft ′ = G[Vt′ ] \ E ′ , and let G
Ev ∪ E ′ ∈ E(t, σ). Set G
ft satisfies the conditions of Definition 1.
that G
The first condition holds by definition. For the second condition, suppose for a contradiction
ft contains a copy of some F ∈ F; let ψ be an embedding of F into G
ft . Since E ′ ∈ E(t′ , σ ′ ),
that G
′
ft , so ψ must map some vertex of F to v. It follows
we know that F is not a subgraph of G
ft ′ and hence by definition of E(t′ , σ ′ ) we must
that ψ|Vt′ is an embedding of some F ′ ⊂ F into G
have φ′ (F ′ , ψ|Vt′ ) = 1. By definition of σ ′ we then have φ(F ′ , ψ|Vt′ ) = 1 and hence, by condition
2(c) in the definition of a valid state, we would also have φ(F, ψ) = 1 (since the properties of
the tree decomposition ensure that every neighbour of ψ −1 (v) in F must belong to D(t′ )). It
then follows that σ is not a valid state for t (by condition 2(d) of the definition of a valid state),
giving the required contradiction.
For the third condition, suppose that F ∈ F, F ′ is an induced subgraph of F , and θ is
ft . If v ∈
ft ′ so, since
an embedding of F ′ into G
/ θ(F ′ ) then θ is an embedding of F ′ into G
E ′ ∈ E(t′ , σ ′ ), we know that φ′ (F ′ , θ) = 1; by the definition of σ ′ it follows that φ(F ′ , θ) = 1, as
required. Thus we may assume that v ∈ θ(F ′ ); suppose that u = θ −1 (v). In this case we see
ft ′ , so by definition of E(t′ , σ ′ ) we must have
that θ|V (F ′ )\{u} is an embedding of F ′ \ u into G
φ′ (F ′ \ u, θ|V (F ′ )\{u} ) = 1 and hence by definition of σ ′ we have φ(F ′ \ u, θ|F ′ \u ) = 1. Since we
know σ is a valid state for t, it then follows from condition 2(c) in the definition of a valid state
that we must also have φ(F ′ , θ) = 1, as required.
fv } ⊆ E(t, σ), and hence
This completes the argument that {Ev ∪ E ′ : E ′ ∈ E(t′ , σ ′ ), Ev ⊆ E
the proof.
Forget nodes
Suppose that the forget node t has child t′ , and that D(t′ ) \ D(t) = {v}. In this case, we need
to consider the set of forget-inherited states for t′ . Given σ = (H, φ) ∈ st(t), we write σ[t′ ]fgt
for the set of states (H ′ , φ′ ) ∈ st(t′ ) satisfying:
1. H ′ [D(t)] = H, and
2. φ−1 (1) = {(F ′ , θ|D(t) ) : (F ′ , θ) ∈ (φ′ )−1 (1)}.
We make the following claim concerning the signatures of t and t′ .
Lemma 3.3. Let t be a forget node with child t′ , let σ = (H, φ) ∈ st(t), and let σ[t′ ]fgt be the
set of forget-inherited states of t′ . Then
delk (t, σ) =

min

σ′ ∈σ[t′ ]fgt

delk (t′ , σ ′ ).

Proof. We shall in fact demonstrate that
E(t, σ) =

[

σ′ ∈σ[t′ ]fgt

12



E(t′ , σ ′ ) ,

and hence that
Ek (t, σ) =

[

σ′ ∈σ[t′ ]fgt



Ek (t′ , σ ′ ) ,

from which the result will follow immediately by taking the minimum cardinality of an element
in each set.
S
We begin by showing that σ′ ∈σ[t′ ]fgt {E(t′ , σ ′ )} ⊆ E(t, σ). Suppose that E ′ ∈ E(t′ , σ ′ ) for
some σ ′ ∈ σ[t′ ]fgt ; we must verify that E ′ also satisfies the three conditions of Definition 1.
ft = G[Vt ] \ E ′ . The first two conditions follow trivially from the
Note that Vt = Vt′ , and set G
definition of σ[t′ ]fgt and the fact that E ′ ∈ E(t′ , σ ′ ). For the third condition, observe that if θ
ft then we must have φ′ (F ′ , θ|D(t′ ) ) = 1 and hence, by definition of
is an embedding of F ′ into G
σ[t′ ]fgt we also have φ(F ′ , θ|D(t) ) = 1, as required.
S
b ∈ E(t, σ). We claim
Conversely, we now argue that E(t, σ) ⊆ σ′ ∈σ[t′ ]fgt {E(t′ , σ ′ )}. Let E
b and let
b ∈ E(t′ , σ ′ ). Set G
ft = G[Vt ] \ E
b = G[Vt′ ] \ E,
that there exists σ ′ ∈ σ[t′ ]fgt such that E
ft [D(t′ )] and, for every (F ′ , θ) ∈ XF ,H , we have φ′ (F ′ , θ) = 1 if and
σ ′ = (H ′ , φ′ ) where H ′ = G
′
only if φ(F , θ|D(t) ) = 1. It is straightforward to verify that (H ′ , φ′ ) ∈ σ[t′ ]fgt . We must verify
ft satisfies the three conditions of Definition 1. The first condition is trivially satisfied by
that G
b ∈ E(t, σ). For the third condition,
our choice of σ ′ , and the second follows from the fact that E
′
ft ; it follows that φ(F ′ , θ|D(t) ) = 1 and also that θ|D(t′ )
suppose that θ is an embedding of F into G
is an embedding of F ′ into H ′ so, by definition of φ′ , we also have φ′ (F ′ , θ|D(t′ ) ) = 1, as required.
′
′
b ∈ E(t′ , σ ′ ), completing the argument that E(t, σ) ⊆ S ′
Thus we see that E
σ ∈σ[t′ ]fgt {E(t , σ )}
and hence the proof.
Join nodes
Suppose that the join node t has children t1 and t2 . Note that st(t1 ) = st(t2 ) = st(t). In this
case, we need to consider a set of pairs of inherited states for the two children t1 and t2 . We
write st(t1 , t2 ) for the Cartesian product st(t1 ) × st(t2 ) and, given any state σ = (H, φ) ∈ st(t),
we write σ[t1 , t2 ]join for the set of pairs of join-inherited states ((H1 , φ1 ), (H2 , φ2 )) ∈ st(t1 , t2 )
satisfying:
1. H1 = H2 = H, and
2. for every (F ′ , θ) ∈ φ−1 (0), and all induced subgraphs F1 and F2 of F ′ such that V (F1 ) ∪
V (F2 ) = V (F ′ ) and V (F1 )∩V (F2 ) = Dom(θ), either φ1 (F1 , θ|V (F1 ) ) = 0 or φ2 (F2 , θ|V (F2 ) ) =
0.
We now make the following claim about the signature of t and those of t1 and t2 .
Lemma 3.4. Let t be a join node with children t1 and t2 , and let σ = (H, φ) ∈ st(t). Then




delk (t, σ) =  min {delk (t1 , σ1 ) + delk (t2 , σ2 ) − (e(G[D(t)]) − e(H))
(σ1 ,σ2 )∈
σ[t1 ,t2 ]join

Proof. We will demonstrate that
[
E(t, σ) =

{E1 ∪ E2 : E1 ∈ E(t1 , σ1 ), E2 ∈ E(t2 , σ2 )},

(σ1 ,σ2 )∈σ[t1 ,t2 ]join

13

.

≤k

and hence that
Ek (t, σ) =

[

{E1 ∪ E2 : E1 ∈ Ek (t1 , σ1 ), E2 ∈ Ek (t2 , σ2 ), |E1 ∪ E2 | ≤ k}.

(σ1 ,σ2 )∈σ[t1 ,t2 ]join

Notice that, for any E1 ∈ E(t1 , σ1 ) and E2 ∈ E(t2 , σ2 ) the properties of the tree decomposition
ensure that E1 ∩ E2 = E(G[D(t)]) \ E(H), so the result will follow immediately by taking the
minimum cardinality of an element
S from each set.
We first show that E(t, σ) ⊇ (σ1 ,σ2 )∈σ[t1 ,t2 ]join {E1 ∪ E2 : E1 ∈ E(t1 , σ1 ), E2 ∈ E(t2 , σ2 )}.
Let (σ1 , σ2 ) ∈ σ[t1 , t2 ]join , and suppose that E1 ∈ E(t1 , σ1 ) and E2 ∈ E(t2 , σ2 ); we claim that
ft = G[Vt ] \ (E1 ∪ E2 ) satisfies the three conditions
E1 ∪ E2 ∈ E(t, σ). It suffices to show that G
of Definition 1.
The first condition is trivially satisfied. For the second and third conditions suppose that,
ft . Write
for some F ∈ F, F ′ is an induced subgraph of F and θ is an embedding of F ′ into G
′
′
′
Fi for F [Vti ] (for i ∈ {1, 2}) and note that θ|Vti is an embedding of Fi into G[Vti ]; thus, as
Ei ∈ E(ti , σi ) we must have φi (Fi′ , θ|Vti ) = 1. Since V (F ′ ) = V (F1′ ) ∪ V (F2′ ), and θ −1 (θ(V (F ′ )) ∩
D(t)) = V (F1′ ) ∩ V (F2′ ), it follows from the definition of σ[t1 , t2 ]join that φ(F ′ , θ|D(t) ) = 1. This
demonstrates that the third condition is satisfied. To see that the second condition is also
satisfied, observe that if F ′ = F then we would by the reasoning above have φ(F, θ|D(t) ) = 1,
contradicting the fact that σ is a valid state, so we see that the second condition must also be
satisfied. Thus we see that E1 ∪ E2 ∈ E(t, σ), S
as required.
Conversely, we now show that E(t, σ) ⊆ (σ1 ,σ2 )∈σ[t1 ,t2 ]join {E1 ∪ E2 : E1 ∈ E(t1 , σ1 ), E2 ∈
b ∈ E(t, σ), and set G
ft = G[Vt ] \ E;
b we also let Ei = E
b ∩ E(G[Vt ]) for i ∈ {1, 2}.
E(t2 , σ2 )}. Let E
i
′
Now set σi = (H, φi ) where φi (F , θ) = 1 if and only if θ can be extended to an embedding of
ft [Vt ].
F ′ into G
i
To verify that (σ1 , σ2 ) ∈ σ[t1 , t2 ]join suppose, for a contradiction, that there exists (F ′ , θ) ∈
φ−1 (0), and induced subgraphs F1 and F2 of F ′ such that V (F1 ) ∪ V (F2 ) = V (F ′ ) and V (F1 ) ∩
V (F2 ) = Dom(θ), and φ1 (F1 , θ|V (F1 ) ) = φ2 (F2 , θ|V (F2 ) ) = 1. By definition of φ1 , φ2 it then
ft [Vt ]; note
follows (for i ∈ {1, 2}) that θ|V (Fi ) can be extended to an embedding θi of Fi into G
i
−1
that θ1 and θ2 agree on V (F1 ) ∩ V (F2 ) and hence on all vertices of θ (D(t)). We can therefore
define θb to be the injective function which agrees with both θ1 and θ2 on their respective
ft and so (as we are assuming
domains. It is clear that θb defines an embedding of F ′ into G
b D(t) ) = 1; however, by
ft satisfies the conditions of Definition 1) we must have φ(F ′ , θ|
that G
b D(t) = θ, so we have φ(F ′ , θ) = 1, contradicting our initial assumption. We may
definition, θ|
therefore conclude that (σ1 , σ2 ) ∈ σ[t1 , t2 ]join .
We now proceed to show that Ei ∈ E(ti , σi ) for each i ∈ {1, 2}. It suffices to demonstrate
ft [Vt ] satisfies the conditions of Definition 1. The first two conditions
that each G[Vti ] \ Ei = G
i
are trivially satisfied. For the third condition, suppose that F ′ is an induced subgraph of some
ft [Vt ]; it follows immediately from the definition
F ∈ F and that θ is an embedding of F ′ into G
i
′
of φi that φi (F , θ|D(t1 ) ) = 1, as required.
S
This completes the argument that (σ1 ,σ2 )∈σ[t1 ,t2 ]join {E1 ∪E2 : E1 ∈ E(t1 , σ1 ), E2 ∈ E(t2 , σ2 )} ⊆
E(t, σ), and hence the proof.

3.3

Running time and extensions

Observe that we can precompute the list of all valid states for a given node t of the tree
decomposition, as this depends only on the subgraph G[D(t)], for which there are at most
w+1
2
2( 2 ) < 2w possibilities. To find the set of valid states for a bag which induces a given subgraph
in G, we first determine all possibilities for H: this must be a spanning subgraph of G[D(t)],
14

2

and there are most 2w possibilities. Next, we determine the set XF ,H of pairs (F ′ , θ) such
that F ′ is an induced subgraph of some F ∈ F and θ is an embedding into H of some induced
subgraph F ′′ of F ′ ; to do this, we consider each of the at most |F|(w + 3)r possible pairs (F ′ , θ)
(as described in Section 3.1), and verify in time at most O(w2 ) for each such possibility whether
θ does indeed define an embedding. Finally, for each possible function φ : XF ,H → {0, 1}
r
(of which there are at most 2|F |(w+3) ), we must determine whether conditions 2(a)-(d) in the
definition of a valid state are satisfied: conditions (a) and (d) can each be checked in constant
time, whereas (b) requires time at most O(2r ) (to consider every possible induced subgraph of
some F1 ∈ F, which can have at most r vertices) and (c) requires time at most O(wr 2 ) (to
consider every possible choice of a pair of vertices u ∈ V (F ) \ V (F1 ) and v ∈ V (H) \ Im(θ), and
to verify that extending the mapping preserves all edges in F that are incident with u). Thus
we can generate a lookup table of the valid states for any given node in time

 2

r
r
2
= 2O(|F |w ) .
O 2w · 2w |F|(w + 3)r · w2 + 2|F |(w+3) 2r + wr 2

Moreover, we can also precompute, for each possible state σ = (H, φ), the corresponding
introduce-inherited state and sets of forget-inherited and join-inherited states.
For an introduce node, there is a single introduce-inherited state for the child node, and this
can clearly be computed in time O(|XF ,H ′ |) = O(|F(w + 3)r ).
For a forget node, we need to consider all valid states σ ′ = (H ′ , φ′ ) for the child. We can first
verify that H and H ′ have the correct relationship (taking time at most O(w2 )), then we compute
the set {(F ′ , θ|D(t) ) : (F ′ , θ) ∈ (φ′ )−1 (1)} (taking time at most O(|XF ,H ′ |) = O(|F|(w+3)r )) and
verify (in time O(|XF ,H |)) that this is equal to φ−1 (1). Thus the total time required to compute
r
2
r
the set of forget-inherited states with respect to σ is O(2w +|F |(w+3) w2 |F|(w + 3)r ) = 2O(|F |w ) .
For a join node, we need to consider all pairs of valid states (σ1 , σ2 ) for the children, where
σi = (Hi , φi ). We can first verify that H1 = H2 = H in time O(w2 ). For the condition on φ,
φ1 and φ2 , we consider each (F ′ , θ) ∈ XF ,H , determine all possibilities for F1 and F2 so that
V (F1 ) ∪ V (F2 ) = V (F ) (of which there are at most 3r , as each vertex of F ′ belongs to either F1 ,
F2 or both) and then verify in constant time whether the condition is satisfied for this choice
of (F ′ , θ) and (F1 , F2 ). Thus the total time required to compute the set of join-inherited states
r
2
r
with respect to σ is O((2w +|F |(w+3) )2 w2 |F|(w + 3)r 3r ) = 2O(|F |w ) .
r
Hence we can perform all precomputation in time 2O(|F |w ) . Having precomputed the sets
of states we then, at each of the O(n) nodes of the nice tree decomposition, iterate over all
2
r
of the valid states for the node, of which there are at most 2w +|F |(w+3) . For each possible
2
r
state of a given node, we will need to consider a collection of at most 22(w +|F |(w+3) ) inherited
states (or pairs of states, in the case of a join node) of the child node(s), and to perform various
constant-time operations for each such state. At each of the O(n) nodes we therefore do


r
2
r
O 23(w +|F |(w+3) ) = 2O(|F |w )
r

work, so this phase of the computation requires time 2O(|F |w ) n, and the overall time complexity
r
r
of the algorithm is therefore 2O(|F |w ) n. We can bound the size of F by 22 , to obtain an upper
bound on the running time that depends only on n, w and r.
It is straightforward to adapt the algorithm to solve the related problem in which we wish
to delete edges to that the resulting graph contains no induced copy of any F ∈ F: we simply
consider strong embeddings instead of embeddings, and make analogous changes to the definition
of a valid state. This does not change the running time as a function of n, w and |F|, but for
monotone properties we would typically need to consider a larger set of forbidden induced
subgraphs than forbidden subgraphs, resulting in an increased running time.
15

For simplicity, we have only described the most basic version of the algorithm. However,
it is straightforward to extend it to deal with a more realistic situation in which the cost of
deleting different edges may vary: in
Pthis case, given a cost function f : E(G) → N, we instead
define delk (t, σ) to be minE ′ ∈E(σ,t) e∈E ′ f (e). Additionally, if we wish to output an optimal
set of edges to delete, we can simply record, for each node t and each state σ ∈ st(t), a set of
edges E ′ ∈ Ek (t, σ) such that |E ′ | = delk (t, σ) (note that in general there may be many such
optimal sets); computing such a set from the relevant sets for the node’s children requires only
basic set operations. An element of E(tr , σ), where tr is the root of the tree decomposition
and delk (tr , σ) = minσ∈st(tr ) is then an optimal solution for the problem. Neither of these
adaptations changes the asymptotic running time of the algorithm.

A specialised algorithm for Th+1-

4

Free Edge Deletion

In this section, we turn our attention to the special case of Th+1 -Free Edge Deletion and
describe a more efficient algorithm for this important special case of the problem. Specifically,
we prove the following theorem.
Theorem 4.1. There exists an algorithm to solve Th+1 -Free Edge Deletion in time O((wh)2w n)
on an input graph with n vertices whose treewidth is at most w.
The general strategy is very similar to that employed in our general algorithm, but in this
special case we can determine whether our input graph is a yes- or no-instance without using all
of the information contained in the signature of the root of the tree indexing the decomposition.
Instead we can record an abridged component-signature for each node, reducing the overall
running time of the algorithm.
This relies on two key observations. Firstly, an optimal solution will never delete an edge
uv if there remains another path from u to v, so it suffices to record which vertices in a bag are
permitted to belong to the same component, rather than the exact subgraph induced by the
bag. Secondly, we do not need to know precisely which partial forbidden subgraphs intersect
the bag and how, rather just the size of the component that contains each vertex of the bag.
We define the component-signature of a node in Section 4.1, before describing mathematically how we compute the component-signature of a bag indexed by a given node from the
signatures of its children in Section 4.2, and discussing the running time and a number of extensions in Section 4.4. As this algorithm achieves a faster running time and answers a question
of particular interest from the point of view of our epidemiological application, the specialised
algorithm is likely to be of more practical use than the general algorithm described in Section
3; we express the procedure in pseudocode in Section 4.3, and give some initial experimental
results on its application to cattle trading networks in Section 4.5.

4.1

The component-signature of a node

In this section, we describe the information we compute for each node, and define the componentsignature of a node.
Throughout the algorithm, we need to record the possible component-states corresponding
to a given bag. A valid component-state of a bag D(t) is a pair consisting of:
1. a partition P of D(t) into disjoint, non-empty subsets or blocks of size at most h, and
2. a function c : P → [h] such that, for each X ∈ P, |X| ≤ c(X).

16

We will write u ∼P v to indicate that u and v belong to the same block of P.
Intuitively, P tells us which vertices are allowed to belong to the same component of the
graph we obtain after deleting edges and c tells us the maximum number of vertices which are
permitted in components corresponding to a given block of the partition.
For any bag D(t), we denote by cst(t) the set of possible component-states of D(t). Note
that there are at most Bw partitions of a set of size w (where Bw is the wth Bell number)
and at most hw functions from a set of size at most w to [h]; thus the total number of valid
component-states for D(t) is at most Bw hw < (wh)w (although not all possible combinations of
a partition and a function will give rise to a valid component-state).
Given any component-state, we make the following definition.
Definition 2. Let σ = (P, c) ∈ cst(t). Then E c (t, σ) is the set of edge-sets E ′ ⊂ E(G[Vt ]) such
ft = G[Vt ] \ E ′ has the following properties:
that G
ft :
1. for each connected component C of G
(a) |V (C)| ≤ h, and

(b) if Ct = V (C) ∩ D(t) 6= ∅, then Ct is contained in a single block XC of P,
ft that
2. for each block X in P, the total number of vertices in connected components of G
intersect X is at most c(X).

Note that, whenever σ is a valid component-state for t, the set E c (t, σ) will be non-empty:
setting E ′ = E(G[Vt ]) will always satisfy both conditions. Since we are interested in determining
whether it is possible to delete at most k edges to obtain a graph with maximum component
size h, we will (as in Section 3) primarily be interested in a subset of E c (t, σ): for any node t
and σ ∈ cst(t) we define this subset as
Ekc (t, σ) = {E ′ ∈ E c (t, σ) : |E ′ | ≤ k}.
We then define
cdelk (t, σ) =

min

E ′ ∈Ekc (t,σ)

|E ′ |.

Finally, we define the component-signature of a node t to be the function csigt : cst(t) →
{0, 1, . . . , k, ∞} such that csigt (σ) = cdelk (t, σ).
Just as in Section 3, our input graph is a yes-instance to Th+1 -Free Edge Deletion if
and only if there exists some σ ∈ cst(tr ) such that csigtr (σ) ≤ k, where tr is the root of the tree
indexing the decomposition.

4.2

Computing component-signatures recursively

In this section we describe how the component-signature of any given node in a nice tree
decomposition can be determined from the component-signatures of its children (if any). As
before, this relationship depends on the type of node under consideration, and we discuss each
type of node in turn, describing how to compute cdelk (t, σ) for an arbitrary component-state σ.
Leaf nodes
Note that, in this case, we have Vt = D(t), and hence for any component-state σ = (P, c) a
ft satisfies the conditions of Definition 2 if and only if the only edges in G
ft are between
graph G
vertices that belong to the same block of P. Thus
cdelk (t, σ) = [|{uv ∈ E (G[D(t)]) : u 6∼P v}|]≤k .
17

Introduce nodes
Suppose that the introduce node t has child t′ , and that D(t)\D(t′ ) = {v}. Given a componentstate σ = (P, c) ∈ cst(t), where P = {X1 , . . . , Xr } and v ∈ Xr , we denote by σ[t′ ]c-intr the set
of introduce-inherited component-states of t′ . A component-state (P ′ , c′ ) belongs to σ[t′ ]c-intr
if and only if it is a valid component-state for D(t′ ) which additionally satisfies the following
conditions:
1. P ′ = {X1 , . . . , Xr−1 , Y1 , . . . , Ys }, with s ≥ 1 and Y1 ∪ · · · ∪ Ys = Xr \ {v},
P
2. c′ (Xi ) = c(Xi ) for 1 ≤ i ≤ r − 1, and si=1 c′ (Yi ) = c(Xr ) − 1.

We make the following claim concerning the component-signatures of t and t′ .

Lemma 4.2. Let t be an introduce node with child t′ , and let σ = (H, P, c) ∈ cst(t). Then


′ ′
cdelk (t, σ) =
min cdelk (t , σ ) + |{uv ∈ G[Vt ] : u 6∼P v}|
.
σ′ ∈σ[t′ ]c-intr

≤k

Proof. Observe first that the edges incident with v in any set E ′ ∈ E c (t, σ) must contain the set
Ev = {uv ∈ G[Vt ] : u 6∼P v}. As in the proof of Lemma 3.2, it suffices to prove that




[
c
′
′
c ′
′
f
f
E (t, σ) = Ev ∪ E : E ∈
E (t , σ ), Ev ⊆ Ev .


′
′
σ ∈σ[t ]c-intr

fv ∪ E ′ : E ′ ∈
We first show that E c (t, σ) ⊆ {E

S

σ′ ∈σ[t′ ]c-intr

fv }. Let E
b ∈
E c (t′ , σ ′ ), Ev ⊆ E

b \ v ∈ E c (t′ , σ ′ ).
E c (t, σ): we claim that there exists σ ′ ∈ σ[t′ ]c-intr such that E
ft = G[Vt ] \ E,
b and let C be the component of G
ft containing v. Suppose that P =
Set G
X1 , . . . , Xr , with v ∈ Xr , and that C \v has connected components C1 , . . . , Cℓ . We now define P ′
to be the partition {Y1 , . . . , Yr+ℓ−1 } where Yi = Xi for 1 ≤ i ≤ r −1, and Yr+j−1 = V (Cj )∩D(t′ )
for 1 ≤ j ≤ ℓ. We also define c′ : P ′ → [h] by setting
(
c(Xi )
if 1 ≤ i ≤ r − 1
c(Yi ) =
|V (Ci−r+1 )| if r ≤ i ≤ r + ℓ − 1,
and then set σ ′ = (P ′ , c′ ). It is straightforward to verify that σ ′ ∈ σ[t′ ]c-intr . We now claim that
b \ v); we need to verify that G
ft ′
b \ v ∈ E c (t′ , σ ′ ). To prove this claim, we set G
ft ′ = G[Vt′ ] \ (E
E
satisfies the conditions of Definition 2. Condition 1(a) is trivially satisfied, so we consider the
remaining conditions.
ft ′ such that Ct = V (C) ∩
For condition 1(b), suppose that C is a connected component of G
b of G
ft , and we know that
D(t′ ) 6= ∅. Since C is contained in some connected component C
ft is contained in a single block of P, it follows that C must be
every connected component of G
contained in a single block Xi of P. There are now two cases to consider, depending on whether
b so C
b = C), it follows from the definition of P ′
i = r. If we have i 6= r (implying that v ∈
/ C,
that C is contained in the block Yi of P ′ . If, on the other hand, we have i = r, it follows from
the definition of P ′ that there is some j ∈ {1, . . . , ℓ} such that Yr+j−1 = C. Thus the condition
is satisfied in either case.
ft ′ is a
For condition 2, consider a block Y of P ′ . If Y is also a block of P, then (as G
ft ) this condition is trivially true, so suppose that this is not the case. Then, by
subgraph of G
18

ft ′ , and
construction of P ′ , Y = V (C ′ ) ∩ D(t′ ) for some (maximal) connected component C ′ of G
we have c′ (Y ) = |V (C ′ )|, so condition 2 is indeed satisfied.
ft ′ satisfies the conditions of Definition 2, implying that
This completes the argument that G
c ′
′
f
b \ v ∈ E c (t′ , σ ′ ) and hence E
b ∈ {E
fv ∪ E ′ : E ′ ∈ S ′
E
σ ∈σ[t′ ]c-intr E (t , σ ), Ev ⊆ Ev }, as required.
S
fv } ⊆ E c (t, σ).
fv ∪ E ′ : E ′ ∈
E c (t′ , σ ′ ), Ev ⊆ E
Conversely, we now show that {E
′
′
σ ∈σ[t ]c-intr

fv ⊇ Ev , and let E ′ ∈ E c (t′ , σ ′ ) for some σ ′ = (P ′ , c′ ) ∈ σ[t′ ]c-intr (where P ′ = {Y1 , . . . , Yp },
Let E
fv ∪ E ′ ∈ E c (t, σ).
with Yi = Xi for 1 ≤ i ≤ r − 1 and Yr ∪ · · · ∪ Yp = Xr \ {v}). We claim that E
′
ft = G[Vt ] \ (E ′ ∪ Ev ). It suffices to demonstrate that G
ft
ft = G[Vt′ ] \ E ′ , and let G
Set G
satisfies the conditions of Definition 2.
ft . If v ∈
For the first condition, let C be a (maximal) connected component of G
/ C, then
ft so we know that |V (C)| ≤ h, and moreover that if Ct =
C is a connected component of G
V (C) ∩ D(t) 6= ∅ (note that V (C) ∩ D(t) = V (C) ∩ D(t′ ) as v ∈
/ C) then Ct is contained in a
single block Xc of P ′ and hence a single block of P (as P ′ refines P). So it remains to consider
the case that v ∈ C. Let C1 , . . . , Cℓ be the (maximal) connected components of C \ v. Note that
it follows from the properties of a tree decomposition that Ci ∩ D(t′ ) 6= ∅ for each i, as there
must be an edge from v to at least one vertex in each Ci ; suppose that ui ∈ Ci ∩ D(t′ ) for each i.
Then u1 , . . . , uℓ all belong to the same component of H as v, so as σ is a valid component-state
ft ′
for t we must have u1 , . . . , uℓ ∈ Xr . We know that each Ci is a connected component of G
and so V (Ci ) ∩ D(t) must be contained in a single block of P ′ ; since ui ∈ Xr , it must be that
V (Ci ) ∩ D(t′ ) ⊆ Yj for some r ≤ j ≤ p. Thus
[
[
V (C) ∩ D(t) =
(Ci ∩ D(t′ )) ∪ {v} ⊆
Yj ∪ {v} = Xr ,
1≤i≤ℓ

r≤j≤s

so V (C) ∩ D(t) is contained in a single block of P, as required.
For the second condition, let X be a block of P. If v ∈
/ X, then X is also a block of P ′ , and
ft that intersect X are the same as those
moreover the vertices belonging to components of G
′
ft that intersect X, so we are done in this case. Thus we may
belonging to components of G
assume that v ∈ X, and that X \ {v} = Yr ∪ · · · ∪ Yp . Then the number of vertices belonging to
ft that intersect X is exactly one more than the number of vertices belonging
components of G
ft ′ that intersect Yr ∪ · · · ∪ Ys . Thus, the number of vertices belonging to
to components of G
ft that intersect X is at most
components of G
1+

s
X

c(Yi ) = 1 + c(X) − 1 = c(X),

i=r

as required.
S
fv } ⊆ E c (t, σ),
This completes the argument that {Ev ∪E ′ : E ′ ∈ σ′ ∈σ[t′ ]c-intr E c (t′ , σ ′ ), Ev ⊆ E
and hence the proof.
Forget nodes
Suppose that the forget node t has child t′ , and that D(t′ ) \ D(t) = {v}. In this case, we need to
consider the set of forget-inherited component-states for t′ . Given σ = (P, c) ∈ cst(t), we write
σ[t′ ]c-fgt for the set of component-states (P ′ , c′ ) ∈ cst(t′ ) satisfying:
1. P = P ′ \ {v}, and
2. for any block Y in P, if Y \ {v} =
6 ∅, we have c′ (Y ) = c(Y \ {v}).
19

We make the following claim concerning the component-signatures of t and t′ .
Lemma 4.3. Let t be a forget node with child t′ , let σ = (P, c) ∈ cst(t), and let σ[t′ ]c-fgt be the
set of inherited component-states of t′ . Then
cdelk (t, σ) =

min

σ′ ∈σ[t′ ]c-fgt

cdelk (t′ , σ ′ ).

Proof. As in the proof of Lemma 3.3, it suffices to prove that
[
 c ′ ′
E c (t, σ) =
E (t , σ ) .
σ′ ∈σ[t′ ]c-fgt

It is straightforward to verifySthat, whenever E ′ ∈ E c (t′ , σ ′ ) for some σ ′ ∈ σ[t′ ]c-fgt , we also have
E ′ ∈ E c (t, σ), implying that σ′ ∈σ[t′ ]c-fgt {E c (t′ , σ ′ )} ⊆ E c (t, σ). We now argue that we also have
S
b ∈ E c (t, σ). We claim that there exists σ ′ ∈ σ[t′ ]c-fgt
E c (t, σ) ⊆ σ′ ∈σ[t′ ]c-fgt {E c (t′ , σ ′ )}. Let E
b ∈ E c (t′ , σ ′ ).
such that E
b Let C be the (maximal) connected component of G
ft that
ft = G[Vt ] \ E
b = G[Vt′ ] \ E.
Set G
′
contains v. If C ∩ D(t) = ∅, we set P to be the partition obtained from P by adding one
additional block containing only v; if C ∩ D(t) 6= ∅ then this set of vertices must be contained
in a single block X of P, and we set P ′ to be the partition obtained from P by adding v to the
block X.
In the case C ∩ D(t) 6= ∅, there is a unique choice of c′ : P ′ → [h] which will satisfy the
definition of σ[t′ ]c-fgt : we set c′ (X ′ ) = c(X ′ ) for X ′ 6= X, and c′ (X ∪{v}) = c(X). If C ∩D(t) = ∅,
we define for any Y ∈ P ′
(
c(Y )
if Y ∈ P
c′ (Y ) =
|V (C)| if Y = {v}.
We now set σ ′ = (P ′ , c′ ). It is straightforward to verify that σ ′ ∈ σ[t′ ]c-fgt . It remains to
b ∈ E c (t′ , σ ′ ); to do so we will argue that G
ft satisfies all the conditions of
demonstrate that E
Definition 2. Condition 1(a) is trivially satisfied.
ft , and suppose that
For condition 1(b), let C be a (maximal) connected component of G
′
′
′
Ct = V (C) ∩ D(t ) 6= ∅. If Ct = {v} then this condition is trivially satisfied, so we may assume
b ∈ E c (t, σ) that V (C) ∩ D(t) is
that V (C) ∩ D(t) 6= ∅. It then follows from the fact that E
′
contained in a single block of P and hence of P ; if we additionally have v ∈ Ct′ , the construction
of P ′ ensures that v will also belong to this same block of P ′ .
For the second condition, let X be a block of P ′ . If v ∈
/ X then the condition is immediately
c
b
satisfied due to the conditions for E to belong to E (t, σ), so we may assume that v ∈ X. If
X \ v 6= ∅ then, by construction of P ′ , there is some vertex u ∈ D(t) such that u and v lie in the
ft (note also that u ∈ X); hence the total number of vertices in connected
same component of G
components that intersect X \ v is the same as the number in components that intersect X,
and so as X \ {v} is a block of P this number must be at most c(X \ {v}) = c′ (X). Finally,
ft that intersects X is the component C that
if X = {v}, the only connected component of G
′
contains v, and by definition we have c (X) = |V (C)|. So the second condition is satisfied in all
cases.
c ′ ′
b ∈ E c (t′ , σ ′ ), completing the argument that E c (t, σ) ⊆ S ′
Thus we see that E
σ ∈σ[t′ ]c-fgt {E (t , σ )}
and hence the proof.

20

Join nodes
Suppose that the join node t has children t1 and t2 . Note that cst(t1 ) = cst(t2 ) = cst(t). In this
case, we need to consider a set of pairs of inherited component-states for the two children t1 and
t2 . We write cst(t1 , t2 ) for the Cartesian product cst(t1 )×cst(t2 ) and, given any component-state
σ = (P, c) ∈ cst(t), we write σ[t1 , t2 ]c-join for the set of pairs of join-inherited component-states
((P1 , c1 ), (P2 , c2 )) ∈ cst(t1 , t2 ) satisfying:
1. P1 = P2 = P, and
2. for every block X of P, c(X) = c1 (X) + c2 (X) − |X|.
We now make the following claim about the component-signature of t and those of t1 and
t2 .
Lemma 4.4. Let t be a join node with children t1 and t2 , and let σ = (P, c) ∈ cst(t). Then



cdelk (t, σ) = 

min

(σ1 ,σ2 )∈
σ[t1 ,t2 ]c-join


{cdelk (t1 , σ1 ) + cdelk (t2 , σ2 ) − |{uw ∈ E(G[D(t)]) : u 6∼P w}|

.

≤k

Proof. As in the proof of Lemma 3.4, it suffices to prove that
[
E c (t, σ) =
{E1 ∪ E2 : E1 ∈ E c (t1 , σ1 ), E2 ∈ E c (t2 , σ2 )}.
(σ1 ,σ2 )∈σ[t1 ,t2 ]c-join

To do this, we will exploit some simple observations about Vt , Vt1 and Vt2 . Note that Vt =
Vt1 ∪ Vt2 , and that by the properties of tree decompositions we have Vt1 ∩ Vt2 = D(t). Thus, for
any set of vertices U ⊆ Vt , we have
|U | = |U ∩ Vt1 | + |U ∩ Vt2 | − |U ∩ D(t)|.

(1)

Similarly, for any set of edges F ⊆ E(G[Vt ]), we have
|F | = |F ∩ E(G[Vt1 ])| + |F ∩ E(G[Vt2 ])| − |F ∩ E(G[D(t)])|.
(2)
S
We first show that E c (t, σ) ⊆ (σ1 ,σ2 )∈σ[t1 ,t2 ]c-join {E1 ∪ E2 : E1 ∈ E c (t1 , σ1 ), E2 ∈ E c (t2 , σ2 )}.
b ∈ E c (t, σ), and let G
ft = G[Vt ] \ E.
b We set σ1 = (P, c1 ) and σ2 = (P, c2 ) where,
Let E
for X ∈ P and i ∈ {1, 2}, ci (X) is defined to be the total number of vertices in connected
ft [Vt ] that intersect X. It is then straightforward to verify that (σ1 , σ2 ) ∈
components of G
i
b ∩ G[Vt ] and E2 = E
b ∩ G[Vt ], then it follows easily
σ[t1 , t2 ]c-join . Moreover, if we set E1 = E
1
2
b = E1 ∪ E2 , this shows that
that E1 ∈ S
E c (t1 , σ1 ) and E2 ∈ E c (t2 , σ2 ). Since it is clear that E
E c (t, σ) ⊆ (σ1 ,σ2 )∈σ[t1 ,t2 ]c-join {E1 ∪ E2 : E1 ∈ E c (t1 , σ1 ), E2 ∈ E c (t2 , σ2 )}.
S
Conversely, we will now demonstrate that (σ1 ,σ2 )∈σ[t1 ,t2 ]c-join {E1 ∪ E2 : E1 ∈ E c (t1 , σ1 ), E2 ∈
E c (t2 , σ2 )} ⊆ E c (t, σ). To do this, fix (σ1 , σ2 ) ∈ σ[t1 , t2 ]c-join , and let E1 ∈ E c (t1 , σ1 ) and
ft = G[Vt ] \ (E1 ∪ E2 ), we then need to demonstrate that G
ft satisfies
E2 ∈ E c (t2 , σ2 ); setting G
f2 = G[Vt ] \ E2 .
f1 = G[Vt ] \ E1 and G
the three conditions of Definition 2. We also set G
2
1
ft with C ∩ D(t) = ∅ then C is contained
Observe that, if C is a connected component of G
f1 or G
f2 , and so |C| ≤ h. This fact, combined with the fact (demonstrated
entirely in either G
below) that condition 2 is satisfied, shows that condition 1(a) is satisfied.
21

ft , where Ct = V (C) ∩ D(t) 6= ∅.
For condition 1(b), consider a connected component C of G
We will argue that, for any two vertices u, w ∈ V (C), we must have u and w belonging to the
same block of P. Recall that ∼P defines an equivalence relation on D(t). Whenever there is a
f1 , u1 and u2 belong to the same component of G
f1 and hence u1 ∼P u2 ;
path from u1 to u2 in G
f
similarly, if there is a path from u1 to u2 in G2 , we have u1 ∼P u2 . Now consider u, w ∈ V (C).
ft , there is a path P from u to w in
Since u and w belong to the same connected component of G
f
Gt . Let u1 = u, u2 , . . . , ur = w be the vertices of V (P ) ∩ D(t), listed in the order in which they
occur as P is traversed from u to w. Recall from the properties of a tree decomposition that
any path from a vertex in Vt1 \ D(t) to a vertex in Vt2 \ D(t) must pass through D(t). Thus, for
f1
1 ≤ i ≤ r − 1, it follows that the segment of P from ui to ui+1 is entirely contained in either G
f
or G2 , and hence that ui ∼P ui+1 . By transitivity, this implies that u ∼P w, or in other words
that u and w belong to the same block of P, as required.
For the second condition, let X be a block of P, and let C1 , . . . , Cr be the components of
ft that intersect X. We want to show that
G
r
X

|V (Ci )| ≤ c(X).

i=1

(1)

(2)

For each i, set Ci = V (Ci ) ∩ Vt1 and Ci = V (Ci ) ∩ Vt2 . Notice that {C1 ∩ X, . . . , Cr ∩ X} is
(1)
(2)
a partition of X, and moreover that Ci ∩ X = Ci ∩ Ci . Hence
r
X

|V (Ci )| =

i=1

=
=
=

r
X

i=1
r 
X

(2)

∪ Ci |

(1)

(2)

(1)

|Ci | + |Ci | − |Ci

i=1
r
X

i=1
r
X
i=1

Sr

(1)

|Ci

(1)

|Ci | +
(1)

|Ci | +

r
X

i=1
r
X

(2)

|Ci | −


(2)
∩ Ci |

r
X

(1)

|Ci

(2)

∩ Ci |

i=1

(2)

|Ci | − |X|,

i=1

(1)
f1 that intersect
Moreover, it is clear that i=1 Ci is the set of vertices in components of G
Sr
(1)
(1)
(1)
X, so | i=1 Ci | ≤ c1 (X); since the sets C1 , . . . , Cr are clearly disjoint, this implies that
Pr
Pr
(1)
(2)
i=1 |Ci | ≤ c1 (X). Similarly, we have
i=1 |Ci | ≤ c2 (X). Thus we see that
r
X

|V (Ci )| ≤ c1 (X) + c2 (X) − |X| ≤ c(X),

i=1

by definition of σ[t1 , t2 ]c-join , so the second
S condition is satisfied.
This completes the argument that (σ1 ,σ2 )∈σ[t1 ,t2 ]c-join {E1 ∪ E2 : E1 ∈ E c (t1 , σ1 ), E2 ∈
E c (t2 , σ2 )} ⊆ E c (t, σ), and hence the proof.

4.3

Algorithmic formulation

In this section, we have expressed our lemmas for recursively calculating component-signatures
at nodes in a tree decomposition as pseudocode (Algorithms 1 to 5). For convenience, “infinity”
is a single arbitrarily large number; in an implementation this might be the maximum number
possible in the programming system.
22

Algorithm 1 Algorithm generating the set of possible component-states st(t) for bag D(t)
Input: A node t of the nice tree decomposition T , the bag at that node D(t), the graph G,
integer h
Output: A set of component-states st(t)
—————————————————————————————————
states ← ∅
allP artition ← all partitions of D(t) such that each block is of size at most h
for P ∈ allP artition do
allF unctions ← all functions c from P = {X1 , . . . X|P| } to [h] such that c(X) ≥ |X|
for c ∈ allF unctions do
add (P, c) to states
end for
end for
return states

Algorithm 2 Algorithm for finding component-signatures of leaf nodes
Input: A leaf node t of the nice tree decomposition T , the bag at that node D(t), the graph
G
Output: A mapping from component-states to del values for component-states of the node
—————————————————————————————————
delValues ← empty dictionary
allStates ← get all the valid (P, c) component-states using Algorithm 1
for (P, c) in allStates do
if |{uw ∈ e(G[D(t)]) : u 6∼P w}| ≤ k then
delValues[t, (P, c)] ← |{uw ∈ e(G[D(t)]) : u 6∼P w}|
else
delValues[t, (P, c)] ← infinity
end if
end for
return delValues

23

Algorithm 3 Algorithm for finding component-signatures of introduce nodes
Input: An introduce node t of the nice tree decomposition T , the bag at that node D(t), the
graph G, the child t′ of t, and a table delV aluesChild of cdelk values for component-states
of t′
Output: A mapping from component-states to cdelk values for component-states of the node
—————————————————————————————————
delValues ← empty dictionary
allStates ← get all the valid (P, c) component-states using Algorithm 1
for (P = {X1 , . . . , Xr }, c) in allStates do
σ[t′ ]intr ← ∅
ref inements ← all partitions of Xr \v
for {Y1 , . . . , Ys } ∈ ref inements do
P ′ ← {X1 , . . . , Xr−1 , Y1 , . . . , Ys }
allCs ← set of all functions c′ : P ′ → [h] such that c′ (Xi ) = c(Xi ) if 1 ≤ i ≤ r − 1 and
Ps
′
i=1 c (Yi ) = c(Xr ) − 1
for c′ ∈ allCs do
add (P ′ , c′ ) to σ[t′ ]intr
end for
end for
minValue ← infinity
for σ ′ ∈ σ[t′ ]intr do
value ← delValuesChild[t′ , σ ′ ] + |{uv ∈ E(G[D(t)]) : u 6∼P v}|
if value < minValue then
minValue ← value
end if
end for
if minV alue ≤ k then
delValues[t, (P, c)] ← minV alue
else
delValues[t, (P, c)] ← infinity
end if
end for
return delValues

24

Algorithm 4 Algorithm for finding component-signatures of forget nodes
Input: A forget node t of the nice tree decomposition T , the bag at that node D(t), the
graph G, the child t′ of t, and a table delV aluesChild of cdelk values for component-states
of t′
Output: A mapping from component-states to cdelk values for component-states of the node
—————————————————————————————————
delValues ← empty dictionary
allStates ← get all the valid (P, c) component-states using Algorithm 1
for (P, c) in allStates do
σ[t′ ]f gt ← ∅
allP artitions ← all partitions P ′ such that P = P ′ \{v}
for P ′ ∈ allP artitions do
allc′ ← ∅
c′ ← empty function
vSingleton ← false
for Y ∈ P ′ do
if Y \{v} =
6 ∅ then
′
c (Y ) ← c(Y \{v})
else
vSingleton ← true
end if
end for
if not vSingleton then
add c′ to allc′
else
for i = 1 to h do
c′ ({v}) ← i
add c′ to allc′
end for
end if
for P ′ ∈ allP artitions do
for c′ ∈ allc′ do
add (P ′ , c′ ) to σ[t′ ]f gt
end for
end for
end for
minValue ← infinity
for σ ′ ∈ σ[t′ ]f gt do
value ← delValuesChild[t′ , σ ′ ]
if value < minValue then
minValue ← value
end if
end for
if minV alue ≤ k then
delValues[t, (P, c)] ← minV alue
else
delValues[t, (P, c)] ← infinity
end if
end for
return delValues
25

Algorithm 5 Algorithm for finding component-signatures of join nodes
Input: A join node t of the nice tree decomposition T , the bag at that node D(t), the graph
G, the join node’s children t1 , t2 , and a table delV aluesChild of cdelk values for componentstates of t1 and t2
Output: A mapping from component-states to cdelk values for component-states of the node
—————————————————————————————————
delValues ← empty dictionary
allStates ← get all the valid (P, c) component-states using Algorithm 1
for (P, c) in allStates do
σ[t1 , t2 ]join ← ∅
P1 ← P
P2 ← P
allF unctions ← set of all function pairs (c1 , c2 ) such that for every block X ∈ P, c(X) =
c1 (X) + c2 (X) − |X|
for (c1 , c2 ) ∈ allF unctions do
add ((P1 , c1 ), (P2 , c2 )) to σ[t1 , t2 ]join
end for
minValue ← infinity
for (σ1 , σ2 ) ∈ σ[t1 , t2 ]join do
value ← delValuesChild[t1 , σ1 ] + delValuesChild[t2 , σ2 ] - |{uw ∈ E(G[D(t)]) : u 6∼P
w}|
if value < minValue then
minValue ← value
end if
end for
if minValue ≤ k then
delValues[t, (P, c)] ← minValue
else
delValues[t, (P, c)] ← infinity
end if
end for
return delValues

26

4.4

Running time and extensions

At each of the O(n) nodes of the nice tree decomposition, we will generate, and then iterate over, fewer than (wh)w component-states for that node. For each of those componentstates, we will need to consider a collection of at most (wh)w inherited component-states (or
pairs of component-states, in the case of a join node) of the child node(s). In the algorithm,
we first generate each of the component-states for a given node, and the corresponding set
of inherited component-states for its children, then iterate over each relevant combination of
component-states, performing various constant-time operations. Thus, at each of O(n) nodes
we do O (wh)2w work, giving an overall time complexity of O((wh)2w n).
For simplicity, we have only described the most basic version of the algorithm; however, it
is straightforward to extend it to deal with more complicated situations, involving any or all of
the following.
Deleting edges so that the sum of weights of vertices in any component is at most h, where a
weight
function w : V (G) → N is given: change condition 1(a) in the definition of E c (t, σ) to
P
v∈V (C) w(v) ≤ h, and add to the definition of the
P set of valid component-states for a node the
condition that, for each block X of P, we have v∈X w(X) ≤ c(X).

Deleting edges so that each vertex v belongs to a component containing at most ℓ(v) vertices,
where a limit function ℓ : V (G) → N is given: change condition 1(a) in the definition of E c (t, σ)
to |V (C)| ≤ minv∈V (C) ℓ(v), and add to the definition of the set of valid component-states for a
node the condition that, for each block X of P, we have c(X) ≤ minv∈X ℓ(v).
Neither of these adaptations changes the asymptotic running time of the algorithm. It is also
straightforward to deal with different deletion costs for different edges, and to output an optimal
set of edges to delete, as discussed for the general algorithm in Section 3.3.

4.5

Experimental results

As an example of its practical use, we have tested an implementation of our algorithm and a
constraint satisfaction programming (CP) formulation of the problem to find minimum deletions
to maximum components of five vertices on graphs derived from the persistent Scottish trade
links.
We report early preliminary results in Table 1, giving the minimum deletions found by our
algorithm and by the CP, and the time required. For the CP, most of the deletions were not
confirmed to be minimum within 2 hours, but we report the time to this confirmation if it
occurred within the 2 hour running time limit. We use an ensemble CP approach, running
two separate solvers, and reporting the best result within the two hour limit. The first CP
uses the MiniZinc [25] modelling language as a front-end to the Gecode solver [28, 12]. Gecode
was chosen for its ease of use and fast performance: it participates regularly in benchmarking
challenges, and came first in all categories in the MiniZinc Challenge in 2009, 2010, 2011, and
2012 [29]. The second CP uses a custom-written program in the Choco solver [26], a medalist
in the last three MiniZinc Challenges, chosen for its speed and the presence of a local expert.
Neither our algorithm nor the CP solver were successful in finding a minimum deletion
within 24 hours on several of the graphs with higher treewidths (15 and 12), and we do not
report these in the table. In all cases our algorithm is much faster in clock-time than the CP
approach: both could likely be improved by careful optimisation of the implementations.
The implementation of our algorithm takes as input a tree decomposition (generated using
LibTW [7]) of a graph and the graph itself. Our implementation of the tree decomposition-based
27

Table 1: Experimental results for deletion to a maximum component size of 5 comparing the
performance of our tree decomposition based algorithm and the CP method. v(G) is the number
of vertices in the graph, e(G) the number of edges, and tw(G) the treewidth. For our tree
decomposition-based method we report the minimum deletion found and the approximate clock
time to find it. For the CP method we report the minimum deletion found within 2 hours, the
approximate clock time to find it, and the approximate clock time to confirm that deletion is
minimum: a dash in this column indicates that the confirmation that the deletion was minimum
did not complete within 2 hours. The graphs used are a selection of anonymised cattle trading
graphs from Scotland. Times are given in seconds, with times over 30 minutes rounded up to
the nearest hour.
Graph information
Tree decomposition method
CP method
Graph
v(G) e(G) tw(G) Minimum
Minimum
Time
Time Time to
ID
deletion
deletion
confirmafound
found
tion
2010-0
104 110 4
38
53
82
7200
11
4
21
7200
2010-3
45
45
3
20
7
24
3600
2010-4
38
38
3
2010-5
37
40
4
7
64
7
1032
1046
58
7200
93
7200
2012-0
97
119 5
2012-1
72
74
3
20
11
37
7200
12
3
12
1082
2012-4
31
30
2
2012-5
49
52
3
15
7
30
7200
20
35
25
3600
2013-1
45
47
4
19
38
30
7200
2013-3
61
62
4
2013-4
35
38
4
15
5
15
3600
14
4
17
7200
2013-6
39
41
3
28
445
28
3600
2014-0
32
49
4
2014-1
47
47
3
18
6
24
7200
17
10
33
7200
2014-2
57
59
4
2014-3
41
40
2
15
5
18
3600
8
18
8
123
123
2014-5
31
35
4
2014-6
48
49
3
21
11
29
7200
16
4
16
7
2014-7
31
32
3
method can be found at github.com/magicicada/fpt-edge-deletion.

5

Conclusions and open problems

We have investigated the relevance of the well-studied graph parameter treewidth to the structure of real-world animal trade networks, and have provided evidence that this parameter is
likely to be small for many networks of interest for epidemiological applications. Motivated
by this observation, we have derived an algorithm to solve F-Free Edge Deletion on input
r
graphs having n vertices and treewidth bounded by some fixed constant w in time 2O(|F |w ) n,
if no graph in F has more than h vertices. The special case of this problem in which F is the
set of all trees on at most h + 1 vertices is of particular interest from the point of view of the
control of disease in livestock, and we have derived an improved algorithm for this special case,
running in time O((wh)2w n). It is straightforward to adapt both algorithms to deal with more
complicated situations likely to arise in the application.
28

Many open questions remain concerning the complexity of this problem more generally, as
we are far from having a complete complexity classification. We know that useful structure in
the input graph is required to give an fpt-algorithm: we demonstrated that it is not sufficient
to parameterise by the maximum component size h alone (unless P=NP). However, it remains
open whether the problem might belong to FPT when parameterised only by the treewidth
w; we conjecture that treewidth alone is not enough, and that the problem is W[1]-hard with
respect to this parameterisation. Considering other potentially useful structural properties of
input graphs, one question of particular relevance to epidemiology would be the complexity of
the problem on planar graphs: this would be relevant for considering the spread of a disease
based on the geographic location of animal holdings (in situations where a disease is likely to
be transmitted between animals in adjacent fields).
Furthermore, animal movement networks can capture more information on real-world activity when considered as directed graphs, and the natural generalisation of Th+1 -Free Edge
Deletion to directed graphs in this context would be to consider whether it is possible to
delete at most k edges from a given directed graph so that the maximum number of vertices
reachable from any given starting vertex is at most h. Exploiting information on the direction
of movements might allow more efficient algorithms for this problem when the underlying undirected graph does not have very low treewidth; a natural first question would be to consider
whether there exists an efficient algorithm to solve this problem on directed acyclic graphs.

Acknowledgements
The authors would like to thank the following: Ivaylo Valkov for his assistance in developing
an initial implementation of this algorithm as part of a summer research project, and the
Engineering and Physical Sciences Research Council for providing funding for this summer
project; EPIC: Scotland’s Centre of Expertise on Animal Disease Outbreaks, which supported
JE for part of her work on this project; the Royal Society of Edinburgh which supported KM for
part of her work on this project through a Personal Research Fellowship funded by the Scottish
Government; Ciaran McCreesh and Patrick Prosser for their assistance in developing the CP
formulation against which we compared the performance of our algorithm.

References
[1] Anderson, R., Gupta, S., Ng, W.: The significance of sexual partner contact networks for
the transmission dynamics of HIV. Journal of Acquired Immune Deficiency Syndromes
and Human Retrovirology 3, 417–429 (1990)
[2] Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a
k-tree. SIAM J. Alg. Disc. Meth. 8, 277–284 (1987)
[3] Arnborg, S., Lagergren, J., Sesse, D.: Easy problems for tree-decomposable graphs. Journal
of Algorithms 12, 308–340 (1991)
[4] Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small
treewidth. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory
of Computing, STOC ’93, pp. 226–234. ACM, New York, NY, USA (1993). DOI
10.1145/167088.167161
[5] Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996). DOI 10.1016/0020-0190(96)00050-6
29

[6] Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable
graphs. Theoretical Computer Science 109(12), 49 – 82 (1993). DOI 10.1016/0304-3975(93)
90064-Z
[7] van Dijk, T., van den Heuvel, J.P., Slob, W.: Computing treewidth with libtw (2006),
http://www.treewidth.com/treewidth
[8] Drange, P.G., Dregi, M.S., van ’t Hof, P.: On the computational complexity of vertex
integrity and component order connectivity. In: H.K. Ahn, C.S. Shin (eds.) Algorithms
and Computation, Lecture Notes in Computer Science, vol. 8889, pp. 285–297. Springer
International Publishing (2014). DOI 10.1007/978-3-319-13075-023
[9] El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE
Trans. Circuits and Systems 3, 354–362 (1988)
[10] Gao, Y.: Treewidth of Erdős-Renyi random graphs, random intersection graphs, and scalefree random graphs. Discrete Applied Mathematics 160(45), 566 – 578 (2012). DOI
10.1016/j.dam.2011.10.013
[11] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1979)
[12] Gecode Team: Gecode: Generic constraint development environment (2016). Available
from http://www.gecode.org
[13] Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster
parameterized algorithms for deletion to split graphs. In: F. Fomin, P. Kaski (eds.) Algorithm Theory SWAT 2012, Lecture Notes in Computer Science, vol. 7357, pp. 107–118.
Springer Berlin Heidelberg (2012). DOI 10.1007/978-3-642-31155-010
[14] Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical
mapping of DNA. Journal of Computational Biology 2, 139–152 (1993)
[15] Golumbic, M.C.: Algorithmic graph theory and perfect graphs, vol. 57. Elsevier (2004)
[16] Gross, D., Heinig, M., Iswara, L., Kazmierczak, L.W., Luttrell, K., Saccoman, J.T., Suffel,
C.: A survey of component order connectivity models of graph theoretic networks. SWEAS
Trans. Math. 12(9) (2013)
[17] Guo, J.: Problem kernels for NP-complete edge deletion problems: Split and related
graphs. In: T. Tokuyama (ed.) Algorithms and Computation, Lecture Notes in Computer Science, vol. 4835, pp. 915–926. Springer Berlin Heidelberg (2007). DOI 10.1007/
978-3-540-77120-379
[18] Kao, R.R., Green, D.M., Johnson, J., Kiss, I.Z.: Disease dynamics over very different timescales: foot-and-mouth disease and scrapie on the network of livestock movements in the
UK. Journal of The Royal Society Interface 4(16), 907–916 (2007). DOI 10.1098/rsif.2007.
1129
[19] Kloks, T.: Treewidth, Lecture Notes in Computer Science, vol. 842. Springer-Verlag, Berlin
(1994). DOI 10.1007/BFb0045375. Computations and approximations
[20] Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NPcomplete. Journal of Computer and System Sciences 20(2), 219 – 230 (1980). DOI
10.1016/0022-0000(80)90060-4
30

[21] Li, A., Tang, L.: The complexity and approximability of minimum contamination problems.
In: M. Ogihara, J. Tarui (eds.) Theory and Applications of Models of Computation, Lecture
Notes in Computer Science, vol. 6648, pp. 298–307. Springer Berlin Heidelberg (2011).
DOI 10.1007/978-3-642-20877-5\ 30
[22] Margot, F.: Some complexity results about threshold graphs. Discrete Applied Mathematics 49(1:3), 299 – 308 (1994). DOI 10.1016/0166-218X(94)90214-3. Special Volume
Viewpoints on Optimization
[23] Mitchell, A., Bourn, D., Mawdsley, J., Wint, W., Clifton-Hadley, R., Gilbert, M.: Characteristics of cattle movements in britain: an analysis of records from the cattle tracing
system. Animal Science 80, 265–273 (2005). DOI 10.1079/ASC50020265
[24] Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Applied Mathematics 113(1), 109 – 128 (2001). DOI
10.1016/S0166-218X(00)00391-7. Selected Papers: 12th Workshop on Graph-Theoretic
Concepts in Computer Science
[25] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc:
Towards a standard CP modelling language. In: Proceedings of the 13th International
Conference on Principles and Practice of Constraint Programming, CP’07, pp. 529–543.
Springer-Verlag, Berlin, Heidelberg (2007)
[26] Prud’homme, C., Fages, J-G., Lorca,
http://www.choco-solver.org (2016)

X.:

Choco Documentation

Web site

[27] Robertson, N., Seymour, P.: Graph minors. III. planar tree-width. Journal of Combinatorial Theory, Series B 36(1), 49 – 64 (1984). DOI 10.1016/0095-8956(84)90013-3. URL
http://www.sciencedirect.com/science/article/pii/0095895684900133
[28] Schulte, C., Tack, G., Lagerkvist, M.Z.: Modeling and programming with Gecode. Web
site: http://www. gecode. org (2013)
[29] Stuckey, P.J., Feydy, T., Schutt, A., Tack, G., Fischer, J.: The MiniZinc Challenge 20082013. AI Magazine 35(2), 55–60 (2014).
[30] Watanabe, T., Ae, T., Nakamura, A.: On the NP-hardness of edge-deletion and contraction problems. Discrete Applied Mathematics 6(1), 63 – 78 (1983). DOI
10.1016/0166-218X(83)90101-4
[31] Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the
Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pp. 253–264. ACM,
New York, NY, USA (1978). DOI 10.1145/800133.804355

31

