Parameterized Aspects of Triangle Enumeration ∗

arXiv:1702.06548v3 [] 19 Dec 2017

Matthias Bentert1, Till Fluschnik†,1 , André Nichterlein‡,1 , and
Rolf Niedermeier1
1

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany,
{firstname.lastname}@tu-berlin.de

Abstract
Listing all triangles in an undirected graph is a fundamental graph primitive with
numerous applications. It is trivially solvable in time cubic in the number of vertices.
It has seen a significant body of work contributing to both theoretical aspects (e.g.,
lower and upper bounds on running time, adaption to new computational models) as
well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the
fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration, providing both positive results (new
enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as
negative results (likely uselessness in terms of “faster” parameterized algorithms of
certain parameters such as graph diameter).

1

Introduction

Detecting, counting, and enumerating triangles in undirected
graphs is a basic graph prim
n
itive. In an n-vertex graph, there can be up to 3 different triangles and an algorithm
checking for each three-vertex subset whether it forms a triangle can list all triangles
in O( n3 ) time. As to counting the number of triangles in a graph, the best known algorithm takes O(nω ) ⊂ O(n2.373 ) time [40] and is based on fast matrix multiplication.1
Finally, detecting a triangle in a graph is doable in O(nω ) time [40] and it is conjectured
that every algorithm for detecting a triangle in a graph takes at least Θ(nω−o(1) ) time [1].
We mention that for m-edge graphs there is also an O(m1.5 )-time algorithm [34] which is
interesting in case of sparse graphs. Our work is motivated by trying to break such (relative or conjectured) lower bounds and improve on best known upper bounds—the twist
is to introduce a secondary measurement beyond mere input size. This is also known as
∗

An extended abstract appeared at FCT 2017.
Supported by the DFG, project DAMM (NI 369/13-2).
‡
Partially supported by a postdoc fellowship of the DAAD while at Durham University, UK.
1
ω is a placeholder for the best known n × n-matrix multiplication exponent.
†

1

problem parameterization. While parameterizing problems with the goal to achieve fixedparameter tractability results is a well-established line of research for NP-hard problems,
systematically applying and extending tools and concepts from parameterized algorithmics
to polynomial-time solvable problems is still in its infancy [2, 31, 21, 25, 44, 13, 23]. Performing a closer study of mostly triangle enumeration, we contribute to this line of research,
also referred to as “FPT-in-P” for short [25]. Our central leitmotif herein is the quest for
parameterized subcubic triangle enumeration algorithms.
Related work. Triangle enumeration, together with its relatives counting and detection, has many applications, ranging from spam detection [6] over complex network analysis [26, 45] and database applications [35] to applications in bioinformatics [54]. We refer
to Kolountzakis et. al. [36] for an extended list of applications with small explanations why
the respective triangle finding problem is relevant in each application.
The significance of the problem triggered substantial theoretical and practical work.
The theoretically fastest algorithms are based on matrix multiplication and run in O(nω +
n3(ω−1)/(5−ω) · (#T )2(3−ω)/(5−ω) ) time, where #T denotes the number of listed triangles [7].
Furthermore, there is (heuristic and experimental) work on enumerating triangles in large
graphs [39, 51] and in the context of map reduce in graph streams [48, 5, 10]. There are
even quantum algorithms for triangle detection [41]. For a broader overview, we refer to a
survey by Latapy [40].
As to parameterized results, early work by Chiba and Nishizeki [11] showed that all
triangles in a graph can be counted in O(m · d) time, where d is the degeneracy of the
graph.2 This running time can be improved by saving polylogarithmic factors if the number
of triangles is not cubic in the number of vertices in the input graph [37], but the 3SUMconjecture3 rules out more substantial improvements [38]. Green and Bader [27] described
an algorithm for triangle counting running in O(TK + |K| · ∆2K ) time, where K is a vertex
cover of the input graph, ∆K is the maximum degree of vertices in K (with respect to
the input graph), and TK is the time needed to compute K. They also described several
experimental results. Recently, Coudert et al. [13] proved that both, finding and counting
triangles in a given graph, can be solved in O(k 2 · (n + m)) time, where k is (amongst
others) the clique-width of the input graph. Finally, Eppstein and Spiro [19] described
a data structure that keeps track of the number of triangles in an undirected graph that
changes over time (in each step a new edge can be inserted or an existing one can be
deleted). They described the time complexity of updating their data structure in terms of
2

A graph G has degeneracy d if every subgraph contains a vertex of degree at most d; thus G contains
at most n · d edges. Indeed, Chiba and Nishizeki [11] used the parameter “arboricity” of a graph, which is
at most two times its degeneracy. Moreover, their algorithm can be modified to list all triangles without
any (substantial) overhead.
3
The 3SUM problem asks whether a given set S of n integers contains three integers a, b, c ∈ S summing
up to 0. The 3SUM-conjecture states that for any constant ε > 0 there is no O(n2−ε )-time algorithm solving
3SUM. The connection between 3SUM and listing/detecting triangles is well studied [41, 49].

2

the h-index of the current graph.4
Complementing algorithmic results, the problems of finding and counting triangles are
studied from a running time lower bounds perspective, where the lower bounds are based
on popular conjectures like, for instance, the Strong Exponential-Time Hypothesis [33, 32].
Accordingly, lower bounds are proven for finding (in a given edge-weighted graph) a triangle
of negative weight [53] or counting (in a given vertex-colored graph) triangles with pairwise
different colors on the vertices [3]. Recently, making use of the above mentioned results,
lower bounds on strict kernelization, that is kernelization where the parameter in the
kernel is not allowed to increase, are proven for both problems when parameterized by, for
instance, the maximum degree or the degeneracy of the given graph [22]; Additionally, for
both problems with the same parameterization, a strict kernel of cubic size computable
in O(n5/3 ) time is given.
Our contributions. We systematically explore the parameter space for triangle enumeration and classify the usefulness of the parameters for FPT-in-P algorithms. In doing so,
we present an extended concept of enumerative kernelization and a novel hardness concept,
as well as algorithmic results. Our concrete results are surveyed in Table 1. We refer to
the respective sections for motivation and a formal definition of the various parameters.
In particular, we provide enumerative problem kernels with respect to the parameters
“feedback edge number” and “distance to d-degeneracy graphs”. Partially based on data
reduction algorithms, we provide fast algorithms for several parameters such as feedback
edge number, (vertex-deletion) distance to bipartite graphs, chordal graphs, cographs and
to d-degeneracy (the last one with and without the additional parameter maximum vertex
degree), and clique-width. On the negative side, using a concept we call “General-Problemhardness”, we show that using the parameters domination number, chromatic number, and
diameter do not help to get FPT-in-P algorithms for detecting triangles, that is, even for
constant parameter values the problem remains as “hard” as the general version with
unbounded parameter.
Organization. The remainder of this work is organized as follows.
some notation and explain basic concepts. Then, in Section 3, we
notions, give a small example for each of them, and state our main
Section 4 we provide the positive results of our work. We conclude in
some directions for possible further research.

2

In Section 2 we fix
introduce two new
negative result. In
Section 5 and state

Preliminaries

Notation. For an integer ℓ ≥ 1, let [ℓ] = {1, . . . , ℓ}. Let G = (V, E) be an undirected
simple graph. We also denote by V (G) and E(G) the vertex set and edge set of G,
respectively. We set n ..= |V |, m ..= |E|, and |G| ..= n + m.
4
The h-index of a graph is the maximum number h such that the graph contains at least h vertices of
degree at least h.

3

parameter k

result

reference

feedback edge number

at most 9k
{ size
in O(n + m) time

Prop. 4.2

{

at most k + 2k + 3 vertices
in O(n · d · (k + 2k )) time

Thm. 4.6

distance to d-degenerate
+ maximum degree ∆
feedback edge number
distance to d-degenerate
distance to bipartite
distance to chordal
distance to cographs
clique-width

O(k · ∆2 + n · d2 )

Prop. 4.4

solving

distance to d-degenerate

O(k 2 + n + m)
O(n · d · (k + d) + 23k + # T )
O(#T + n + m · k)
O(n + m · k)
O(#T + n + m · k)
O(n2 + n · k 2 + # T )

Thm.
Cor.
Thm.
Thm.
Thm.
Thm.

hard

enum-kernel

Table 1: Overview of our results. (n: number of vertices; m: number of edges; #T : number of
triangles; k: respective parameter; ∆: maximum degree)

domination number,
chromatic number, and
diameter

for k ≥ 3
as hard as
the general case

Prop. 3.3

4.3
4.7
4.8a
4.8b
4.8c
4.13

We denote by N(v) the (open) neighborhood of a vertex v ∈ V and by deg(v) ..= |N(v)|
the degree of v. By G[U] we denote the subgraph of G induced by the vertex subset U ⊆ V
and G − U ..= G[V \ U]. A vertex subset U ⊆ V is a vertex cover of G if G − U contains
no edges. If {x, y, z} ⊆ V induces a triangle in a graph, we refer to T = {x, y, z} as this
triangle. We denote the number of triangles in the graph by #T. Our central problem is
as follows.
Triangle Enumeration (△-Enum)
Input: An undirected graph G.
Task: List all triangles contained in G.
Parameterized Complexity. A language L ⊆ Σ∗ × N is a parameterized problem over
some finite alphabet Σ, where (x, k) ∈ Σ∗ × N denotes an instance of L and k is the
parameter. For a parameterized problem L, the language L̂ = {x ∈ Σ∗ | ∃k : (x, k) ∈ L}
is called the unparameterized problem associated to L. Then L is called fixed-parameter
tractable (equivalently, L is in the class FPT) if there is an algorithm that on input (x, k)
decides whether (x, k) ∈ L in f (k) · |x|O(1) time, where f is some computable function only
depending on k and |x| denotes the size of x. We call an algorithm with a running time of
4

the form f (k) · |x| a linear-time FPT algorithm. Creignou et al. [16, Definition 3.2] introduced the concept of FPT-delay algorithms for enumeration problems. An algorithm A is
an FPT-delay algorithm if there exist a computable function f and a polynomial p such
that A outputs for every input x all solutions of x with at most f (k) · p(|x|) time between
two successive solutions. If the delay can be upper-bounded in p(|x|), then the algorithm
is called a p-delay algorithm. A kernelization for L is an algorithm that on input (x, k)
computes in time polynomial in |x| + k an output (x′ , k ′ ) (the kernel ) such that
(i) (x, k) ∈ L ⇐⇒ (x′ , k ′ ) ∈ L, and
(ii) |x′ | + k ′ ≤ g(k) for some computable function g only depending on k.
The value g(k) denotes the size of the kernel. It is well-known that a decidable parameterized problem P is in FPT if and only if L admits a kernelization.
We can associate a graph parameter k with a function κ : G → N∪{∞} that maps every
graph G to its parameter value, where G denotes the family of all graphs. We say that k
lower-bounds a parameter k ′ , associated with function κ′ , if there is a function f : N → N
such that for every graph G ∈ G it holds that κ(G) ≤ f (κ′ (G)) (respectively, we say k ′
upper-bounds k). If for two parameters it holds that none of them lower-bounds the other,
we say that the two parameters are unrelated.
Our work focuses on enumeration, while the great majority of parameterized complexity
works study decision (or search and optimization) problems.
Definition 2.1 ([16, Definition 1]). A parameterized enumeration problem is a pair (P, Sol)
such that
• P ⊆ Σ∗ × N is a parameterized problem over a finite alphabet Σ and
• Sol : Σ∗ × N → P(Σ∗ ) is a function such that for all (x, k) ∈ Σ∗ × N, Sol(x, k) is a
finite set and Sol(x, k) 6= ∅ ⇐⇒ (x, k) ∈ P .
Intuitively, the function Sol contains for each instance (x, k) of P the set of all solutions.
Given an instance (x, k), the task is then to compute Sol(x, k).

3

New Notions of Hardness and Kernelization

In this section we introduce two notions and give simple proofs of concept for both of
them. The first notion is a many-one reduction that relates a parameterized problem to
its unparameterized counterpart. We call it “General-Problem-hardness” as it proves the
parameterized version to be as hard as the unparameterized (general) problem. The second
concept is an adaption of an existing kernelization concept for enumeration problems. It
uses some additional space in order to avoid encoding everything in the kernel instance.

5

3.1

Computational Hardness

We show hardness for the following problem.
Triangle Detection (△-Detect)
Input:
An undirected graph G.
Question: Does G contain a triangle?
Since △-Detect is a special case of △-Enum, it follows that any lower bound for △Detect implies the same lower bound for △-Enum. Thus, if a certain parameter does not
admit a solving algorithm for △-Detect in some (parameterized) time X, then △-Enum
does not either.
Before giving a formal definition of our concept, consider as an introductory example
the parameter minimum degree. Adding an isolated vertex to any graph in constant time
leaves the set of triangles unchanged and the resulting graph has minimum degree zero.
Hence, one cannot use the parameter minimum degree to design faster algorithms for △Detect. Upon this trivial example, we study which parameters for △-Detect cannot
be used to design linear-time FPT algorithms under the hypothesis that △-Detect is not
linear-time solvable [1]. To this end we reduce in linear time an arbitrary instance of △Detect to a new equivalent (and not too large) instance of the problem with the parameter
upper-bounded by a constant. The corresponding notion of a many-one reduction is as
follows.
Definition 3.1. Let P ⊆ Σ∗ × N be a parameterized problem, let Q ⊆ Σ∗ be the unparameterized problem associated to P , and let f : N → N be a function. We call P
ℓ-General-Problem-hard(f ) (ℓ-GP-hard(f )) if there exists an algorithm A transforming
any input instance x of Q into an instance (x′ , k ′ ) of P such that
(G1) A runs in O(f (|x|)) time,
(G2) x ∈ Q ⇐⇒ (x′ , k ′ ) ∈ P ,
(G3) k ′ ≤ ℓ, and
(G4) |x′ | ∈ O(|x|).
We call P General-Problem-hard(f ) (GP-hard(f )) if there exists an integer k such that P
is k-GP-hard(f ). We omit the running time and call P k-General-Problem-hard (k-GPhard) if f is a linear function.
If one can exclude an algorithm solving Q in O(f (|x|)) time and one can further prove
that P is GP-hard, then one can (under the same assumptions that excludes an O(f (|x|))time algorithm for Q) exclude an algorithm solving P in g(k) · f (|x|) time for any computable function g. This yields the following.

6

Lemma 3.2. Let f : N → N be a function, let P ⊆ Σ∗ × N be a parameterized problem
that is ℓ-GP-hard(f ), and let Q ⊆ Σ∗ be the unparameterized problem associated to P . If
there is an algorithm solving each instance (x, k) of P in g(k) · f (|x|) time, then there is
an algorithm solving each instance x′ of Q in O(f (|x′ |)) time.
Proof. Assume that there is an algorithm B which solves each instance (x, k) of P in
O(g(k) · f (|x|)) time. Let xQ be an arbitrary instance of Q. Since P is ℓ-GP-hard(f ),
there is an algorithm A which transforms x into a new instance (x′ , k ′ ) of P in O(f (|x|))
time such that k ′ ≤ ℓ, |x′ | ∈ O(|x|), and x ∈ Q if and only if (x′ , k ′ ) ∈ P .
By assumption, algorithm B solves (x′ , k ′ ) in g(k ′) · f (|x′ |) time. Since |x′ | ∈ O(|x|) and
k ′ ≤ ℓ, it holds that g(k ′) · f (|x′ |) ∈ O(f (|x|)). Since x ∈ Q if and only if (x′ , k ′ ) ∈ P holds,
this algorithm solves Q in O(f (|x|)) time.
It is folklore that △-Detect in tripartite graphs is among the hardest cases. Based
on this, we show that △-Detect with respect to the combined parameters domination
number, chromatic number, and diameter is 9-GP-hard. Indeed, △-Detect is 3-GP-hard
for each of the (single) parameters.
S The domination number of a graph is the size of a
minimum cardinality set S with v∈S N(v) ∪ S = V . The chromatic number of a graph
is the minimum number of colors needed to color the vertices such that no edge contains
vertices of the same color. The diameter of a graph is the length of the longest shortest
path between two vertices.
Proposition 3.3. △-Detect is 9-GP-hard with respect to the sum of domination number,
chromatic number, and diameter.
Proof. Let G = (V, E) be an instance of Triangle Detection. Let V = {v1 , . . . , vn }.
We construct a graph G′ = (V ′ , E ′ ) in time linear in the size of G such that G contains
a triangle if and only if G′ contains a triangle. Moreover, G′ has domination number,
chromatic number, and diameter at most three.
We refer to Figure 1 for an illustrative example of the following construction of G′ .
Let G′ be initially empty. Add three copies V1′ , V2′ , V3′ of V to G′ , and let Vi′ = {v1i , . . . , vni },
i ∈ {1, 2, 3}. For each edge {vx , vy } ∈ E, add the edge set {{vxi , vyj } | i, j ∈ {1, 2, 3}, i 6= j}
to G′ . Add the vertex sets L = {ℓ1 , ℓ2 , ℓ3 } and R = {r1 , r2 , r3 } to G′ . For each i ∈ {1, 2, 3},
connect ℓi , ri with each vertex in Vi′ by an edge, that is. add {{ℓi , vxi }, {ri , vxi } | i ∈
{1, 2, 3}, x ∈ [n]} to the edge set of G′ . Finally, for i 6= j, connect ℓi ∈ L with rj ∈ R by
an edge in G′ , that is, add the edge set {{li , rj } | i, j ∈ {1, 2, 3}, i 6= j}. This completes
the construction of G′ .
We prove that the properties (G1)–(G4) of Definition 3.1 are fulfilled. Note that G′ is
constructed in O(|G|) time (G1) and contains 3n + 6 vertices and 6m + 6n + 6 edges (G4).
Observe that each Vi′ , i ∈ {1, 2, 3}, forms an independent set in G′ . In addition, each vertex
set N(ℓi ), N(ri ), i ∈ {1, 2, 3}, forms an independent set in G′ .
Next, we prove that G contains a triangle if and only if G′ contains a triangle (G2).
Suppose that {vx , vy , vz } forms a triangle in G. Then, by construction of G′ , G′ contains
the vertices vx1 , vy2 , and vz3 and the edges {vx1 , vy2 }, {vy2 , vz3 }, and {vx1 , vz3 }. Hence, {vx1 , vy2 , vz3 }
forms a triangle in G′ .
7

V1′

r1

v1
v3
v4

v2

V2′

v11

l1

l2

v42

v21

r2

v32

v31

v22

v41

v12

v13

v23

l3

V3′

v33

v43

r3

Figure 1: An illustration of the construction of the graph in the proof of Proposition 3.3,
exemplified on the left-hand side graph. The triangle {v1 , v2 , v3 } on the left-hand side corresponds
in the right-hand side to multiple triangles, one of them is highlighted by bold lines.

Conversely, suppose that {x, y, z} forms a triangle in G′ . As Vi′ , N(ℓi ), and N(ri ) form
independent sets for each i ∈ {1, 2, 3} in G′ , {x, y, z} does not contain ℓi , ri , or at least two
vertices of Vi′ , i ∈ {1, 2, 3}. It follows that for each i ∈ {1, 2, 3} it holds |{x, y, z} ∩ Vi′ | = 1.
Let without loss of generality be x = va1 ∈ V1′ , y = vb2 ∈ V2′ , and z = vc3 ∈ V3′ . As for i 6= j
it holds that {vai , vbj } ∈ E ′ if and only if {va , vb } ∈ E, it follows that {va , vb , vc } forms a
triangle in G.
Last, we prove that the domination number, the chromatic number, and the diameter
of G′ are all at most 3 (G3). As for each i ∈ {1, 2, 3}, each vertex in Vi′ is connected with ℓi ,
and N(ri ) ∩ L 6= ∅, the set L is a dominating set in G′ . As each Vi′ , i ∈ {1, 2, 3}, is an
independent set in G′ , color the vertices of Vi′ with color i. Next, color the vertices ℓi , ri with
color 1 + (i mod 3) for each i ∈ {1, 2, 3}. This forms a valid coloring of the vertices in G′
with at most three colors. Observe that since Vi ∪R\{ri } ∈ N(ℓi ) and Vi ∪L\{ℓi } ∈ N(ri ),
each vertex in G′ has distance at most two to ℓi and ri , for each i ∈ {1, 2, 3}. As each
vertex in V1′ ∪ V2′ ∪ V3′ has a neighbor in L ∪ R, it follows that G′ is of diameter at most
three.
Altogether, (G1)–(G4) of Definition 3.1 are satisfied and hence the theorem follows.

8

≤ h(ℓ)

input (x, ℓ)

R

≤ h(ℓ)
R

kernel
I(x, ℓ)

input (x, ℓ)

w∈W

f (x, w) = Sol(x, ℓ)

kernel
I(x, ℓ)

Tf

Tf
S

advice
A(x, ℓ)

S

W = Sol(I(x, ℓ))

w∈W

(a) Enum kernelization.

f (w, A(x, ℓ)) = Sol(x, ℓ)

W = Sol(I(x, ℓ))

(b) Enum-advice kernelization.

Figure 2: A schematic picture of (a) enum- and (b) enum-advice kernelization. Here, R refers
to the algorithm that produces the kernel and, for enum-advice kernelization, also the advice,
and Tf refers to the polynomial-delay algorithm enumerating all solutions of the input.

3.2

Enum-Advice Kernelization

The second new notion we introduce in this paper is an adaption of an enumerative kernelization concept due to Creignou et al. [16].
The aim of kernelization is to efficiently reduce a large instance of a computationally
hard, say NP-hard, problem to an “equivalent” instance (called “kernel”) whose size only
depends on the parameter and not on the size of the original input instance. Then, solving
the kernel by a trivial brute-force algorithm often significantly reduces the overall running
time. This technique is by no means restricted to computationally hard problems even
though it was invented to tackle problems for which no polynomial-time algorithms are
known.
Observe that kernelization is usually defined for decision problems only. Creignou et
al. [16] developed a concept to address enumeration problems. Roughly speaking, their
concept requires that all solutions of the input instance can be recovered from the input
instance and the solutions of the kernel (see Figure 2(a)). We modify the concept by adding
a generic object which we call the advice of the kernelization. The intention of this change
is that in order to compute all solutions of the input instance, one only needs the kernel
and the advice (which might be much smaller than the input instance), see Figure 2 for an
illustration. In the examples we provide in this paper, in the advice we store information
about all triangles that are destroyed by data reduction rules.
We will now give a formal definition of our new enumerative kernelization concept and
then discuss the potential advantages compared to the concept by Creignou et al. [16].
Definition 3.4. Let (P, Sol) be a parameterized enumeration problem. Let R be an
algorithm which for every input (x, k) computes in time polynomial in |x|+k a pair (I(x, k),
A(x, k)). We call R an enum-advice kernelization of (P, Sol) if
(K1) there exists a function h such that for all (x, k) it holds that |I(x, k)| ≤ h(k),
9

(K2) for all (x, k) it holds that (x, k) ∈ P ⇐⇒ I(x, k) ∈ P , and
(K3) there exists a function f such that for all (x, k) ∈ P
(a) ∀p, q ∈ Sol(I(x, k)) : p 6= q =⇒ f (p, A(x, k)) ∩ f (q, A(x, k)) = ∅,
S
(b)
w∈Sol(I(x,k)) f (w, A(x, k)) = Sol(x, k), and

(c) there exists an algorithm Tf such that for every (x, k) ∈ P and w ∈ Sol(I(x, k)),
Tf computes f (w, A(x, k)) in FPT-delay time [16].

If R is an enum-advice kernelization of (P, Sol), then I(x, k) is called the kernel of (x, k)
and A(x, k) is called the advice of I(x, k). If algorithm Tf has p-delay time for some
polynomial p (only in |x|), then we say that the problem admits a p-delay enum-advice
kernel.
Clearly, since every polynomial-time solvable enumeration problem has a trivial enumadvice kernelization, we are only interested in those kernelizations where R and Tf are both
significantly faster than the best (known) algorithms to solve the enumeration problem.
We will now discuss the potential advantages of our new definition compared to enumkernelization. The advice can be used to design faster algorithms since the advice might
be much smaller than the input instance, as described in the following example. Observe
that one can set A(x, ℓ) = (x, ℓ), and thus enum-advice kernelization is a generalization of
enum-kernelization.
Example 3.5. Consider the Enum Vertex Cover problem parameterized by solution
size k; here the task is to list all minimal vertex covers of size at most k of an input graph G.
As observed by Creignou et al. [16, Proposition 1], the standard Buss’ kernelization [18]
provides an enum-kernelization for this problem. It consists of the following two data
reduction rules:
1. If deg(v) > k, then remove v and all edges incident with v from G and decrease k by
one (v is contained in every vertex cover of size at most k).
2. If deg(v) = 0, then remove v from G (no minimal vertex cover contains v).
Let G′ be the graph obtained from exhaustively applying the two data reduction rules on G
such that none of the two rules is applicable to G′ . If G′ contains more than k 2 edges, then
return the complete graph of k + 2 vertices as there is no vertex cover of size k. Otherwise,
return graph G′ .
Let VD be the set of vertices that are deleted by the first rule. The set of minimal
vertex covers in the input graph G can be obtained by adding VD to each minimal vertex
cover in the kernel G′ . For the set of minimal vertex covers of G of size at most k one
considers only minimal vertex covers in G′ that have size at most k − |VD |. In an enumadvice kernel one can store VD in the advice, which then has size O(k) and adds it to each
minimal vertex cover in G′ in O(k) time. In contrast, the enum-kernelization concept would
require to again compute VD which requires time linear in the size of G for each minimal
10

≤ h(ℓ)

≤ h(ℓ)
R

R

VD

k=2
k=3

Tf

k=3

×

k=2

Tf
×

(a) Enum kernelization.

(b) Enum-advice kernelization.

Figure 3: A schematic picture of (a) enum- and (b) enum-advice kernelization for Enum Vertex
Cover. In this example the kernel only consists of a single vertex while the input instance consists
of 12 vertices and 11 edges.

vertex cover in G′ . We refer to Figure 3 for an illustration. When considering NP-hard
problems replacing a term like n + m by k might be only a small improvement, but for
polynomial-time solvable problems (like △-Enum) it can have a significant impact.
As discussed in the above example, the advice can be used to efficiently compute the
solutions from the kernel. In general, enumeration algorithms can be derived from enumadvice kernels as stated in the next lemma.
Lemma 3.6. Let R be an enum-advice kernelization of a parameterized enumeration problem (P, Sol) such that for every instance (x, k) of P :
• R runs in O((|x| + k)c ) time for some constant c;
• the unparameterized version of P can be solved in g(|x|) time on x;
• the kernelization computes the pair (I, A) where |I| ≤ h(k), and algorithm Tf takes
O(|I|d) time between generating two solutions for some constant d; and
• #s denotes the number of solutions in I and #S denotes the number of solutions
in x.
Then, (P, Sol) can be solved in O((|x| + k)c + g(h(k)) + (#s + #S) · h(k)d ) time.
Proof. We use the notation as stated in the lemma and assume that all stated conditions
hold. We will prove that there exists an algorithm solving (P, Sol) in O((|x| + k)c +
g(h(k)) + (#s + #S) · h(k)d ) time.
c
First, compute the kernel (I, A) in O((|x| + k)
S ) time. Second, find all solutions in I
in g(|I|) ∈ O(f (h(k))) time. Third, compute w∈Sol(I) f (w, A). This can be done by
running Tf on every solution in I. There are #s solutions in I, hence there are #s
11

iterations of Tf . The algorithm therefore spends at most O(#s ·|I|d) time as precalculation or postcalculation time. We refer to Creignou et al. [16] for a formal definition
of pre- and postcalculation time. Informally, precalculation time is the time from the
start of the calculation until the first solution is listed and postcalculation time is the
time needed after the last solution is listed. Apart from pre- and postclaculation time,
the time between two solution outputs is O(|I|d) ⊆ O(h(k)d ). Since there are #S solutions in x, computing all solutions takes (#S + #s) · (h(k))d time. Thus, this algorithm
takes O((|x| + k)c + g(h(k)) + (#s + #S) · h(k)d ) time.
Note that in general we cannot give any meaningful upper bound on the delay of
the constructed algorithm as the kernel instance might be packed with solutions p such
that f (w, A) = ∅. If no such solutions exist, then the delay of the described algorithm
is O((|x| + k)c + f (h(k)) + h(k)d )). The delay of all algorithms presented in our work is
only upper-bounded by the respective running times of the algorithms.

4

Algorithms

In this section, we present FPT algorithms solving △-Enum exploiting several parameters.
We systematically explore the parameter landscape along a hierarchy of graph parameters
(see [52]) in the following way (Figure 4 surveys our line of attack). We start from the
fact that △-Enum allows for an O(m · d)-time algorithm when parameterized by degeneracy d [11], and go into the following two directions: First, we study in Section 4.1 whether
parameters k upper-bounding degeneracy admit algorithms running in f (k) + O(n + m)
time. Kernelization is one way to achieve such additive (f (k) + O(n + m)) instead of
multiplicative (f (k) · O(n + m)) running times. Indeed, for the two parameters feedback
edge number and distance to d-degenerate graphs (see definitions below) we show enum
advice-kernels. Second, we study in Section 4.2 parameters that are incomparable with
degeneracy and so far have been unclassified.
We remark that in most of our running times the dependency on the parameter is modest. The only exception here is the parameter distance to d-degenerate with an exponential
dependency. Thus, in scenarios where the respective parameter is small, the corresponding
algorithms should be suitable for implementation.

4.1

Parameters Lower-Bounded By Degeneracy

In this section we show results on graph parameters that upper-bound a graph’s degeneracy.
We first describe the parameters and then turn to the results.
We begin with feedback edge number. A feedback edge set in a graph is a subset of the
edges such that removing the edges from the graph results in a forest. The feedback edge
number of a graph is the size of a minimum feedback edge set. Graphs with small feedback
edge set number are “almost trees”; such social networks occur in the context of sexually
transmitted infections [50] and extremism propagation [24]. Note that the feedback edge

12

Distance to d-degenerate + maximum degree (Prop. 4.4)
Feedback edge number
(Prop. 4.2, Thm. 4.3)

Distance to d-degenerate (Thm. 4.6, Cor. 4.7)
Vertex cover number (0-degenerate)
Feedback vertex number (1-degenerate)

enum-advice
kernel

f (k) · (n + m)

..
.
Distance to
Cograph
(Thm. 4.8c)

Distance to
Chordal
(Thm. 4.8b)

Domination
Number (Prop. 3.3)

Degeneracy [11]

Average
degree [34]

Clique-width
(Thm. 4.13)

f (k) · n2

GP-hard

Distance to
Bipartite
(Thm. 4.8a)

Chromatic
Number (Prop. 3.3)
Minimum degree
(Sec. 3.1)

Diameter (Prop. 3.3)

Figure 4: “Layerwise separation” of considered parameters with respect to known and new
results. Herein, the parameters are hierarchically arranged in the sense that if two parameters
are connected by a line, then the lower one can be upper-bounded by some function only depending
on the higher one. Thus, hardness results transfer downwards and tractability results upwards.
For the family of parameters distance to d-degenerate graphs we highlighted d = 0 and d = 1 as
prominent examples.

number can be of order O(m) (for instance in a complete graph). Moreover, the parameter
is neither related to the distance to 0-degenerate graphs (vertex cover number) nor to
the maximum degree, but it upper-bounds the distance to 1-degenerate graphs (feedback
vertex number). Computing a feedback edge set of minimum cardinality can be done in
linear time by e. g. breadth-first-search. We hence assume that an optimal feedback edge
set is given.
A graph is d-degenerate if each induced subgraph contains a vertex of degree at most d.
The distance to d-degenerate graphs of a graph G is the size of a minimum-cardinality
vertex set D such that G − D is d-degenerate. This parameter generalizes several wellknown parameters like vertex cover (distance to 0-degenerate graphs) and feedback vertex
set (distance to 1-degenerate graphs). For any fixed d the distance to d-degenerate graphs
is NP-hard to compute [42]. However, we can use existing linear-time constant-factor
13

approximation algorithms for d = 0 and d = 1 [4]. Since a minimum feedback vertex set of
a graph is always (and possibly much) smaller than its smallest vertex cover, it is natural
to use this parameter rather than the vertex cover if comparably good results can be shown
for both parameters.
For larger values of d, one can use heuristics to compute small sets D such that G − D
is d-degenerate. Notably, the quality of the heuristic only affects the running time but not
the solution quality of the subsequent parameterized algorithm.
The distance to d-degenerate graphs is usually small in many applications such as social
networks as they contain only few vertices with high degree [20]. Depending on the degree
distribution at hand one can then choose the value of d that gives the best overall runningtime. (The running time of the corresponding algorithms usually have some trade-off
between d and the distance to d-degenerate graphs.)
4.1.1

Feedback Edge Number

We first provide a key lemma and then state a linear-size enum-advice kernel for △-Enum
parameterized by feedback edge number.
Lemma 4.1. Let G = (V, E) be an undirected graph and let F be a feedback edge set in G.
All triangles {u, v, w} where at least one of the edges between the three vertices is not in F
can be enumerated in O(n + m) time. There are at most 2|F | such triangles.
Proof. Let G′ = (V, E \ F ) be an arbitrarily rooted forest and let p(v) denote the parent
of a vertex v in it. Note that F , G′ , and p can be computed in O(n + m) time. Notice
further that all edges in E \ F are of the form {v, p(v)} for some vertex v and hence
every triangle {u, v, w} in G where at least one of the edges between the three vertices
is not in F is of the form {u, v, p(v)} for some vertices u, v. We can therefore check for
each edge {u, v} ∈ F whether p(u) = p(v), {p(u), v} ∈ E or {u, p(v)} ∈ E in constant
time. In the first case we list {u, v, p(u)} as a triangle and do not consider the other cases.
If p(u) 6= p(v) and {p(u), v} ∈ E, then we list {u, v, p(u)} as a triangle. If p(u) 6= p(v)
and {u, p(v)} ∈ E, then we list {u, v, p(v)} as a triangle. Note that for every edge in F we
list at most two triangles. Assume towards a contradiction that there is a triangle {x, y, z}
in G which is not listed by the described algorithm and where at least one edge between
these three vertices is not in F . Without loss of generality let {x, y} ∈ E \ F . Since G′
is a rooted forest, either x is the parent of y or y is the parent of x. Let without loss of
generality be y = p(x). Since {x, y, z} is a triangle, it holds that {y, z} ∈ E. Thus {x, y, z}
is found by the algorithm above.
Using this we can easily show the following enum-advice kernel.
Proposition 4.2. △-Enum parameterized by feedback edge number k admits a constantdelay enum-advice kernel with at most 2k+3 vertices and k+3 edges which can be computed
in O(n + m) time.

14

Proof. Construct an enum-advice kernel (I = I(G, k), A = A(G, k)) as follows. For every
edge e ∈ F put e and both of its endpoints into the graph. Compute the feedback edge
number k ′ ≤ k of GI in linear time. Compute all triangles in G with at least one edge
in E \ F and set A to be the set of all triangles found. If A 6= ∅, then add one extra
triangle {x, y, z} where x, y, z ∈
/ V . Lemma 4.1 shows that there are at most 2k such
triangles and that they can be computed in linear time. Observe that each step can be
done in O(n + m) time. Set the function f ({x, y, z}, A) = A and f (w, A) = {w} for
each w ∈ Sol(I), w 6= {x, y, z}.
We prove that the algorithm fulfills conditions (K1)–(K3) of Definition 3.4.
By construction, for each edge in F there are at most two vertices and one edge put
into I. There is at most one extra triangle added with three vertices and three edges.
Thus, it holds that |GI | ≤ 3 · k + 3 (K1).
Assume that there is a triangle T = {vx , vy , vz } in G. It either contains at least one
edge in E \ F or only edges in F . In the first case GI contains the triangle {x, y, z} and
in the second case GI contains T . Analogously, if GI contains a triangle T ′ , then it is
either {x, y, z} or not. If it is, then, by construction, A 6= ∅ and hence G contains a
triangle in A. If it is not, then T ′ is also contained in G. Thus G contains a triangle if and
only if GI contains a triangle (K2).
It remains to discuss the properties (K3) of function f .
For p, q ∈ Sol(I) \ {x, y, z}, if p 6= q, then f (p, A) ∩ f (q, A) = {p} ∩ {q} = ∅. If p or q
is {x, y, z} (without loss of generality p = {x, y, z}), then f (p, A) only contains triangles
with at least one edge not in F and f (q, A) = {q} contains only a triangle where all edges
are in F . It follows that f (p, A) ∩ f (q, A) = ∅ (K3a).
By construction and by Lemma 4.1, f ({x, y, z}, A) contains all triangles in G where
at least one of the edges is not in F . Since all edges in F are included in GI , all other
triangles are contained in GI (K3b).
It is easy to see that f can be computed in constant-delay time (K3c).
To the best of our knowledge, there is no known algorithm that solves △-Enum
in O(n + m) or constant-delay time.
A straight-forward application of Lemma 3.6 combined with Proposition 4.2 yields the
following.
Theorem 4.3. △-Enum parameterized by feedback edge number k can be solved in O(k 1.5 +
n + m) time.
Proof. By Proposition 4.2, △-Enum parameterized by feedback edge number k admits a
constant-delay enum-advice kernel with at most k edges that can be computed in O(n+ m)
time, where the size of the advice is at most O(k). Itai and Rodeh [34, Theorem 3] showed
that the number of triangles in a graph is upper-bounded by m3/2 and that all triangles
in a graph can be enumerated in O(m3/2 ) time. Let (G, k) be an input instance of △Enum parameterized by feedback edge number and let I(G, k) be the kernel instance of
the described enum-advice kernelization. Since |I(G, k)| ∈ O(k), all solutions can be listed

15

in O(|I(G, k)|3/2) time and the number of triangles in both instances is in O(k 3/2 ). The
statement of the theorem then follows directly from Lemma 3.6.
4.1.2

Distance to d-Degenerate Graphs plus Maximum Degree

Green and Bader [27] stated that Triangle Counting parameterized by the size of a
vertex cover V ′ and the maximum degree dmax = max({deg(v) | v ∈ V ′ }) of vertices in this
vertex cover can be solved in O(|V ′ | · d2max + n) time. We will construct an algorithm which
solves △-Enum parameterized by the distance to d-degenerate graphs, provided that the
respective set is given. Let D be set of vertices such that G − D is d-degenerate, where G
is the input graph, and let ∆D be the maximum degree of a vertex in D with respect
to G. The algorithm takes O(|D| · ∆2D + n · d2 ) time. Bear in mind that for each vertex
cover V ′ it holds that G − V ′ is 0-degenerate and hence O(|D| · ∆2D + n · d2 ) = O(|D| · ∆2D ).
Consequently, our result generalizes the result by Green and Bader.
Proposition 4.4. △-Enum parameterized by distance to d-degenerate graphs and maximum degree ∆D in a set D such that G−D is d-degenerate is solvable in O(|D| · ∆2D + n · d2 )
time provided that the set D is given.
Proof. Let D be a set such that G − D is d-degenerate and let the maximum degree
in D be ∆D = max({degG (v) | v ∈ D}). We show how to list all triangles in G
in O(|D| · ∆2D + n · d2 ) time in two steps.
In the first step, list all triangles which do not contain any vertices in D. To this
end, compute the d-degenerate graph G′ = G − D and list all triangles contained in G′
in O(n · d2 ) time [11].
In the second step, list all triangles with at least one vertex contained in D. To
this end, in linear time fix an arbitrary strict order <a on V (G) such that v <a w for
all v ∈ D, w ∈ V (G′ ). For each u ∈ D, iterate over all of the at most ∆2D possible pairs
of neighbors v, w ∈ N(u). For each pair v, w ∈ N(u), check in constant time whether
(i) {v, w} ∈ E(G) and (ii) u <a v <a w, and list the triangle if both conditions are
met. Let {x, y, z} form a triangle in G with at least one vertex in D, and without loss
of generality let x <a y <a z. Then x ∈ D, and only in the iteration when x is chosen
from D conditions (i) and (ii) are met and hence {x, y, z} is listed. It follows that in
the second step all triangles with at least one vertex in D are enumerated exactly once
in O(|D| · ∆2D ) time.
Using the above ideas, we also provide an enum-advice kernel for △-Enum parameterized by distance to d-degenerate graphs and the maximum degree in the deletion set D.
Observation 4.5. △-Enum parameterized by distance to d-degenerate graphs and maximum degree ∆D in a set D such that G − D is d-degenerate admits a constant-delay
enum-advice kernel provided that the distance deletion set D to d-degenerate graphs is
given. The kernel is of size O(|D| · ∆D · d) and can be computed in O(n · d2 + |D| · ∆D ) time.

16

Proof. The main idea is to only compute the first step of the algorithm in the proof of
Proposition 4.4. Store in the advice all the triangles that are found in the process such
that at least one vertex of the triangle has no neighbor in D. (In this way, we avoid double
counting by having a triangle in the advice and in the kernel.) This first step takes O(n·d2)
time. Then, the kernel contains the subgraph induced by D and all neighbors of vertices
in D. The kernel can be computed in O(n + m) ⊆ O(n · d + |D| · ∆D ) time and the
resulting graph contains at most |D| · (∆D + 1) vertices, at most |D| · ∆D edges with at
least one endpoint in D, and at most |D| · ∆D · d edges with no endpoint in D since G − D
is d-degenerate.
4.1.3

Distance to d-Degenerate Graphs

We next present an enum-advice kernel for △-Enum parameterized by distance to ddegenerate graphs. The ideas for this kernel are a little bit different than for Observation 4.5;
we will, however, start similarly and enumerate all triangles in the d-degenerate subgraph
and store them in the advice.
Theorem 4.6. △-Enum parameterized by distance to d-degenerate graphs admits a constant-delay enum-advice kernel provided that the distance deletion set D to d-degenerate
graphs is given. The kernel contains at most |D| + 2|D| + 3 vertices and can be computed
in O(n · (d + 1) · (|D| + d)) time.
Proof. Let G be an instance of △-Enum and let k = |D| be the parameter. Construct the
enum-advice kernel (I(G, k), A(G, k)) as follows. To this end, we call (GI , k ′ ) ..= I(G, k)
and A ..= A(G, k).
First, compute the d-degenerate graph G′ = G − D. The graph G′ contains exactly
those triangles in G that do not contain any vertices in D. Using a result of Chiba and
Nishizeki [11, Theorem 1], compute the set of triangles in G′ in O(m·d) time. Next, compute
all triangles with exactly one vertex in D. To this end, compute the degeneracy ordering in
linear time [43], iterate over all v ∈ D, u ∈ N(v) \ D, and the at most d neighbors of u that
are ordered after u in the degeneracy order, and list all triangles found. By this, all triangles
in G containing exactly one vertex in D are found in O(k · n · d) time. Altogether, we can
compute the set T1 of all triangles in G with at most one vertex in D in O(n·d·(k+d)) time.
Delete all edges which have no endpoint in D as they cannot be part of any further
triangles. Next, compute all twin class in the current graph, that is, a partition P of the
vertices according to their neighbors, using partition refinement in O(n + m) time [29].
For each non-empty part P ∈ P pick one vertex vP ∈ P and store a function M such
that M(vP ) = P \ D. Put all vertices in D, all of the chosen vertices, and all edges
induced by these vertices into GI . Add three new vertices a, b, c to GI and if T1 6= ∅, then
add three new edges {a, b}, {a, c}, {b, c}. Note that all edges have an endpoint in D ′ =
D ∪ {a, b} and thus D ′ is a deletion set to d-degenerate graphs for every d. Complete
the construction by setting k ′ = |D ′| and A = (T1 , M, {a, b, c}). Note that GI contains at
most k + 2k + 3 vertices (K1). Observe that since m ∈ O(n · (k + d)), the kernel can be

17

constructed in O(n · d · (k + d)) time. For x1 , x2 , x3 ∈ V (GI ), define the function f as
(
T1 , if {x1 , x2 , x3 } = {a, b, c}, and otherwise
f ({x1 , x2 , x3 }, A) ..=
{{v1 , v2 , v3 } | v1 ∈ M(x1 ) ∧ v2 ∈ M(x2 ) ∧ v3 ∈ M(x3 )}.
Next, we prove that the algorithm fulfills all conditions of Definition 3.4.
Observe that GI is isomorphic to a subgraph of G and, hence, if there is a triangle GI ,
then there is a triangle in G. Assume that there is a triangle X with vertices {x1 , x2 , x3 }
in G. If X contains at most one vertex in D, then T1 6= ∅ and thus there is the triangle
formed by {a, b, c} in GI . Otherwise, X contains at least two vertices in D. Assume
without loss of generality that x2 , x3 ∈ D. If x1 is in D, then X is also contained in GI .
Otherwise, there is a vertex v in GI such that x1 ∈ M(v). Since {x1 , x2 , x3 } forms a triangle
in G, it follows that {v, x2 , x3 } forms a triangle in G and GI . Hence, condition (K2) (of
Definition 3.4) is fulfilled.
Next we discuss the condition (K3). We will prove that for each triangle X = {x1 , x2 , x3 }
in G there is a unique solution w ∈ Sol(GI , k ′ ) such that X ∈ f (w, A) (K3b). If X contains at most one vertex in D, then by construction X ∈ f ({a, b, c}, A). Since GI contains only edges with an endpoint in D, no triangle {v1 , v2 , v3 } where v1 ∈ M(x1 ), v2 ∈
M(x2 ), and v3 ∈ M(x3 ) is contained in GI . Thus, {a, b, c} is the only triangle T such
that X ∈ f (T, A). If X contains at least two vertices x2 , x3 ∈ D, then there exists a
vertex v in GI such that x1 ∈ M(v) and the triangle {v, x2 , x3 } is contained in G. By
construction, the triangle {v, x2 , x3 } is also contained in GI and X ∈ f ({v, x2 , x3 }, A).
Since X ∈
/ T1 , it follows X ∈
/ f ({a, b, c}, A).
Next we show that for any two triangles p = {u1, u2 , u3 } and q = {v1 , v2 , v3 } in GI , it
holds that f (p, A) ∩ f (q, A) = ∅ (K3a).
If either p or q is {a, b, c} (without loss of generality p = {a, b, c}), then by definition f (p, A) only contains triangles with at most one vertex in D and f (q, A) only contains
triangles with at least two vertices in D and thus f (p, A) ∩ f (q, A) = ∅.
If neither p nor q is {a, b, c}, then both of them only contain vertices from the original graph G. As p 6= q, assume without loss of generality that u1 ∈
/ q and v1 ∈
/ p.
By construction all triangles in f (p, A) contain one vertex in M(u1 ) and all triangles
in f (q, A) contain one vertex in M(v1 ). As shown above, M(u1 ) (M(v1 ), respectively)
only contains u1 (v1 ) and vertices that have the same neighbors as u1 (v1 ) in D. Hence,
no triangle in f (p, A) (f (q, A) respectively) contains a vertex in M(v1 ) (M(u1 )) and
thus f (p, A) ∩ f (q, A) = ∅.
Each triangle in {{v1 , v2 , v3 } | v1 ∈ M(x1 ) ∧ v2 ∈ M(x2 ) ∧ v3 ∈ M(x3 )} and in T1 can
be returned with constant delay between generating two successive solutions (K3c).
Overall, the time needed to compute the kernel (I(G, |D|), A(G, |D|)) is upper-bounded
by O(n · d · (|D| + d) + |D| + m) = O(n · (d + 1) · (|D| + d)). The equality holds
since m ∈ O(n · (|D| + d)).
To the best of our knowledge, there is no algorithm that solves △-Enum parameterized
by distance to d-degenerate graphs within O(n · d2 + |D| · ∆D ) time. All solutions can be
18

reconstructed in constant-delay time and there is no known algorithm that solves △-Enum
in constant-delay time (and it seems unlikely that such an algorithm exists).
Using Lemma 3.6 and Theorem 4.6 we get the following result.
Corollary 4.7. △-Enum parameterized by distance to d-degenerate graphs is solvable
in O(n · (d + 1) · (|D| + d) + 23|D| + #T) time provided that the vertex-deletion set D to
d-degenerate graphs is given.
Proof. By Theorem 4.6, △-Enum parameterized by the distance to d-degenerate graphs
(provided that the set D such that G − D is d-degenerate is given) admits a constant-delay
enum-advice kernel with size O(22|D| ) that can be computed in O(n · (d + 1) · (|D| + d))
time. Hence, all triangles in the kernel instance can be found in O(23|D| ) time [34]. Since
the delay is constant and the number of triangles in both graphs is at most #T, we can
compute all triangles in the original instance from all solutions in the kernel in O(#T) time.
Thus, by Lemma 3.6, △-Enum is solvable in O(n · (d + 1) · (|D| + d) + 23|D| + #T) time
parameterized by distance to d-degenerate graphs assuming that the set D is given.

4.2

Parameters Incomparable with Degeneracy

In this section we present results on parameters that are unrelated to the degeneracy.
Again, we first describe the parameters and then turn to our results.
In Section 4.2.1, we consider the vertex-deletion distance to cographs, bipartite, or
chordal graphs. A graph is bipartite if its set of vertices can be partitioned into two sets
such that no edge in the graph has both endpoints in one of the sets. A graph is called
chordal if it does not contain induced cycles of length at least four. A graph is called a
cograph if it contains no induced path with four vertices (P4 ).
We show below that enumerating all triangles is easy if the input graph falls into one of
the three graph classes. Thus, the three parameters mentioned above are natural candidates
for a “distance-to-triviality” approach [28]. Furthermore, all three parameters are upperbounded by the vertex cover number. The vertex cover number allows for tractability
results (see Section 4.1). Thus, aiming at generalizing the tractability result, we arrive at
the study of these parameters. Moreover, two of these parameters are lower-bounded by
parameters for which we know intractability, see Figure 4. Thus, we also investigate the
limits of how far we can generalize the tractability results.
Distance to cographs lower-bounds the cluster vertex number—a parameter advocated
by Doucha and Kratochvı́l [17] by proving that several basic graph theoretic problems
parameterized by it are fixed-parameter tractable (note that the parameter lies between
the vertex cover number and clique-width). Moreover, given a graph G, we can determine in
linear time whether G is a cograph and, if this is not the case, return an induced P4 [8, 12].
This implies that in O(k · (m + n)) time, with k being the distance to cographs, we can
compute a set K ⊆ V of size at most 4k such that G − K is a cograph. However, we are
not aware of (parameterized) linear-time constant-factor approximation algorithms for the
other two parameters.
19

In Section 4.2.2, we consider the parameter clique-width. Since treewidth is lowerbounded by degeneracy, we know that there is an O(ω · m)-time algorithm for △-Enum,
where ω is the treewidth of the input graph. A parameter lower bounding treewidth in the
parameter hierarchy is clique-width k (it holds that k ≤ 2ω+1 + 1 and k can be arbitrarily
small compared to ω [15]). Moreover, clique-width also lower-bounds distance to cograph.
Thus, we study clique-width as it lies on the “border to tractability” of △-Enum.
4.2.1

Distance to Bipartite Graphs, Chordal Graphs, or Cograph

We give linear-time FPT algorithms for △-Enum with respect to the distance to bipartite,
distance to chordal, and distance to cographs, respectively. Our main results in this section
are summarized in the following.
Theorem 4.8. △-Enum is solvable in O(n + k · m + M) time
(a) with M = 0, when parameterized by the distance k to bipartite graphs, provided that
the deletion set is given;
(b) with M = #T, when parameterized by the distance k to chordal graphs, provided that
the deletion set is given;
(c) with M = #T, when parameterized by the distance k to cographs.
In order to prove Theorem 4.8, we provide a general lemma which can be used to
solve △-Enum with a given (vertex) deletion set to some graph class Π if all triangles in Π
can be enumerated efficiently.
Lemma 4.9. △-Enum with a given vertex-deletion set K to Π is solvable in O(m · |K| +
n + M) time if △-Enum on every graph in Π is solvable in O(M) time.
Proof. Let K be a set of vertices such that G′ = G − K is a graph contained in Π. By
assumption, all triangles within G′ can be listed in O(M) time. All triangles with at least
one vertex in K can be listed in O(m · |K| + n) time by the following algorithm. Read
the whole input and fix an arbitrary linear order ≤a of the vertices in K in O(n + m)
time. Check for each edge {u, w} ∈ E(G) and each vertex v ∈ K whether {u, v, w} is a
triangle and for all x ∈ {u, w} ∩ K it holds that v ≤a x. If both conditions hold, then list
{u, v, w} as a new triangle. We prove that this algorithm lists all triangles with at least
one vertex in K exactly once. Since v ∈ K holds, this algorithm does not list any triangles
which do not contain vertices in K. Let {a, b, c} be an arbitrary triangle and let a be in
K. This triangle is found at least once as {b, c} ∈ E and a ∈ K holds. If for all x ∈ {b, c}
it holds that x ∈
/ K or a ≤a x, then this triangle is listed in the iteration where v = a
and {u, w} = {b, c}. Otherwise, b ≤a a or c ≤a a holds. Without loss of generality, let b be
such that b ≤a y with y ∈ {a, b, c} ∩ K. Then {a, b, c} is listed in the iteration where v = b
and {u, w} = {a, c} holds. There are m · |K| iterations and each iteration takes constant
time. Thus, △-Enum parameterized by deletion set to Π is solvable in O(m · |K| + n)
time.
20

Theorem 4.8 follows immediately from applying Lemma 4.9 with Π being the class of
bipartite graphs, of chordal graphs, and of cographs. To this end, in the remainder of
this section, we provide the remaining requirements to apply Lemma 4.9, that is, we give
the running times in which △-Enum is solvable on bipartite graphs (Observation 4.10),
chordal graphs (Proposition 4.11), and cographs (Proposition 4.12).
Distance to Bipartite Graphs. Since bipartite graphs do not contain cycles of odd
length and thus are triangle-free, △-Enum is solvable in constant time on bipartite graphs
after reading the input.
Observation 4.10. △-Enum is solvable in O(n + m) time on bipartite graphs.
Distance to Chordal Graphs. For each chordal graph there is a perfect elimination
order ≤p of the vertices which can be computed in linear time. That is, for each vertex v
all neighbors w of v with v ≤p w form a clique. We will use this to find all triangles in
chordal graphs in O(#T + n + m) time and thus by Lemma 4.9 solve △-Enum given a
deletions set K to chordal graphs in O(#T + n + m · |K|) time. Recall that #T is the
number of triangles in G. Note that a clique containing n vertices contains O(n3 ) triangles
and that graphs consisting of only one large clique are chordal. We therefore cannot avoid
the term #T in the running time.
Proposition 4.11. △-Enum is solvable in O(#T + n + m) time on chordal graphs.
Proof. Compute the perfect elimination ordering in O(n + m) time. Next, list all triangles
containing the first vertex in this ordering and delete it afterwards. Proceed in this manner
until no vertex is left.
Let v be the vertex at the first position in the perfect elimination ordering in some
iteration. Listing all triangles containing v can be done as follows. As v is the first
vertex in the ordering, there are no vertices before v and, by the definition of a perfect
elimination ordering, N(v) forms a clique. Hence, v combined with any two of its neighbors
forms a triangle. Thus, we list all triangles of the form {v, x, y} with x ∈ N(v), y ∈ N(v),
and x 6= y. Once all of these triangles are listed, v is not contained in any triangle not
being listed and hence one can delete it.
Distance to Cograph. We now show how to enumerate all triangles in a cograph. To
this end, we need the following notation. Every cograph has a binary cotree representation
which can be computed in linear time [12]. A cotree is a rooted tree in which each leaf
corresponds to a vertex in the cograph and each inner node either represents a disjoint
union or a join of its children. A join of two graphs (V1 , E1 ), (V2 , E2 ) with V1 ∩ V2 = ∅ is
the graph (V1 ∪ V2 , E1 ∪ E2 ∪ {{x, y} | x ∈ V1 ∧ y ∈ V2 }). We will use these representations
to find all triangles in cographs in O(#T + n + m) time, where #T is the number of
triangles in G. Note that one can compute a set K of size at most 4k such that G − K
is a cograph, where k is the size of a minimum set K ′ such that G − K ′ is a cograph,
in O(k · (n + m)) time.
21

Proposition 4.12. △-Enum is solvable in O(#T + n + m) time on cographs.
Proof. Consider a dynamic program which stores for each node p in the cotree all vertices V (p), all edges E(p) and all triangles T (p) in the corresponding subgraph of G. This
can be done as follows:
Let q1 , q2 be the children of an inner node p in the cotree.
• A single leaf node has one vertex and no edges or triangles.
• A union node has vertices V (q1 )∪V (q2 ), edges E(q1 )∪E(q2 ), and triangles T (q1 ) ∪ T (q2 ).
• A join node has
V (p) = V (q1 ) ∪ V (q2 ),
E(p) = E(q1 ) ∪ E(q2 ) ∪ {{x, y} | x ∈ V (q1 ) ∧ y ∈ V (q2 )}, and
T (p) = T (q1 ) ∪ T (q2 ) ∪ {{x, y, z} | x ∈ V (q1 ) ∧ {y, z} ∈ E(q2 )}∪
{{x, y, z} | x ∈ V (q2 ) ∧ {y, z} ∈ E(q1 )}.
That is, a join node contains all edges the two children contain and all possible edges
between vertices of them. A join node contains all triangles its two child-nodes contain
and one triangle for each edge {y, z} of one of its children and a vertex x of the other,
because edges {x, y} and {x, z} are in E and therefore {x, y, z} is a triangle.
We will first prove that all triangles are enumerated that way and afterwards we will
analyze the running time of the dynamic program.
Let {a, b, c} be any triangle in the cograph. We will prove that there is at least one
node p in the cotree with {a, b, c} ∈ T (p). As each inner node keeps the triangles from its
children, it follows that {a, b, c} ∈ T (r) when r is the root node of the cotree. Let without
loss of generality be p the least common ancestor of a, b, and c, and let q1 , q2 be the two
children of p. As neither {a, b, c} ∈ V (q1 ) nor {a, b, c} ∈ V (q2 ), let us assume without loss
of generality that a ∈ V (q1 ) and b, c ∈ V (q2 ). It holds that {b, c} ∈ E(q2 ) because there is
an edge between b and c and they are both descendants of q2 . The node p has to be a join
node as {a, b}, {a, c} ∈ E and p is by definition the least common ancestor. By definition it
holds that {{x, y, z} | x ∈ V (q1 ) ∧ {y, z} ∈ E(q2 )} ⊆ T (p). It follows that {a, b, c} ∈ T (p).
Note that {a, b, c} is only computed once in the least common ancestor node p and then
passed to the parent node. Hence, T (r) only contains {a, b, c} once and thus listing all
triangles in T (r) solves △-Enum.
We will now analyze the running time. There are n leaf nodes in the cotree each of
which require a constant amount of time to compute. There are at most n − 1 union nodes
each of which only require a constant amount of time as they only need to point on their
children’s values. There are at most n − 1 join nodes. Each edge and triangle is only
added once and all other values do not need to be recomputed. A pointer to the edges and
triangles in the children nodes is enough and only require a constant amount of time to be
set. Altogether, the global running time of this algorithm is in O(#T + n + m).
22

4.2.2

Clique-width

We next turn to the parameter clique-width as it is incomparable to the degeneracy and
upper-bounded by two parameters allowing for linear-time FPT algorithms: the distance
to cographs (Proposition 4.12) and treewidth (as treewidth upper-bounds the degeneracy).
The clique-width of a graph G is the minimum number k such that G can be constructed
using a k-expression. A k-expression consists of four operations which use k labels [14].
The operations are the following.
• Creating a new vertex with some label i.
• Disjoint union of two labeled graphs.
• Edge insertion between every vertex with label i to every vertex with label j for some
labels i 6= j.
• Renaming of label i to j for some i, j.
Let V1 ⊆ V be a set of vertices. A twin class in V1 is a set V ′ ⊆ V1 of vertices such that
every vertex in V \ V1 either has all vertices in V ′ as its neighbors or none of them. The
set V1 is called an ℓ-module if it can be partitioned into at most ℓ twin classes. Let B be
a rooted full binary tree whose leaves are in bijection to the vertices in V . For each inner
node p in B let Vp ⊆ V be the set of all vertices in G whose corresponding nodes in B are
in the induced subtree of B rooted at p. If for each inner node p in B the set Vp is an ℓmodule, then B is an ℓ-module decomposition. We will use this ℓ-module decomposition
to construct a dynamic program to solve △-Enum parameterized by some k-expression
in O(n2 + k 2 · n + #T) time.
We leave open whether △-Enum parameterized by clique-width k admits a linear FPT
algorithm. Our results suggest that the parameters clique-width and average degree form
the border case between parameters admitting linear FPT algorithms and those that are
GP-hard.
Theorem 4.13. △-Enum parameterized by clique-width is solvable in O(n2 + n · k 2 + #T)
time, provided that a k-expression of the input graph is given.
Proof. Recall that #T is the number of triangles in G. Bui-Xuan et al. [9, Lemma 3.2]
proved the following: First, given a k-expression tree B of G one can compute in overall O(n2 ) time for every node u in B the partition of Vu into its twin classes Qu (1), . . . , Qu (hu )
where Vu is the set of vertices corresponding to the leaves of the subtree of B rooted at u.
Second, the maximum number hu of twin classes for each node u in B is at most k. Third, B
can be modified such that it becomes a full binary tree and thus combined with the twin
classes becomes a k-module decomposition of G. Fourth, the k-module decomposition has
only a single twin class in the root node and each twin class of a node u in B is fully
contained in one of the twin classes of the parent v of u. We use these statements in our
algorithm.
23

We next describe which information is stored in our dynamic program. First, store the
information that all vertices in Qu (i) are contained in the twin class Qv (b) by adding i to
a set Mu,b .
Next, for each node v in B store Qv (1), . . . , Qv (hv ), the twin classes of v (which
v
are already computed), the set Ei,j
of all edges between vertices in twin classes Qv (i)
and Qv (j) (1 ≤ i, j ≤ hv ), and the set LT v of all triangles formed by vertices in Vv . Denote
by Fu,a,w,b the set of all edges with one endpoint in Qu (a) and one in Qw (b) where u and w
have the same parent in B, formally, Fu,a,w,b = {{x, y} | x ∈ Qu (a) ∧ y ∈ Qw (b)} ∩ E.
Note that by the definition of twin classes, either all vertices of the twin classes of two
nodes with the same parent in B are pairwise connected or none of them are.
The dynamic program is defined as follows. A leaf node v in B has an empty set of triangles and only empty edge sets. An inner node v with children u, w has for each 1 ≤ i, j ≤ hv
an edge set
[
[
[ [
[
[
[
[
v
u
w
Fu,m,w,l
Fu,m,w,l ∪
Ei,j
=
El,m
∪
El,m
∪
l∈Mu,i m∈Mu,j

l∈Mw,i m∈Mw,j

m∈Mu,i l∈Mw,j

m∈Mu,j l∈Mw,i

and a set of triangles
LT v = LT u ∪ LT w ∪ LTu,u,w ∪ LTw,w,u
where
LTx,x,y =

hy
hx [
hx [
[

{{a, b, c} | a ∈ Qx (o) ∧ b ∈ Qx (p) ∧ c ∈ Qy (q) ∧

o=1 p=o q=1
x
Fx,o,y,q 6= ∅ ∧ Fx,p,y,q 6= ∅ ∧ {a, b} ∈ Eo,p
}.

We next analyze the running time and then the correctness of the dynamic program.
The table entries for each of the n leaves in B can be computed in constant time. For each
of the n − 1 inner nodes, at most k 2 sets of edges have to be computed, each of which is
built out of two parts: edges already stored in the children and edges between vertices of
different children. The former requires O(k 2 ) time per node as it can be seen as a list of
pointers to the children’s sets of edges. The latter requires O(m) global time as each edge
is only added once. Hence, the edge sets of all nodes can be computed in O(n·k 2 +m) time.
The list of triangles is a list containing two pointers to its children’s list of triangles and a
third list of new triangles. As each triangle is only added once, all lists can be computed
in O(#T +n) time.
We will prove that each triangle {x, y, z} is found in the least ancestor node p of x, y,
and z. As each node in B references the triangles of its children, {x, y, z} is passed on to the
root node in B. Note that each node in B only computes those new triangles which have
one vertex in the subtree rooted in one child node and two vertices in the subtree rooted
in the other child node. Thus each triangle is computed at most once. Let q and r be
the children of p and let without loss of generality be x ∈ Qq (s), y ∈ Qq (t) and z ∈ Qr (u).
Since {x, z}, {y, z} ∈ E, it holds that Fq,s,r,u 6= ∅ and Fq,t,r,u 6= ∅. Moreover, it holds
24

q
that {x, y} ∈ Es,t
because x ∈ Qq (s), y ∈ Qq (t), and {x, y} ∈ E. Hence, {x, y, z} is
contained in

q
,
{a, b, c} | a ∈ Qq (s) ∧ b ∈ Qq (t) ∧ c ∈ Qr (u) ∧ Fq,s,r,u 6= ∅ ∧ Fq,t,r,u 6= ∅ ∧ {a, b} ∈ Es,t

which is a subset of LTq,q,r which itself is a subset of LT p .

5

Conclusion

Employing the framework of FPT-in-P analysis [25], we provided novel notions and insights
concerning potentially faster solution algorithms for enumerating (and detecting) triangles
in undirected graphs. It remains to be seen whether General-Problem-hardness is an
appropriate notion for intractability within the field of FPT-in-P. So far, there is still little
work on kernelization in the context of enumeration problems. We hope that the notion
of enum-advice kernels can be used to further develop this area of research.
As previously observed by Ortmann and Brandes [47], the parameterized algorithm of
Chiba and Nishizeki [11] is quite old but it is still very competitive. Experiments revealed
that their algorithm could enumerate all triangles on social networks with several hundred
thousand vertices within a few seconds. Our algorithms had to perform less operations,
we were, however, not able to beat the actual running time of the algorithm by Chiba and
Nishizeki [11]. An analysis revealed that their algorithm uses main memory of modern
computers with their memory hierarchy more efficiently. In particular, our algorithms
access data that is scattered throughout the memory. We conclude that the main direction
for further practical improvement for △-Enum should include aspects of memory-efficiency
in the algorithm design process. A first step into this direction has already been done by
Hu et al. [30].
It remains open to study whether our exponential-size kernel for parameter distance to
d-degenerate graphs (see Theorem 4.6) can be improved in terms of size and running time.
On a more general scale, note that triangles are the smallest non-trivial cliques as well
as cycles. Can one generalize our findings to these two different settings when increasing
the subgraph size? Finally, we mention that following the FPT-in-P route might be an
attractive way to “circumvent” lower bound results for other polynomial-time solvable
problems. To this end, a systematic exploration of parameter landscapes (cf. Sorge and
Weller [52] or Figure 4) and parameter combinations [46] seems beneficial.

References
[1] Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for
dynamic problems. In Proc. 55th FOCS, pages 434–443. IEEE Computer Society, 2014. 1, 6
[2] Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proc. 27th SODA, pages
377–391. SIAM, 2016. 2

25

[3] Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing
hardness on an extremely popular conjecture. In Proc. 47th STOC, pages 41–50. ACM, 2015. 3
[4] Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M. Roth. Approximation algorithms for
the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference.
SIAM Journal on Computing, 27(4):942–959, 1998. 14
[5] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proc. 13th SODA, pages 623–632. ACM/SIAM, 2002.
2
[6] Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algorithms
for local triangle counting in massive graphs. In Proc. 14th ACM KDD, pages 16–24. ACM, 2008. 2
[7] Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles.
In Proc. 41st ICALP, volume 8572 of LNCS, pages 223–234. Springer, 2014. 2
[8] Anna Bretscher, Derek G. Corneil, Michel Habib, and Christophe Paul. A simple linear time LexBFS
cograph recognition algorithm. SIAM Journal on Discrete Mathematics, 22(4):1277–1296, 2008. 19
[9] Binh-Minh Bui-Xuan, Ondrej Suchý, Jan A. Telle, and Martin Vatshelle. Feedback vertex set on
graphs of low clique-width. European Journal of Combinatorics, 34(3):666–679, 2013. 23
[10] Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, and Rasmus Pagh. Triangle counting in
dynamic graph streams. Algorithmica, 76(1):259–278, 2016. 2
[11] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on
Computing, 14(1):210–223, 1985. 2, 12, 13, 16, 17, 25
[12] Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A linear recognition algorithm for cographs.
SIAM Journal on Computing, 14(4):926–934, 1985. 19, 21
[13] David Coudert, Guillaume Ducoffe, and Alexandru Popa. Fully polynomial FPT algorithms for some
classes of bounded clique-width graphs. CoRR, abs/1707.05016, 2017. 2
[14] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems
on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125–150, 2000. 23
[15] Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied
Mathematics, 101(1-3):77–114, 2000. 20
[16] Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer.
Paradigms for parameterized enumeration. Theory of Computing Systems, 60(4):737–758, 2017. 5, 9,
10, 12
[17] Martin Doucha and Jan Kratochvı́l. Cluster vertex deletion: A parameterization between vertex cover
and clique-width. In Proc. 37th MFCS, volume 7464 of LNCS, pages 348–359. Springer, 2012. 19
[18] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer,
2013. 10
[19] David Eppstein and Emma S. Spiro. The h-index of a graph and its application to dynamic subgraph
statistics. Journal of Graph Algorithms and Applications, 16(2):543–567, 2012. 2
[20] Emilio Ferrara. Measurement and analysis of online social networks systems. In Encyclopedia of
Social Network Analysis and Mining, pages 891–893. Springer New York, 2014. 14
[21] Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and
Nimrod Talmon. When can graph hyperbolicity be computed in linear time? In Proc. 15th WADS,
volume 10389 of LNCS, pages 397–408. Springer, 2017. 2

26

[22] Till Fluschnik, George B. Mertzios, and André Nichterlein. Kernelization lower bounds for finding
constant size subgraphs. CoRR, abs/1710.07601, 2017. 3
[23] Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, and Marcin Wrochna. Fully
polynomial-time parameterized computations for graphs and matrices of low treewidth. In Proc. 28th
SODA, pages 1419–1432. SIAM, 2017. 2
[24] D. W. Franks, J. Noble, P. Kaufmann, and S. Stagl. Extremism propagation in social networks with
hubs. Adaptive Behavior, 16(4):264–274, 2008. 12
[25] Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter
algorithms: A case study for longest path on interval graphs. Theoretical Computer Science, 689:67–
95, 2017. 2, 25
[26] Carsten Grabow, Stefan Grosskinsky, Jürgen Kurths, and Marc Timme. Collective relaxation dynamics of small-world networks. Physical Review E, 91:052815, May 2015. 2
[27] Oded Green and David A. Bader. Faster clustering coefficient using vertex covers. In Proc. 6th
SocialCom, pages 321–330. IEEE Computer Society, 2013. 2, 16
[28] Jiong Guo, Falk Hüffner, and Rolf Niedermeier. A structural view on parameterizing problems:
Distance from triviality. In Proc. 1st IWPEC, volume 3162 of LNCS, pages 162–173. Springer, 2004.
19
[29] Michel Habib, Christophe Paul, and Laurent Viennot. A synthesis on partition refinement: A useful
routine for strings, graphs, boolean matrices and automata. In Proc. of STACS 1998, volume 1373
of LNCS, pages 25–38. Springer, 1998. 17
[30] Xiaocheng Hu, Yufei Tao, and Chin-Wan Chung. I/O-efficient algorithms on triangle listing and
counting. ACM Transactions on Database Systems, 39(4):27:1–27:30, 2014. 25
[31] Thore Husfeldt. Computing graph distances parameterized by treewidth and diameter. In Proc. 11th
IPEC, volume 63 of LIPIcs, pages 16:1–16:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2016. 2
[32] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and
System Sciences, 62(2):367–375, 2001. 3
[33] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. 3
[34] Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing,
7(4):413–423, 1978. 1, 13, 15, 19
[35] Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems, 41(4):22:1–22:45, 2016.
2
[36] Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. Efficient
triangle counting in large graphs via degree-based vertex partitioning. Internet Mathematics, 8(12):161–185, 2012. 2
[37] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Dynamic set intersection. In Proc. 14th WADS, volume
9214 of LNCS, pages 470–481. Springer, 2015. 2
[38] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In
Proc. 27th SODA, pages 1272–1287. SIAM, 2016. 2
[39] Sofiane Lagraa and Hamida Seba. An efficient exact algorithm for triangle listing in large graphs.
Data Mining and Knowledge Discovery, 30(5):1350–1369, 2016. 2

27

[40] Matthieu Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs.
Theoretical Computer Science, 407(1-3):458–473, 2008. 1, 2
[41] Troy Lee, Frédéric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle
detection and associativity testing. Algorithmica, 77(2):459–486, 2017. 2
[42] John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is
NP-complete. Journal of Computer and System Sciences, 20(2):219–230, 1980. 13
[43] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring
algorithms. J. ACM, 30(3):417–427, 1983. 17
[44] George B. Mertzios, André Nichterlein, and Rolf Niedermeier. The power of linear-time data reduction
for maximum matching. In Proc. 42nd MFCS, volume 83 of LIPIcs, pages 46:1–46:14. Schloss Dagstuhl
- Leibniz-Zentrum fuer Informatik, 2017. 2
[45] Mark E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167–256,
2003. 2
[46] Rolf Niedermeier. Reflections on multivariate algorithmics and problem parameterization. In Proc.
27th STACS, volume 5 of LIPIcs, pages 17–32. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
2010. 25
[47] Mark Ortmann and Ulrik Brandes. Triangle listing algorithms: Back from the diversion. In Proc.
16th ALENEX, pages 1–8. SIAM, 2014. 25
[48] Ha-Myung Park, Francesco Silvestri, U. Kang, and Rasmus Pagh. MapReduce triangle enumeration
with guarantees. In Proc. of CIKM 2014, pages 1739–1748. ACM, 2014. 2
[49] Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd STOC,
pages 603–610. ACM, 2010. 2
[50] J. J. Potterat, L. Phillips-Plummer, S. Q. Muth, R. B. Rothenberg, D. E. Woodhouse, T. S.
Maldonado-Long, H. P. Zimmerman, and J. B. Muth. Risk network structure in the early epidemic
phase of HIV transmission in Colorado Springs. Sexually Transmitted Infections, 78:159–163, 2002.
12
[51] Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an
experimental study. In Proc. 4th WEA, volume 3503 of LNCS, pages 606–609. Springer, 2005. 2
[52] Manuel Sorge and Mathias Weller. The graph parameter hierarchy. Unpublished Manuscript, TU
Berlin, 2016. 12, 25
[53] Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and
triangle problems. In Proc. 51st FOCS, pages 645–654. IEEE Computer Society, 2010. 3
[54] Yang Zhang and Srinivasan Parthasarathy. Extracting analyzing and visualizing triangle k-core motifs
within networks. In Proc. 28th ICDE, pages 1049–1060. IEEE Computer Society, 2012. 2

28

