arXiv:1711.05839v3 [cs.DS] 10 Jan 2018

Exact and heuristic algorithms for Cograph
Editing
W. Timothy J. White, Marcus Ludwig and Sebastian Böcker
January 11, 2018
Abstract
We present a dynamic programming algorithm for optimally solving the Cograph Editing problem on an n-vertex graph that runs in
O(3n n) time and uses O(2n ) space. In this problem, we are given a graph
G = (V, E) and the task is to find a smallest possible set F ⊆ V × V of
vertex pairs such that (V, E 4 F ) is a cograph (or P4 -free graph), where 4
represents the symmetric difference operator. We also describe a technique
for speeding up the performance of the algorithm in practice. Additionally, we present a heuristic for solving the Cograph Editing problem
which produces good results on small to medium datasets. In application
it is much more important to find the ground truth, not some optimal
solution. For the first time, we evaluate whether the cograph property is
strict enough to recover the true graph from data to which noise has been
added.

1

Introduction

A cograph, or complement reducible graph, is a simple undirected graph
that can be built from isolated vertices using the operations of disjoint
union and complement. Specifically:
1. A single-vertex graph is a cograph.
2. The disjoint union of two cographs is a cograph.
3. The complement of a cograph is a cograph.
There are several equivalent definitions of cographs [1], perhaps the
simplest to state being that cographs are exactly the graphs that contain
no induced P4 (path on 4 vertices). As a subclass of perfect graphs,
they enjoy advantageous algorithmic properties: many problems that are
NP-hard on general graphs, such as Clique and Chromatic Number,
become polynomial-time for cographs.
Cographs can be recognised in linear time [2]. A more difficult problem arises when we ask for the minimum number of “edge editing” operations required to transform a given graph into a cograph. Three problem
variants can be distinguished: If we may only insert edges, we have the

1

Cograph Completion problem; if we may only delete edges, we have
the Cograph Deletion problem; if we may both insert and delete edges,
we have the Cograph Editing problem. When framed as decision problems, in which the task is to determine whether such a transformation
can be achieved using at most a given number k of operations, all three
problem variants are NP-complete [3, 4]. (Note that the edge completion
and deletion problems can be trivially transformed into each other by taking complements.) A general result of Cai, when combined with lineartime recognition of cographs, directly gives an O(6k n) fixed-parameter
tractable (FPT) algorithm [5] for Cograph Editing; more recently, a
O(4.612k + n4.5 ) FPT algorithm [4] has been described.
Concerning applications, we focus in particular on a recently developed
approach for inferring phylogenetic trees from gene orthology data that
involves solving the Cograph Editing problem [6]. Briefly, in this setting
we may represent genes as vertices in a graph, with pairs of vertices linked
by an edge whenever they are deemed to have arisen through a speciation
(as opposed to gene duplication) event. In a perfect world, this graph
would be a cograph, and its cotree (see below) would correspond to the
gene tree, which can be combined with gene trees inferred from other gene
families to infer a species tree. In the real world, measurement errors—
false positive and false negative inferences of orthology—frequently cause
the inferred orthology graph not to be a cograph, and in this case it is
reasonable to ask for the smallest number k∗ of edge edits that would
transform it into one.
For practical instances arising from orthology-based phylogenetic analysis, it is often the case that k∗ > n or even k∗ = Ω(m), limiting the effectiveness of FPT approaches parameterised by the number of edits and motivating the development of “traditional” exponential-time algorithms—
that is, algorithms that require time exponential in the number of vertices
n. We first give a straightforward dynamic programming algorithm that
solves the more general edge-weighted versions of each of the three problem variants in O(3n n) time and O(2n ) space, and which additionally
offers simple implementation and predictable running time and memory
usage. We then describe modifications that are likely to significantly improve running time in practice, without sacrificing optimality (though also
without improving the worst-case bound). In addition, we describe and
evaluate a heuristic solving the Cograph Editing problem based on an
algorithm by Lokshtanov et al. [7].

1.1

Definitions

Every cograph G = (V, E) determines a unique vertex-labelled tree TG =
(U, D, h : U → {0, 1}) called the cotree of G, which encodes the sequence of
basic operations needed to build G from individual vertices. The vertices
of TG correspond to induced subgraphs of G: leaves in TG correspond to
individual vertices of G, and internal vertices to the subgraphs produced
by combining the child subgraphs in one of two ways, according to whether
the vertex is labelled 0 or 1 by h. 0-vertices specify parallel combinations,
which combine the subgraphs represented by the child vertices into a single graph via disjoint union, while 1-vertices specify serial combinations,

2

which combine these subgraphs into a single graph by adding all possible edges between vertices coming from different children (or equivalently,
by complementing, forming the disjoint union, and then complementing
again). The root is labelled 1, and every path from the root alternates
between 0-vertices and 1-vertices.
Given a cotree TG , a postorder traversal that begins with a distinct
single-vertex graph at each leaf and then applies the series or parallel
combination operations specified at the internal nodes will culminate, at
the root node, in the corresponding cograph G.

2 An O(3n n)-time and O(2n )-space algorithm for weighted cograph editing, completion, and deletion problems
We describe here an algorithm for the weighted version of the Cograph
Editing problem. The deletion and completion problem variants are
dealt with using simple modifications to the base algorithm, described
later. Unweighted variants can of course be obtained by setting all edge
weights to 1.
Given an undirected graph G = (V, E) with V = {v1 , . . . , vn } and
vertex-pair weights given by w : V × V → R≥0 , with the interpretation
that w(u, v) is the cost of deleting the edge (u, v) when (u, v) ∈ E and the
cost of inserting it otherwise, we seek a minimum-weight edge modification
set F ⊆ V ×V such that (V, E 4F ) is a cograph, where 4 is the symmetric
difference operator.
We compute the minimum cost of transforming every subset of vertices
into a cograph using dynamic programming. The algorithm hinges on the
following property of cotrees [8]:
Property 1 In a cograph G, two vertices u and v are linked by an edge if
and only if their lowest common ancestor in the cotree TG of G is a series
node.
For any subset X of vertices in V , let vX denote the vertex with
maximum index in X. We can compute the minimum cost f(X) of editing
the induced subgraph G[X] to a cograph using:
(

if |X| < 4
otherwise
(1)
cost(A, B) = min{parCost(Y, X \ Y ), serCost(Y, X \ Y )}
(2)
X
parCost(A, B) =
w(u, v) (these edges need to be deleted)
f(X) =

0,
minY (X,vX ∈Y (f(Y ) + f(X \ Y ) + cost(Y, X \ Y )),

{(u,v)∈E:u∈A,v∈B}

serCost(A, B) =

X

w(u, v)

(3)
(these edges need to be inserted)

{(u,v)∈E:u∈A,v∈B}
/

(4)

3

Because each invocation of f has a strictly smaller set of vertices as
input, it suffices to compute solutions to subproblems in increasing order
of subset size. To instead solve the edge deletion (respectively, insertion)
problem, replace serCost (respectively, parCost) with a function that is
zero when the original function is zero, and infinity otherwise.
The 3n factor in the time complexity arises from there being at most
one argument to the outer min for every way of partitioning V into 3
parts (V \ X, X \ Y, Y ). If we enumerate bipartitions (Y | X \ Y ) in Gray
code order, then straightforward algorithms for computing parCost and
serCost incrementally may be used, resulting in the additional factor of
n.
An optimal solution can be found by back-tracing the dynamic programming matrix as usual. It is possible to extract every optimal solution
this way, but producing each of them exactly once requires a slight reformulation whereby we include the root node type (series or parallel) in the
dynamic programming state, which doubles the memory requirement.
Although the above is a “subset convolution”-style dynamic program,
the possibility of achieving O∗ (2n ) time by applying the Möbius transform
approach of Björklund et al. [9] appears to be complicated by the third
term in the summation.

3 Reducing the number of partitions considered
Given any subset X of vertices, the dynamic programming algorithm
above enumerates every possible bipartition to find a best one, and thereby
compute f(X). For many graphs encountered in practice, this will be
overkill: The vast majority of bipartitions tried will be very bad, suggesting that there could be a way to avoid trying many of them without
sacrificing optimality. Instead of enumerating all bipartitions of X, we
propose to use a search tree to gradually refine a set of bipartitions defined by a series of weaker constraints, avoiding entire sets of bipartitions
that can be proven to lead to suboptimal solutions. Here we describe
a branch and bound algorithm, running “inside” the dynamic program,
that uses this strategy to find an optimal bipartition of a given vertex
subset X. We however note that, since O(2n ) space is already needed
by the “core” dynamic programming algorithm, and since a full enumeration of all bipartitions of X would require only asymptotically the same
amount of space, an A∗ algorithm is likely feasible. The overall strategy
is somewhat inspired by the Karmarkar-Karp heuristic [10] for number
partitioning, which achieves good empirical performance on this related
problem by deferring as far as possible the question of exactly which part
in the partition to assign an element to.
The basic idea is to maintain, in every subproblem P , a set of constraints SP of the form “A ⊆ X are all in the same part”, and another
set of constraints OP of the form “A ⊆ X and B ⊆ X are in different
parts” (clearly A ∩ B = ∅). We call a constraint of the former kind a
same-constraint and denote it same(A); a constraint of the latter kind

4

we call an opp-constraint and denote it opp(A|B). Each subproblem (except the root; see below) has one extra bit of information λP ∈ {+, −}
that records whether it represents a series (+) or parallel (−) node in the
cotree: we will see later that separating these two cases enables stronger
lower bounds to be used. A subproblem P = (λP , CP ) thus represents
the set of all bipartitions consistent with its constraint set CP = SP ∪ OP
that introduce a series (λP = +) or parallel (λP = −) node in the cotree.
Note that any cotree may be represented as a binary tree with internal
nodes labelled either + or − (though this representation is not unique).
The root subproblem PX for a vertex subset X is special: it has no
associated λ value; rather it has has exactly two children PX + and PX −
having opposite values of λ, with each containing only the trivial constraints CPX + = CPX − = {same({v}) : v ∈ X}. These two children
(which may be thought of as the roots of entirely separate search trees)
thus together represent the set of all possible configurations of X, where
a configuration is a bipartition together with a choice of cotree node type
(series or parallel).

3.1

Generating subproblems

Before discussing the general rule we use for generating subproblems, we
first give a simplified example. If there are two vertices u, v in X that have
not yet been used in any opp-constraint, we may create a new subproblem
in which u and v are forced to be in the same part of the bipartition, as
well as another new subproblem in which they are forced to be in opposite
parts. (Clearly every bipartition in the original subproblem belongs to
exactly one of these two subproblems.)

3.1.1

Structure of a general subproblem

More generally, let SP∗ be the set of all inclusion-maximal subsets of X
appearing in a same-constraint in subproblem P (i.e., SP∗ = {Z ⊆ X :
same(Z) ∈ SP ∧ (@Z 0 ) Z ∧ same(Z 0 ) ∈ SP )}). Then we may choose
two distinct (necessarily disjoint and nonempty) subsets A and B from
SP∗ and form two new subproblems: one in which same(A ∪ B) is added
to the constraint set, and one in which opp(A|B) is added. Each new
subproblem inherits the λ of the original. As before, every bipartition in
the original subproblem belongs to exactly one of these two subproblems.
When no such pair (A, B) can be found, we halt this refinement process
and enumerate all bipartitions consistent with the constraints, evaluating
each as per Equation 1. In this way, the constraint set CP of any subproblem P can be represented as a directed forest, each component of which
is a binary tree that may have either a same(·) node or an opp(·) node at
the root and same(·) nodes everywhere else. The components containing
only same(·) nodes are exactly the members of SP∗ , so a standard unionfind data structure [11] can be used to efficiently find a pair of vertex sets
A, B ∈ SP∗ eligible for generating a new pair of child subproblems.
Although it would be possible and perhaps fruitful to continue adding
constraints of a more complicated form, for example a constraint opp(A|C)
when the constraints opp(A|B) and opp(C|D) already exist in CP , there

5

are several reasons to avoid doing so. First, allowing such constraints
destroys the simple forest structure of constraints in CP . In the presence of such constraints, a new candidate constraint may be tautological
or inconsistent; these cases can be detected (for example using a 2SAT
algorithm), but doing so slows down the process of finding a new candidate constraint to add. Second, any set of constraints containing one or
more such complicated constraints is “dominated” in the sense that some
set of simple constraints exists that implies the same set of bipartitions,
meaning that no additional “power” is afforded by these constraints.

3.2

Strengthening lower bounds

The procedure described above is only useful in reducing the total number of bipartitions considered if the constraints added in subproblems
are able to improve a lower bound on the cost of a solution. The lower
bound
LP associated
with any subproblem P will have the form LP =
P
P
L
(x)
+
∗
S
opp(A|B)∈OP LO (A, B). We now examine the two kinds
x∈SP
of terms in this lower bound, and how they may be efficiently computed
for a subproblem from its parent subproblem.

3.2.1

Lower bounds LS (·) from same-constraints

Whenever two same-constraints same(A) and same(B) are combined into
a single same-constraint same(A ∪ B), we may add f(A ∪ B) − f(A) − f(B)
to the lower bound. This represents the cost of editing the entire vertex
set A ∪ B into a cograph, offset by subtracting the costs already paid for
editing each vertex subset A and B into cographs. Note that any function
computing a lower bound on these costs can be used in place of f, provided
that its value does not change between the time at which it is first added
to the lower bound (at some subproblem), and later subtracted (at some
deeper subproblem). If the bottom-up strategy is followed for computing
f, then we always have these function values available exactly.

3.2.2

Lower bounds LO (·, ·) from opp-constraints

Whenever an opp-constraint opp(A|B) is added to a parallel subproblem,
then for each edge (a, b) ∈ E with a ∈ A and b ∈ B we may add w(a, b) to
the lower bound. This represents the cost of deleting these edges, which
cannot exist if they are in different subtrees of a parallel cotree node by
Property 1. Because the sets of vertices involved in the opp-constraints
of a given subproblem are all disjoint, no edge is ever counted twice. The
reasoning is identical for series subproblems, except that we consider all
vertex pairs (a, b) ∈
/ E: these edges must be added.
In fact it may be possible to strengthen this bound by considering
vertices that belong neither to A nor to B: For any triple of vertices
a ∈ A, b ∈ B, v ∈ X \ (A ∪ B) such that neither (v, a) nor (v, b) is
in E, we may in principle add min{w(v, a), w(v, b)} to the lower bound,
since v cannot be in the same part of the bipartition as both a and b and
so must, by Property 1, have an edge to at least one of these vertices
added. However, doing so introduces the possibility of counting an edge

6

multiple times. Although this can be addressed, doing so appears to come
at its own cost: For example, dividing by the maximum number of times
that any edge is considered produces lower bound increases that are valid
but likely weak; while partitioning vertices a priori and then counting
only bound increases from vertex triples in the same “pristine” part of
the partition has the potential to produce stronger bounds, but entails
significant extra complexity.

3.3

Choosing a subproblem pair

It remains to describe a way to choose disjoint vertex sets A, B ∈ MP
to use for generating child subproblem pairs. The strategy chosen is not
important for correctness, but can have a dramatic effect on the practical performance of the algorithm. Since both types of child subproblem are able to improve lower bounds, a sensible choice is to consider
all A, B ∈ MP and choose the pair that maximises min{LB(SP ∪ OP ∪
{same(A ∪ B)}), LB(SP ∪ OP ∪ {opp(A|B)})}—that is, the pair A, B that
offers the best worst-case bound improvement. Ties could be broken by
max{LB(SP ∪OP ∪{same(A∪B)}), LB(SP ∪OP ∪{opp(A|B)})}. Any remaining ties could be broken arbitrarily, or perhaps using more expensive
approaches such as fixed-length lookahead.

4 Heuristics for the Cograph Editing problem
In the following we will assume unweighted graphs. For graph G = (V, E)
we denote V (G) = V and E(G) = E. Given vertices V 0 ⊆ V , G[V 0 ] is
the subgraph of G induced by V 0 . All neighbors of v in G are denoted by
Nv (G).
Lokshtanov et al. [7] developed an algorithm to find a minimal cograph
completion H = (V, E ∪ F ) of G in O(|V | + |E| + |F |) time. A cograph
completion is called minimal if the set of added edges F is inclusion minimal, i.e., if there is no F 0 ( F such that (V, E ∪ F 0 ) is a cograph. Let
Gx be a graph obtained from G by adding a vertex x and connecting it to
some vertices already contained in G, and let H be any minimal cograph
completion of G. Lokshtanov et al. showed that there exists a minimal
cograph completion Hx of Gx such that Hx [V (H)] = H.
Using this observation they describe a way to compute a minimal cograph completion of G in an iterative manner starting from an empty
graph H0 . In each iteration a graph Gi is derived from Hi−1 by adding
a new vertex vi from G. Vertex vi is connected to all its neighbors
Nvi (G[V (Gi )]) in Gi . Now a set of additional edges Fvi is computed
such that Hi = (V (Gi ), E(Gi ) ∪ Fvi ) is a minimal cograph completion of
Gi . Finally, Hn is a minimal cograph completion of G.
It is obvious that finding a minimal cograph completion gives an upper bound on the Cograph Editing problem. To find a minimal cograph
deletion of G we can simply find a minimal cograph completion of its complement Ḡ. This algorithm allows us to efficiently find minimal cograph

7

deletions and completions. However, only adding or only deleting edges
from G is rather restrictive for finding a good heuristic solution for the
Cograph Editing problem. (Indeed, it is straightforward to construct
instances for which insertion-only or deletion-only strategies yield solutions that are arbitrarily far from optimal.) To allow a combination of
edge insertions and deletions, in each iteration step we choose a vertex vi
and compute the minimum set of edges Fvi (Gi ) to make Hi a minimal
cograph completion of Gi . Furthermore, we compute Fvi (Ḡi ) for its complement. If |Fvi (Gi )| ≤ |Fvi (Ḡi )| we add edges to Hi . Else we remove
edges from Hi to preserve the cograph property. In this way Lokshtanov’s
algorithm serves as a heuristic for the Cograph Editing problem, allowing us to add and remove edges from G. Finding a set of edges Fvi such
that Hi is a minimum cograph completion of Gi takes O(|Nvi (Hi )| + 1)
time. Computing both, Fvi (Gi ) and Fvi (Ḡi ), needs O(|V |) time. Hence,
allowing edge insertions and deletions in every step increases overall running time to O(|V |2 ).
To improve the heuristic there are multiple natural modifications which
can be easily integrated into the Lokshtanov algorithm. The resulting cograph clearly depends on the order in which vertices from G are drawn.
Although it is infeasible to test all possible orderings of vertices in V , it
is nevertheless worthwhile to try more than one. In our simplest version
of the heuristic, we draw random orderings from V and compute a solution for each ordering. Going further, we can test multiple vertices in
each iteration step and add the vertex vi to Hi which needs the smallest
number of edge modifications. In its most exhaustive version this leads to
an algorithm which greedily takes in each step the best of all remaining
vertices and adds it to Hi . This algorithm’s running time increases by a
factor of O(|V |). Another version of the heuristic may apply beam search,
storing the best k intermediate results in each step.
All modifications described so far restrict each iteration to performing
only insertions or only deletions. In order to search more broadly, when
considering how to compute Hi from Gi , we may test whether removing
a single edge incident on vi in Gi before inserting edges as usual results
in fewer necessary edge edits overall. A similar strategy can be applied
to the complement graph. In this way we can insert and delete edges in
a single step – for the price of having to iterate over all of vi ’s neighbors.
If we apply this strategy in each step to Gi and its complement Ḡi , the
running time increases by a factor of O(|V |).
It must be noted that by applying Lokshtanov’s algorithm in the above
manner, we lose any proven guarantees such as minimality.

4.1

Results

We evaluate five heuristic versions. All of them consider adding edges
or deleting edges in each iteration. Unless stated otherwise we run each
heuristic 100 times and take the cograph with lowest costs. The five
versions are:
1. standard : Compute a cograph using random vertex insertion order.
2. modify: When adding vi , allow removing one vertex from vi ’s neigh-

8

borhood in Gi . Hence, multiple edges may be inserted and a single
edge may be deleted in the same step (or vice versa when applied to
Ḡi ).
3. choose-multiple: In each step, choose 10 random vertices, and add
the one with the lowest modification costs.
4. beam-search: Maintain 10 candidate solutions. In each step, for each
candidate solution choose 10 random vertices and try adding each
of them; keep the best 10 of the 100 resulting solutions. Run the
heuristic 10 times instead of 100.
5. choose-all : In each step, consider all remaining vertices from G, and
add the one with the lowest modification costs. Run the heuristic
just once.
We evaluate the heuristics on simulated data. As Cograph Editing
is NP-complete it is computationally too expensive to identify the correct
solution for reasonable size input graphs. We simulate cographs and afterwards randomly perturb edges. The true cograph serves as a proxy for
the optimal cograph: It is a good bound, but there is no guarantee that
no other cograph is closer to the perturbed graph. To simulate cographs
based on their recursive construction definition we start with a graph on
all vertices without any edges. We put all vertices in different bins and
randomly merge bins. When two bins are merged, with some probability
d we connect all vertices which are in different bins.
We simulate cographs with different numbers of vertices n ∈
{10, 20, 50, 100} and edge densities d ∈ {10%, 20%, 50%} where edge density is defined as the number of edges in a graph divided by the number
of edges in a fully connected graph. We limit our evaluations to d ≤ 50%;
edge densities of x% and (100 − x)% will produce the same results as the
complement of a cograph is again a cograph. As our simulation does not
force the exact edge density, we exclude instances where the simulated
cograph’s edge density deviates by more than 10% of the intended edge
density. For each parameter setting 100 cographs are computed: these are
the true cographs. Each true cograph is then perturbed by randomly flipping vertex pairs—making edges non-edges and vice versa—to produce
a noisy graph, which will be given as input to the heuristics. An edge
change is only valid if it introduces at least one new P4 . Each edge can
only be flipped once. We use noise rates r ∈ {1%, 5%, 10%, 20%}. If it
is not possible to introduce a new P4 in each iteration step, we simulate
and perturb a new cograph instead. It must be noted, that a flipped edge
that creates a new P4 will be retained even if it also removes one or more
existing P4 s from the graph.
The heuristic solution to each noisy graph will be denoted the heuristic
cograph. A noise rate of 1% on graphs with 10 vertices is not interesting as
these graphs only contain 45 vertex pairs, so this parameter combination
is excluded from evaluation.
The distance between graphs is the number of edge deletions and insertions needed to transform one graph into another. Dividing this distance
by the number of edges in a complete graph with the same number of
vertices gives the normalized distance, a value between 0 and 1, inclusive.
In the context of an instance of the Cograph Editing problem, the cost

9

of a graph is simply the distance between it and the input graph; we use
solution cost as a measure of solution quality. Given two pairs of graphs,
the first pair is closer than the second pair if the distance between the
first pair is lower than that between the second pair.
We do two kinds of evaluation: the first measures the quality of our
heuristics in solving the Cograph Editing problem, while the second
gauges the strength of the cograph property and this problem formulation
to recover information from noisy data.
First, to test whether the heuristics produce good results we count how
often a heuristic can find a cograph of cost less than or equal to the cost
of the true cograph. Recall that the true cograph gives the best upper
bound for the Cograph Editing problem we can get in practice. Such a
solution will be denoted “fit”. It is clear, that this is not necessarily the
optimal solution.
Second, we evaluate whether the heuristic solution “improves on” the
noisy input graph: that is, whether it produces a cograph which is closer
to the true cograph than the noisy graph is to the true cograph. In
applications like phylogenetic tree estimation, recovering the structure of
the underlying true cograph is of much more interest than a minimum
number of modifications. The use of this optimization problem (and our
heuristic as approximation) is only justified to the extent that a cograph
that requires few edits usually corresponds closely to this “ground truth”
cograph. Let d be the distance between the true cograph and the noisy
graph obtained through experimental measurements. If it is frequently
the case that there exist multiple different cographs at the same distance
d from the noisy graph, some of which are at large distances from the true
cograph, then even an exact solution to the optimization problem is of
limited use in such applications. Worse yet, if it is common to find such
cographs at distances strictly below d, then such an optimization problem
is positively misleading.
On graphs of 20 vertices or fewer, all modifications perform quite well.
To determine the best heuristic method on larger graphs, we compare
results on graphs with 50 vertices (see Fig. 1). Here, the modify heuristic
clearly outperforms the other versions. Hence, it is interesting to see how
this method performs on graphs with different numbers of vertices.
For small graphs with 10 or 20 vertices the modify heuristic finds a
fit solution in almost all cases (see Fig. 2), as do the other heuristics. If
input graphs have as little as 1% noise, even on graphs with 50 vertices
a fit cograph is found in over 98%. For 100 vertices it is still over 65%.
For more complex graphs, having a more balanced ratio of edges and nonedges, the number of fit solutions decreases. Interestingly, looking only at
graphs with 100 vertices and over 1% noise, high noise rates seem to favor
a good heuristic solution. This is likely due to the fact that for high noise
the true cograph is no longer a good bound on the optimal solution.
In application the relevant question is whether or how well the true
cograph can be recovered from noisy data. To make different parameter
combinations comparable we evaluate relative distances. Given distances
distn between the true cograph and the noisy graph and disth between
disth
the true and the heuristic cographs, the relative distance is distrel = dist
n
(see Fig. 3). A value smaller than one implies an improvement: the true

10

number of fit cographs

modify

choose­multiple

80
60
40
20
0

number of fit cographs

standard

100

1%

5%

10%

noise rate

20%

1%

beam­search

100

5%

10%

noise rate

20%

1%

5%

10%

20%

noise rate

choose­all

80
60

edge density

40

10%
20%
50%

20
0

1%

5%

10%

noise rate

20%

1%

5%

10%

noise rate

20%

Figure 1: Comparison of five heuristic versions on graphs with 50 vertices. The
figures show in how many cases the heuristics can find a fit cograph—that is, a
cograph that is at least as close to the noisy graph as the true cograph is to the
noisy graph.

|V| = 10

|V| = 20

|V| = 50

|V| = 100
edge density

number of fit cographs

100

10%
20%
50%

80
60
40
20
0

5%

10%

noise rate

20%

1%

5%

10% 20%

noise rate

1%

5%

10% 20%

noise rate

1%

5%

10% 20%

noise rate

Figure 2: Performance of modify heuristic. The figures show in how many cases
the heuristics can find a fit cograph—that is, a cograph that is at least as close
to the noisy graph as the true cograph is to the noisy graph.

11

cograph is closer to the heuristic cograph than to the noisy graph. A
distrel larger than one implies a loss of similarity, while a value of zero
corresponds to a perfect match between heuristic and true cograph. The
median distrel for graphs with 20 vertices and 1% noise is 0.0 . The mean
is 0.54, 0.34 and 0.27 for 10%, 20% and 50% edge density, respectively.
The distances relative to the maximum number of possible edges can be
seen in supplementary Fig. S1 and S2.
Interestingly, for graphs of size 10 to 50, a certain amount of complexity, meaning greater edge density, seems to encourage a better recovery
of the true cograph. This might be due to the fact that on sparse graphs
there are often multiple options to resolve a P4 which all lead to good
results. Hence, there is no unambiguous way to denoise the graph. Particularly on graphs with 50 vertices we see that increasing edge density
leads to fewer fit cograph solutions (see Fig. 2), but on average the resulting graph is closer to the true cograph (see Fig. 3). This observation does
not hold for graphs with 100 vertices; but, as already explained, the true
cograph no longer gives a good cost bound for large noisy graphs and so
we also cannot expect to recover it. If we limit our evaluation to graphs
with 10 and 20 vertices, we are able to find a fit cograph in almost all
cases. The complexity of graphs with 10 vertices seems to be not sufficiently high to reliably produce a cograph closer to the true cograph. For
graphs of size 20, heuristic and true cograph are mostly closer to each
other than the noisy graph is to the true graph. This means we are able
to partially recover the ground truth. Nevertheless, only for 1% noise and
at least 20 vertices can we either recover the true cograph or at least get
very close to the correct solution.
Lokshtanov’s algorithm has a running time linear in the number of vertices plus edges. The standard heuristic is just the second fastest method
in our evaluation because we run it 100 times and choose-all only once (see
Fig. 4). As expected, running times of beam-search and choose-multiple
are both slower than standard. An iteration step in Lokshtanov’s algorithm for adding vi to Hi is composed of two actions. Step A consists
of examining which edges need to be added so that Hi is a minimal cograph completion of Gi . In step B, vi and all necessary edges are added to
Hi (more precisely, to its cotree). Both choose-multiple and beam-search
perform step A ten times more often than standard, but all three methods perform the same number of B-steps. Hence, running times do not
increase by a factor of ten but rather by two to four.
On graphs with 50 vertices no method takes more than 1.69 seconds
on average; For 100 vertices the slowest method is modify with 12.03
seconds on average. Running times of modify grow fastest. Still, it is
easily applicable to graphs with several hundreds of vertices. The chooseall modification is fastest because only a single cograph is computed; but
running times grow faster than for standard, choose-multiple and beamsearch. All computations were executed single-threaded on an Intel E52630 @ 2.3GHz.

12

|V| = 10

relative number of differing edges

2.5

|V| = 20

2.0

1.5

1.0

0.5

0.0
5%

10%

1%

5%

|V| = 50

2.5

relative number of differing edges

20%

noise rate

noise rate

10%

20%

|V| = 100
edge density

10%
20%
50%

2.0

1.5

1.0

0.5

0.0
1%

5%

noise rate

10%

20%

1%

5%

noise rate

10%

20%

Figure 3: It is shown how well the modify heuristic is able to recover the ground
truth. Each column summarizes the distribution of relative distances for 100
simulated instances. A value lower than one indicates improvement; zero corresponds to perfect recovery.

13

running time in s

10
1

method

modify
choose­multiple
beam­search
standard
choose­all

0.1
0.01
0.001

10

20

|V|

50

100

Figure 4: Running times for five heuristic versions. Noise rate is 5%, edge
density is 20%. Remaining parameter combinations show similar results. The
methods choose-multiple and beam-search have almost identical running times.

5

Conclusion

We presented an exact algorithm solving the weighted Cograph Editing
problem in O(3n n) time and O(2n ) space. We evaluated five heuristics
based on an algorithm for minimal cograph completions. For small and
medium graphs of 10 and 20 vertices we are able to find cographs with
equal or lower cost than the ground truth, indicating that we find (nearly)
optimal solutions. In application, the focus lies on recovering the true
cograph, not the optimal one. We showed that for small noise of 1% we
get results very similar to this true cograph, even for large graphs with
100 vertices. Interestingly, it is easier to recover the true edges when
graphs contain about 50% edges. For higher noise rates it is not possible
to recover the true cograph. This may be partly explained by the fact that
we apply a heuristic and do not solve the Cograph Completion problem
optimally. But this observation already holds for medium graphs with 20
vertices on which we produce good results. We therefore argue that the
cograph constraint is not strict enough to always correctly resolve graphs
with 5% noise and more. Therefore, if true graph structure recovery is
important, low noise rates are crucial.
The presented heuristics are fast enough to be applied to graphs with
several hundreds of vertices. Accuracy clearly improves when removing
the restriction that in each iteration step edges can only be added or
deleted. Different heuristic modifications can be easily combined. This
will likely improve results further.

14

Acknowledgment
Funding was provided to W. Timothy J. White and Marcus Ludwig by
Deutsche Forschungsgemeinschaft (grant BO 1910/9).

References
[1] D. Corneil, H. Lerchs, and L. S. Burlingham, “Complement reducible
graphs,” Discrete Applied Mathematics, vol. 3, no. 3, pp. 163 – 174,
1981.
[2] D. Corneil, Y. Perl, and L. Stewart, “A linear-time recognition algorithm for cographs,” SIAM Journal of Computing, vol. 14, pp. 926–
934, 1985.
[3] E. El-Mallah and C. Colbourn, “The complexity of some edge deletion problems,” IEEE Transactions on circuits and systems, vol. 35,
no. 3, pp. 354–362, 1988.
[4] Y. Liu, J. Wang, J. Guo, and J. Chen, “Complexity and parameterized algorithms for Cograph Editing,” Theoretical Computer Science,
vol. 461, pp. 45–54, 2012.
[5] L. Cai, “Fixed-parameter tractability of graph modification problems
for hereditary properties,” Information Processing Letters, vol. 58,
pp. 171–176, 1996.
[6] M. Hellmuth, N. Wieseke, M. Lechner, H.-P. Lenhof, M. Middendorf,
and P. F. Stadler, “Phylogenomics with paralogs,” Proceedings of the
National Academy of Sciences, vol. 112, no. 7, pp. 2058–2063, 2015.
[7] D. Lokshtanov, F. Mancini, and C. Papadopoulos, “Characterizing and computing minimal cograph completions,” Discrete Applied
Mathematics, vol. 158, pp. 755–764, Apr. 2010.
[8] H. Lerchs, “On the clique-kernel structure of graphs,” Department of
Computer Science, University of Toronto, Toronto, Ont., 1972.
[9] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, “Fourier meets
möbius: fast subset convolution,” in Proceedings of the thirty-ninth
annual ACM symposium on Theory of computing, pp. 67–74, ACM,
2007.
[10] N. Karmarkar and R. M. Karp, “The Differencing Method of Set Partitioning,” Technical Report UCB/CSD 82/113, University of California at Berkeley: Computer Science Division (EECS), 1982.
[11] R. E. Tarjan, “Efficiency of a good but not linear set union algorithm,” J. ACM, vol. 22, pp. 215–225, Apr. 1975.

15

6

Supplementary

16

|V| = 10

0.35

|V| = 20

0.30

0.25

normalized distance

0.25

0.20

0.20

0.15

0.15
0.10

0.10

0.05

0.05
0.00

0.00
5%

10%

noise rate

20%

5%

|V| = 50

0.30

20%

|V| = 100
edge density

0.30
0.25
0.25

normalized distance

10%

noise rate

10%
20%
50%

0.20
0.20
0.15

0.15

0.10

0.10

0.05

0.05

0.00
5%

10%

noise rate

20%

5%

10%

noise rate

20%

Figure S1: It is shown how well the modify heuristic is able to recover the
ground truth for noise rates 5%, 10% and 20%. Each column summarizes the
distribution of normalized distances between a true cograph and the cograph
computed heuristically from a noisy version of it for 100 simulated instances.
The red dashed line indicates the normalized distance between the noisy graph
and the true cograph (noise rate). There are minor deviations from the intended
noise rate as the number of edges in a graph is not continuous. Values below
this line show improvement.

17

edge density

10%
20%
50%

normalized distance (in %)

2.0

1.5

1.0

0.5

0.0
20

50

number of vertices

100

Figure S2: It is shown how well the modify heuristic is able to recover the
ground truth for a intended noise rate of 1%. Each column summarizes the
distribution of normalized distances between a true cograph and the cograph
computed heuristically from a noisy version of it for 100 simulated instances.
The red dashed line indicates the normalized distance between the noisy graph
and the true cograph (noise rate). There are deviations from the intended noise
rate as the number of edges in a graph is not continuous. Values below this line
show improvement.

18

