arXiv:1607.04002v2 [] 25 Apr 2017

Directed Hamiltonicity and Out-Branchings
via Generalized Laplacians
Andreas Björklund 1 , Petteri Kaski2 , and Ioannis Koutis3
1

Department of Computer Science, Lund University, andreas.bjorklund@yahoo.se
2
Department of Computer Science, Aalto University, petteri.kaski@aalto.ﬁ
3
Computer Science Department, UPR Rio Piedras, ioannis.koutis@upr.edu

Abstract
We are motivated by a tantalizing open question in exact algorithms: can we detect
whether an n-vertex directed graph G has a Hamiltonian cycle in time signiﬁcantly less
than 2n ?
We present new randomized algorithms that improve upon several previous works:
a. We show that for any constant
0 < λ < 1 and prime p we can count the Hamiltonian
n
cycles modulo p⌊(1−λ) 3p ⌋ in expected time less than cn for a constant c < 2 that
depends only on p and λ. Such an algorithm was previously known only for the case
of counting modulo two [Björklund and Husfeldt, FOCS 2013].
b. We show that we can detect a Hamiltonian cycle in O∗ (3n−α(G) ) time and polynomial space, where α(G) is the size of the maximum independent set in G. In particular, this yields an O∗ (3n/2 ) time algorithm for bipartite directed graphs, which
is faster than the exponential-space algorithm in [Cygan et al., STOC 2013].
Our algorithms are based on the algebraic combinatorics of “incidence assignments” that
we can capture through evaluation of determinants of Laplacian-like matrices, inspired
by the Matrix–Tree Theorem for directed graphs. In addition to the novel algorithms
for directed Hamiltonicity, we use the Matrix–Tree Theorem to derive simple algebraic
algorithms for detecting out-branchings. Speciﬁcally, we give an O∗ (2k )-time randomized
algorithm for detecting out-branchings with at least k internal vertices, improving upon
the algorithms of [Zehavi, ESA 2015] and [Björklund et al., ICALP 2015]. We also present
an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial
detection problem.

1

Introduction

The Hamiltonian cycle problem has played a prominent role in development of techniques
for the design of exact algorithms for hard problems. The early O ∗ (2n ) algorithms based on
dynamic programming and inclusion-exclusion [1, 20, 19], remained un-challenged for several
decades. In 2010, Björklund [3], gave a randomized algorithm running in O(1.657n ) time for
the case of undirected graphs. The algorithm taps into the power of algebraic combinatorics,
and in particular determinants that enumerate cycle covers.

1

Despite this progress in the undirected Hamiltonian cycle problem, a substantial improvement
in the more general directed version of the problem remains an open problem and a key
challenge in √
the area of exact algorithms. The currently best known general algorithm runs
n−Θ( n/ log n)
∗
in O (2
) time [4], and there are no known connections with the theory of SETHhardness [18] that would—at least partly—dash the hope for a faster algorithm.
A number of recent works have attempted to crack directed Hamiltonicity, revealing that the
problem is indeed easier in certain restricted settings. Cygan and Pilipczuk [12] showed that
the problem admits an O∗ (2(1−ǫd )n ) time algorithm for graphs with average degree bounded by
d, where ǫd is a constant with a doubly exponential dependence on d. Cygan et al. [11] showed
that the problem admits an O ∗ (1.888n ) time randomized algorithm for bipartite graphs and
that the parity of directed Hamiltonian cycles can also be computed within the same time
bound. Björklund and Husfeldt [6] showed that the parity of Hamiltonian cycles can be computed in O∗ (1.619n ) randomized time in general directed graphs. Finally, Björklund et al. [5]
showed that the problem can be solved in O ∗ ((2 − Θ(1))n ) time when the graph contains
less than 1.038n Hamiltonian cycles, via a reduction to the parity problem. In this paper we
improve or generalize all of these works.
Our results. As one would expect, all recent “below-2n ” algorithm designs for the Hamiltonicity problem rely on algebraic combinatorics and involve formulas that enumerate Hamiltonian cycles. But somewhat surprisingly, none of these approaches employs the directed
version of the Matrix–Tree Theorem (see e.g. Gessel and Stanley [17, §11]), one of the most
striking and beautiful results in algebraic graph theory. The theorem enables the enumeration of spanning out-branchings, that is, rooted spanning trees with all arcs oriented away
from the root, via a determinant polynomial. Our results in this paper derive from a detailed
combinatorial understanding and generalization of this classical setup.
The combinatorial protagonist of this paper is the following notion that enables a “two-way”
possibility to view each arc in a directed graph:
Definition 1 (Incidence assignment). Let G be a directed graph with vertex set V and arc
set E. For a subset W ⊆ V we say that a mapping µ : W → E is an incidence assignment if
for all u ∈ W it holds that µ(u) is incident with u.
In particular, looking at a single arc uv ∈ E, an incidence assignment µ can assign uv in two1
possible ways: as an out-arc µ(u) = uv at u, or as an in-arc µ(v) = uv at v.
From an enumeration perspective the serendipity of this “two-way” possibility to assign an arc
becomes apparent when one considers how an incidence assignment µ can realize a directed
cycle in its image µ(W ). Indeed, let
u1 u2 , u2 u3 , . . . , uℓ−1 uℓ , uℓ u1 ∈ E
be the arcs of a directed cycle C of length ℓ ≥ 2 in G with V (C) ⊆ W . It is immediate that
there are now exactly two2 ways to realize C in the image µ(W ). Namely, we can realize C
1

Strictly speaking we are here assuming that both u ∈ W and v ∈ W . To break symmetry in our applications
we do allow also situations where uv has only one possible assignment due to either u ∈
/ W or v ∈
/ W.
2
Again strictly speaking it will be serendipitous to break symmetry so that certain cycles will have only
one realization instead of two.

2

either (i) using only in-arcs with
µ(u1 ) = uℓ u1 ,

µ(u2 ) = u1 u2 ,

µ(u3 ) = u2 u3 ,

...,

µ(uℓ ) = uℓ−1 uℓ ,

(1)

µ(uℓ ) = uℓ u1 .

(2)

or (ii) using only out-arcs with
µ(u1 ) = u1 u2 ,

µ(u2 ) = u2 u3 ,

µ(u3 ) = u3 u4 ,

...,

Incidence assignments thus enable two distinct ways to realize a directed cycle. Furthermore,
it is possible to switch between (1) and (2) so that only the images of u1 , u2 , . . . , uℓ under
µ are aﬀected. The algebraization of this combinatorial observation is at the heart of the
directed Matrix–Tree Theorem (which we will review for convenience of exposition in Sect. 2)
and all of our results in this paper.
Our warmup result involves a generalization of the directed Hamiltonian path problem, namely
the k-Internal Out-Branching problem, where the goal is to detect whether a given directed
graph contains a spanning out-branching that has at least k internal vertices. This is a wellstudied problem on its own, with several successive improvements the latest of which is an
O∗ (3.617k ) algorithm by Zehavi [25] and an O∗ (3.455k ) algorithm by Björklund et al. [9] for
the undirected version of the problem.
Using a combination of the directed Matrix–Tree Theorem and a monomial-sieving idea due
to Floderus et al. [15], in Sect. 3 we show the following:
Theorem 2 (Detecting a k-Internal Out-Branching). There exists a randomized algorithm
that solves the k-internal out-branching problem in time O∗ (2k ) and with negligible probability
of reporting a false negative.
In Appendix A we give a further application for the k-Leaf problem, that is, detecting a
spanning out-branching with at least k leaves. We note that Gabizon et al. [16] have recently
given another application of the directed Matrix–Tree Theorem for the problem of detecting
out-branchings of bounded degree.
Proceeding to our two main results, in Sect. 4 we observe that the directed Matrix–Tree
Theorem leads to a formula for computing the number of Hamiltonian paths in arbitrary
characteristic by using a standard inclusion–exclusion approach, which leads to a formula
that involves the summation of 2n determinants. To obtain a below-2n design, we present a
way to randomize the underlying Laplacian matrix so that the number of Hamiltonian paths
does not change but in expectation most of the summands vanish modulo a prime power.
Furthermore, to eﬃciently list the non-vanishing terms, we use a variation of an algorithm of
Björklund et al. [8] that was used for a related problem, computing the permanent modulo a
prime power. This leads to our ﬁrst main result:
Theorem 3 (Counting directed Hamiltonian cycles modulo a prime power). For all 0 < λ < 1
there exists a randomized algorithm that, given an n-vertex directed graph and a prime p
as input, counts the number of Hamiltonian cycles modulo p⌊(1−λ)n/(3p)⌋ in expected time
2
O∗ 2n(1−λ /(19p log2 p)) . The algorithm uses exponential space.
A corollary of Theorem 3 is that if G has at most dn Hamiltonian cycles, we can detect one
in time O(cnd ), where d is any ﬁxed constant and cd < 2 is a constant that only depends
3

on d. As a further corollary we obtain a randomized algorithm for counting Hamiltonian
cycles in graphs of bounded average (out-)degree d in O(2(1−ǫd )n ) time. The constant ǫd has
a polynomial dependency in d. Previous algorithms had a constant ǫd with an exponential
dependency on d [7, 12]. (The proofs of these results are relegated to Appendix B.)
Returning to undirected Hamiltonicity, a key to the algorithm in [3] was the observation
that determinants enumerate all non-trivial cycle covers an even number of times. This is
due to the fact that each undirected cycle can be traversed in both directions. By picking a
special vertex, one can break symmetry and force this to happen only for non-Hamiltonian
cycle covers, so that the corresponding monomials cancel in characteristic 2. In Sect. 5 we
present a “quasi-Laplacian” matrix whose determinant enables a similar approach for the
directed case via algebraic combinatorics of incidence assignments, and furthermore enables
one to accommodate a speedup assuming the existence of a good-sized independent set. We
speciﬁcally prove the following as our second main result:
Theorem 4 (Detecting a directed Hamiltonian cycle). There exists a randomized algorithm
that solves the directed Hamiltonian cycle problem on a given directed graph G with a maximum
independent set of size α(G), in O∗ (3n(G)−α(G) ) time, polynomial space and with negligible
probability of reporting a false negative.
Theorem 4 improves and generalizes the exponential-space algorithm of Cygan et al. [11].
Terminology and conventions. All graphs in this paper are directed and without loops
and parallel arcs unless indicated otherwise. For an arc e starting from vertex u and ending
at vertex v we say that u is the tail of e and v is the head of e. The vertices u and v are
the ends of e. A directed graph is connected if the undirected graph obtained by removing
orientation from the arcs is connected. A subgraph of a graph is spanning if the subgraph has
the same set of vertices as the graph. A connected directed graph is an out-branching if every
vertex has in-degree 1 except for the root vertex that has in-degree 0. We say that a vertex is
internal to an out-branching if it has out-degree at least 1; otherwise the vertex is a leaf of the
out-branching. The (directed) Hamiltonian cycle problem asks, given a directed graph G as
input, whether G has a spanning directed cycle as a subgraph. The notation O∗ ( ) suppresses
a multiplicative factor polynomial in the input size. We say that an event parameterized by
n has negligible probability if the probability of the event tends to zero as n grows without
bound.

2

The symbolic Laplacian of a directed graph

This section develops the relevant preliminaries on directed graph Laplacians.
Permutations and the determinant. A bijection σ : U → U of a ﬁnite set U is called
a permutation of U . A permutation σ moves an element u ∈ U if σ(u) 6= u; otherwise σ
fixes u. The identity permutation ﬁxes every element of U . A permutation σ of U is a
cycle of length k ≥ 2 if there exist distinct u1 , u2 , . . . , uk ∈ U with σ(u1 ) = u2 , σ(u2 ) =
u3 , . . . , σ(uk−1 ) = uk , σ(uk ) = u1 and σ ﬁxes all other elements of U . Two cycles are disjoint
if every point moved by one is ﬁxed by the other. The set of all permutations of U forms
4

the symmetric group Sym(U ) with the composition of mappings as the product operation of
the group. Every nonidentity permutation factors into a unique product of pairwise disjoint
cycles. The sign P
ofc a permutation σ that factors into c disjoint cycles of lengths k1 , k2 , . . . , kc
is sgn(σ) = (−1) j=1 (kj −1) . The sign of the identity permutation is 1.
The determinant of a square matrix A with rows and columns indexed by U is the multivariate
polynomial
X
Y
det A =
sgn(σ)
au,σ(u) .
u∈U

σ∈Sym(U )

The punctured Laplacian determinant via incidence assignments. Let G be a directed graph with n vertices. Associate with each arc uv ∈ E = E(G) an indeterminate xuv .
The symbolic Laplacian L = L(G) of G is the n × n matrix with rows and columns indexed
by the vertices u, v ∈ V = V (G) and the (u, v)-entry deﬁned3 by
P

 w∈V :wu∈E xwu if u = v;
ℓuv = −xuv
(3)
if uv ∈ E;


0
if u 6= v and uv ∈
/ E.
Observe that for each v ∈ V we have that column v of L sums to zero because the diagonal
entries cancel the negative oﬀ-diagonal entries. Furthermore, for each u ∈ V we have that
the monomials on row u of L correspond to the arcs incident to u. Indeed, each monomial
at the diagonal corresponds to an in-arc to u, and each monomial at an oﬀ-diagonal entry
corresponds to an out-arc from u. Thus, selecting one monomial from each row corresponds
to selecting an incidence assignment.

To break symmetry, select an r ∈ V . The symbolic Laplacian of G punctured at r is obtained
from L by deleting both row r and column r. We write Lr = Lr (G) for the symbolic Laplacian
of G punctured at r. Let us write Br = Br (G) for the set of all spanning out-branchings
of G with root r ∈ V . The following theorem is well-known (see e.g. Gessel and Stanley [17,
§11]) and is presented here for purposes of displaying a proof that presents the cancellation
argument using incidence assignments.
Q
P
Theorem 5 (Directed Matrix–Tree Theorem). det Lr = H∈Br uv∈E(H) xuv .
Proof. Let us abbreviate Vr = V (G) \ {r} and study the determinant
X
Y
ℓu,σ(u) .
det Lr =
sgn(σ)
σ∈Sym(Vr )

(4)

u∈Vr

In particular,
Qlet us ﬁx an arbitrary permutation σ ∈ Sym(Vr ) and study the monomials of the
polynomial u∈Vr ℓu,σ(u) with the assumption that this polynomial is nonzero.
P From (3) it is
immediate for each u ∈ Vr that ℓu,σ(u) expands either (i) to the diagonal sum w∈V :wu∈E xwu ,
which happens precisely when σ ﬁxes u with σ(u) = u, or (ii) to the oﬀ-diagonal −xuv , which
happens precisely when σ moves u with σ(u) = v.
Let us write M (σ) for the set of all incidence assignments µ : Vr → E with the properties
that (i) each u ∈ Vr ﬁxed by σ is assigned to an in-arc µ(u) = wu ∈ E for some w ∈ V , and
3

Recall that we assume that G is loopless so the entries with u = v are well-defined.

5

(ii) each u ∈ Vr moved by σ is assigned to the unique out-arc µ(u) = uv ∈ E with σ(u) = v.
Let us write f = f (σ) for the number of elements in Vr ﬁxed by σ. It is immediate by (i) and
(ii) that we have
Y
X
Y
xµ(u) .
(5)
ℓu,σ(u) =
(−1)n−1−f (σ)
u∈Vr

u∈Vr

µ∈M (σ)

Next observe that from µ we can reconstruct σ = σ(µ) by (i) setting σ(u) = u for each u
assigned to an in-arc in µ,Sand (ii) setting σ(u) = v for each u assigned to an out-arc uv in
µ. Thus the union M = σ∈Sym(Vr ) M (σ) is disjoint. Let us call the elements of M proper
incidence assignments. By (4) and (5) we have
X
Y
xµ(u) .
(6)
det Lr =
(−1)n−1−f (σ) sgn(σ(µ))
µ∈M

u∈Vr

We claim that an incidence assignment µ is proper if and only if for every u ∈ Vr there is
exactly one u′ ∈ Vr such that µ(u′ ) is an in-arc to u. For the “only if” direction, let σ be the
permutation underlying a proper µ, and observe that vertices moved by σ partition to cycles
so a σ never moves a vertex to a ﬁxed vertex. Thus, we have u′ = u for the points ﬁxed by σ,
and u′ = σ −1 (u) is the vertex preceding u along a cycle of σ for points moved by σ. For the
“if” direction, deﬁne σ(u) = u if u = u′ and σ(u′ ) = u if u′ 6= u. In the latter case we have
µ(u′ ) = u′ u, which means that u′′ 6= u′ and thus σ(u′′ ) = u′ ; by uniqueness of u′ eventually a
cycle must close so σ is a well-deﬁned permutation underlying µ and thus µ is proper.
Let us write Hr for the set of all spanning subgraphs of G with the property that every vertex
in Vr has in-degree 1 and the root r has in-degree 0. From the previous claim it follows that
we can view the set µ(Vr ) = {µ(u) : u ∈ Vr } for a proper µ as an element of Hr . Furthermore,
µ(Vr ) is connected (and hence a spanning out-branching with root r) if and only if µ(Vr ) is
acyclic.
Consider an arbitrary H ∈ Hr . If H has a cycle, let C be the least cycle in H according
to some ﬁxed but arbitrary ordering of the vertices of G. (Observe that any two cycles in
H must be vertex-disjoint and cannot traverse r because r has in-degree 0.) Now consider
an arbitrary proper µ that realizes H by µ(Vr ) = H. The cycle C is realized in µ by either
(1) (in which case σ(µ) ﬁxes all vertices in C), or (2) (in which case σ(µ) traces the cycle
C). Furthermore, we may switch between realizations (1) and (2) so that the number of
ﬁxed points in the underlying permutation changes by |V (C)| and the sign of the underlying
permutation gets multiplied by (−1)|V (C)|−1 . It follows that the realizations (1) and (2) have
diﬀerent signs and thus cancel each other in (6). If H does not have a cycle, that is, H ∈ Br ,
it follows that there is a unique proper µ that realizes H. Indeed, ﬁrst observe that H can
be realized only by assigning in-arcs since any assignment of an out-arc in µ implies a cycle
in H = µ(Vr ), a contradiction. Second, the in-arcs are unique since each u ∈ Vr has indegree 1 in H. Finally, since µ assigns only in-arcs the underlying permutation σ(µ) is the
identity permutation which has sgn(σ(µ)) = 1 and (−1)n−1−f (σ(µ)) = 1. Thus, each acyclic
H contributes to (6) through a single µ ∈ M with coeﬃcient 1. The theorem follows.

6

3

Corollary for k-internal out-branchings

This section proves Theorem 2. We rely on a substitution idea of Floderus et al. [15, Theorem 1] to detect monomials with at least k distinct variables.
Let G be an n-vertex directed graph given as input together with a nonnegative integer k.
Without loss of generality we may assume that k ≤ n − 1. Iterate over all choices for a root
vertex r ∈ V . Introduce an indeterminate yu for each vertex u ∈ V and an indeterminate
zuv for each arc uv ∈ E. Introduce one further indeterminate t. Construct the symbolic
Laplacian L of G given by (3) and with the assignment xuv = (1+tyu )zuv to the indeterminate
xuv for each uv ∈ E. Puncture L at r to obtain Lr . Using, for example, Berkowitz’s
determinant circuit design [2] for an arbitrary commutative ring with unity, in time O∗ (1)
build an arithmetic circuit C of size O ∗ (1) for det Lr . Viewing det Lr as a multivariate
polynomial over the polynomial ring R[t, yu , zuv : u ∈ V, uv ∈ E] where R is an abstract ring
with unity, from Theorem 5 it follows that G has a spanning out-branching rooted at r with at
least k internal vertices if and only if the coeﬃcient of tk in det Lr (which is a polynomial that
is either identically zero or both (i) homogeneous of degree k in the indeterminates yu and (ii)
homogeneous of degree n − 1 in the indeterminates zuv ) has a monomial that is multilinear of
degree k in the indeterminates yu . Indeed, observe that the substitution xuv = (1 + tyu )zuv
tracks in the degree of the indeterminate yu whether u occurs as an internal vertex or not;
the indeterminates zuv make sure that distinct spanning out-branchings will not cancel each
other.
To detect a multilinear monomial in C restricted to the coeﬃcient of tk we can invoke [10,
Lemma 1] or [21, Lemma 2.8]. This results in a randomized algorithm that runs in time
O∗ (2k ) and has a negligible probability of reporting a false negative. This completes the
proof of Theorem 2.

4

Modular counting of Hamiltonian cycles

This section proves Theorem 3. Fix an arbitrary constant 0 < λ < 1. Let 0 < β < 1/2 be a
constant whose precise value is ﬁxed later. Let p be a prime and let G be an n-vertex directed
graph with vertex set V and arc set E given as input. Without loss of generality (by splitting
any vertex u into two vertices, s and t, with s receiving the out-arcs from u, and t receiving
the in-arcs to u) we may count the spanning paths starting from s and ending at t instead of
spanning cycles. Similarly, without loss of generality we may assume that 2 ≤ p < n. (Indeed,
for p ≥ n the counting outcome from Theorem 3 is trivial.)
Sieving for Hamiltonian paths among out-branchings. Let s, t ∈ V be distinct vertices. Let us write hp(G, s, t) for the set of spanning directed paths that start at s and end
at t in G. Recall that we write Vt = V \ {t} for the t-punctured version of the vertex set
V . Let us also write Vst = V \ {s, t}. For O ⊆ Vt , let LO
s be the matrix obtained from the
Laplacian (3) by ﬁrst puncturing at s and then substituting xuv = 0 for all arcs uv ∈ E with
u ∈ Vt \ O. Since a path P ∈ hp(G, s, t) is precisely a spanning out-branching rooted at s
such that every vertex u ∈ Vt has out-degree 1, we have, by Theorem 5 and the principle of

7

inclusion and exclusion,
X

Y

xuv =

X

(−1)|Vt \O| det LO
s .

(7)

O⊆Vt

P ∈hp(G,s,t) uv∈E(P )

In particular observe that (7) holds in any characteristic.
Cancellation modulo a power of p. With foresight, select k = ⌊(1−λ)(1/2−β)n/p⌋. Our
objective is next to show that by carefully injecting entropy into the underlying Laplacian we
can, in expectation and working modulo pk , cancel all but an exponentially negligible fraction
of the summands on the right-hand side of (7). Furthermore, we can algorithmically narrow
down to the nonzero terms, leading to an exponential improvement to 2n .
Let us assign xuv = 1 for all uv ∈ E with u 6= t. Since no spanning path that ends at t may
contain an arc tu ∈ E for any u ∈ Vt , we may without loss of generality assume that G contains
all such arcs, and assign, independently and uniformly at random xtu ∈ {0, 1, . . . , p−1}. Thus,
the summands det LO
s for O ⊆ Vt are now integer-valued random variables and (7) evaluates
to |hp(G, s, t)| with probability 1.

Let us next study a ﬁxed O ⊆ Vt . Let FO be the event that LO
s has no more than k rows
≡
6
0
(mod
pk ) implies FO . To bound
where each entry is divisible by p. In particular, det LO
s
the probability of FO from above, observe that LO
s is identically zero at each row u ∈ Vst \ O
except possibly at the diagonal entries. Furthermore, because of the random assignment to
the indeterminates xtu , each diagonal entry at these rows is divisible by p with probability
1/p. Let us take this intuition and turn it into a listing algorithm for (a superset of the) sets
O ⊆ Vt that satisfy FO .
Bipartitioning. For listing we will employ a meet-in-the-middle approach based on building
(2)
(1)
each set O ⊆ Vt from two parts using the following bipartitioning. Let Vt ∪ Vt = Vt be a
(1)
(2)
(1)
bipartition with |Vt | = ⌈n/3⌉ and |Vt | = n − 1 − ⌈n/3⌉. Associate with each O1 ⊆ Vt a
vector z O1 ∈ {0, 1, . . . , p − 1, ∞}Vst with the entry at u ∈ Vst deﬁned by
(
∞
if u ∈ O1 ;

(8)
zuO1 =
P
xtu + w∈O1 :wu∈E xwu mod p otherwise.
(1)

Similarly, associate with each O2 ⊆ Vt a vector z O2 ∈ {0, 1, . . . , p − 1, ∞}Vst with the entry
at u ∈ Vst deﬁned by
(
∞
if u ∈ O2 ;

zuO2 =
(9)
P
− w∈O2:wu∈E xwu mod p otherwise.
(2)

(1)

Suppose now that we have O1 ⊆ Vt and O2 ⊆ Vt with O = O1 ∪ O2 . We claim that
FO holds only if the vectors z O1 and z O2 agree in at most k entries. Indeed, observe that
zuO1 = zuO2 holds only if both u ∈ Vst \ O and the (u, u)-entry of LO
s is divisible by p. That
O
O
O
2
1
is, zu = zu implies the entire row u of Ls consists only of elements divisible by p. Thus it
suﬃces to list all pairs (O1 , O2 ) such that z O1 and z O2 have at most k agreements.

8

Balanced and unbalanced sets. To set up the listing procedure, let us now partition the
index domain Vst of our vectors into b = ⌊3 log 2 p⌋ pairwise disjoint sets S1 , S2 , . . . , Sb such
that we have ⌊(n − 2)/b⌋ ≤ |Si | ≤ ⌈(n − 2)/b⌉.

Let us split the sets O ⊆ Vt into two types. Let us say that O is balanced if (1/2 − β)n/b ≤
|(Vst \P
O) ∩ Si |≤ (1/2 + β)n/b holds for all i = 1, 2, . . . , b; otherwise O is unbalanced. Recalling
that ℓj=0 nj ≤ 2nH(ℓ/n) holds for all integers 1 ≤ ℓ ≤ n/2, where H(ρ) = −ρ log2 ρ − (1 −
ρ) log2 (1 − ρ) is the binary entropy function, observe that there are in total at most
⌈(1/2−β)n/b⌉
n+1−mini |Si |

2

b

X
j=0

⌊n/b+2⌋
j

≤ 2n−(n−2)/b+3 2(n/b+2)H(1/2−β) b

(10)

≤ 2n(1−(1−H(1/2−β))/b)+7 b

sets O that are unbalanced.
(1)

(1)

Precomputation and listing. Suppose that O1 ⊆ Vt and O2 ⊆ Vt are compatible in
the sense that z O1 and z O2 agree in at most k entries. For S ⊆ Vst and a vector z whose
entries are indexed by Vst , let us write zS for the restriction of z to S. If O1 and O2 are
compatible, then by an averaging argument there must exist an i = 1, 2, . . . , b such that zSOi1
and zSOi2 agree in at most k/b entries. In particular, this enables us to iterate over O2 and list
all compatible O1 by focusing only on each restriction to Si for i = 1, 2, . . . , b. Furthermore,
the search inside Si can be precomputed to look-up tables. Indeed, for each i = 1, 2, . . . , b
(1)
and each key g ∈ {0, 1, . . . , p − 1, ∞}Si , let us build a complete list of all subsets O1 ⊆ Vt
O1
such that zSi and g agree in at most k/b entries. These b look-up tables can be built by
processing in total at most
b
X
i=1

(1)

2Vt (p + 1)|Si | ≤ 2n/3+7 2(n/(⌊3 log2 p⌋)+2) log2 (p+1) log2 p = O(20.87n )

pairs (O1 , g). This takes time O ∗ (20.87n ) in total.
(2)

The main listing procedure now considers each O2 ⊆ Vt in turn, and for each i = 1, 2, . . . , b
consults the look-up table for direct access to all O1 such that zSOi1 and zSOi2 agree in at most k/b
entries. In particular this will list all compatible pairs (O1 , O2 ) and hence all sets O = O1 ∪O2
such that FO holds.
Expected running time. Let us now analyze the expected running time of the algorithm.
We start by deriving an upper bound for the expected number of pairs (O1 , O2 ) considered by
the main listing procedure. First, observe that the total number of pairs (O1 , O2 ) considered
by the procedure with O = O1 ∪ O2 unbalanced is bounded from above by our upper bound
(2)
(1)
(10) for the total number of unbalanced O. Indeed, O1 = O ∩ Vt and O2 = O ∩ Vt are
uniquely determined by O.
Next, for a pair (O1 , O2 ) with balanced O = O1 ∪ O2 and i = 1, 2, . . . , b, let GO1 ,O2 ,i be
the event that zSOi1 and zSOi2 agree in at most k/b entries. We seek an upper bound for the
probability of GO1 ,O2 ,i to obtain an upper bound for the expected number of pairs with
balanced O = O1 ∪ O2 considered by the main listing procedure. Let AO1 ,O2 ,i be the number
9

of entries in which zSOi1 and zSOi2 agree. We observe that AO1 ,O2 ,i is binomially distributed with
expectation |(Vt \ O) ∩ Si |/p. Since O is balanced, we have (1/2 − β)n/b ≤ |(Vt \ O) ∩ Si | ≤
(1/2 + β)n/b. We also recall that k = ⌊(1 − λ)(1/2 − β)n/p⌋. A standard Chernoﬀ bound now
gives

Pr(GO1 ,O2,i ) ≤ Pr AO1 ,O2 ,i ≤ k/b

≤ Pr AO1 ,O2 ,i ≤ (1 − λ)|(Vt \ O) ∩ Si |/p

≤ exp −λ2 |(Vt \ O) ∩ Si |/(2p)

≤ exp −λ2 (1/2 − β)n/(2pb) .

Recalling that b = ⌊3 log 2 p⌋, the main
 listing procedure thus considers in expectation at most
2n exp −λ2 (1/2 − β)n/(2p(3 log 2 p) pairs (O1 , O2 ) with O = O1 ∪ O2 balanced. Recalling our
upper bound for the total number of unbalanced sets (10), we thus have that the main list
ing procedure runs in O ∗ 2n exp −λ2 (1/2 − β)n/(2p(3 log 2 p)) + 2n(1−(1−H(1/2−β))/(3 log2 p))
expected time. Recalling that precomputation runs in O∗ (20.87n ) time, we thus have for
2
β = 1/6 that the entire algorithm runs in O∗ (2n(1−λ /(19p log2 p)) ) expected time and computes
|hp(G, s, t)| modulo p⌊(1−λ)n/(3p)⌋ . This completes the proof of Theorem 3.

5

Directed Hamiltonicity via quasi-Laplacian determinants

This section proves Theorem 4. Let G be a directed n-vertex graph given as input.
Finding a maximum independent set. Let B ∪ Y = V (G) be a partition of the vertex
set into two disjoint sets B (“blue”) and Y (“yellow”) such that no arc has both of its ends
in Y . That is, Y is an independent set.
We can ﬁnd an Y of the maximum possible size as follows. First, in time polynomial in n
compute the maximum-size matching in the undirected graph obtained from G by disregarding
the orientation of the arcs. This maximum-size matching must consist of at least ⌊n/2⌋ edges
or G does not admit a Hamiltonian cycle. (Indeed, from a Hamiltonian cycle we can obtain
a matching with ⌊n/2⌋ edges by taking every other arc in the cycle.) Since for each matching
edge it holds that both ends of the edge cannot be in an independent set, we can in time
O∗ (3n/2 ) ﬁnd a maximum-size independent set Y of G. Furthermore, α(G) = |Y | ≤ ⌊n/2⌋ + 1,
so we are within our budget of O∗ (3n(G)−α(G) ) in terms of running time. In fact, |Y | ≤ ⌊n/2⌋
or otherwise G trivially does not admit a Hamiltonian cycle.
The symbolic quasi-Laplacian. We will ﬁrst deﬁne the quasi-Laplacian and then give
intuition for its design. Let us work over a ﬁeld of characteristic 2. For each y ∈ Y introduce
a copy yin and let Yin be the set of all such copies. Similarly, for each y ∈ Y introduce a copy
yout and let Yout be the set of all such copies. We assume that Yin and Yout are disjoint. For
each j ∈ Yin ∪ Yout let us write j ∈ Y for the underlying element of Y of which j is a copy.
Let B∗ be a set of n − 2|Y | elements that is disjoint from both Yin and Yout . For each uv ∈ E
(j)
and each j ∈ B∗ ∪ Yin ∪ Yout , introduce an indeterminate xuv .

Select an arbitrary vertex s ∈ B for purposes of breaking symmetry and let I, O ⊆ B. The
quasi-Laplacian QI,O,s = QI,O,s(G) of G with skew at s be the n × n matrix whose rows are
10

indexed by u ∈ B ∪ Y and whose columns are indexed by j ∈ B∗ ∪ Yin ∪ Yout such that the
(u, j)-entry is deﬁned by
P
(j)


w∈O:wu∈E,u∈I xwu

P

(j)


 + w∈I:uw∈E,u∈O\{s} xuw (a) if u ∈ B and j ∈ B∗ ;


(j)


(b) if u ∈ O \ {s} and j ∈ Yin with uj ∈ E;

xuj
I,O,s
quj
=

(j)

xju


P

(j)


w∈O:wu∈E xwu


P

(j)


 w∈I:uw∈E xuw


0

(c) if u ∈ I and j ∈ Yout with ju ∈ E;

(11)

(d) if u ∈ Y and j ∈ Yin with u = j;

(e) if u ∈ Y and j ∈ Yout with u = j;
otherwise.

Let us next give some intuition for (11) before proceeding with the proof.
Analogously to the Laplacian (3), the quasi-Laplacian (11) has been designed so that the
monomials of each row u ∈ B ∪ Y of QI,O,s control the assignment of either an in-arc or an
out-arc to u in an incidence assignment, and the skew at s is used to break symmetry so that
s is always assigned an in-arc to s. In particular, without the skew at row s and with I = O,
each column of QI,O,s would sum to zero, in analogy with the (non-punctured) Laplacian.
Let us now give intuition for the columns j ∈ Yin and j ∈ Yout . First, observe by (b) and (d)
in (11) that selecting a monomial from column j ∈ Yin corresponds to making sure that the
in-degree of j is 1. Such a selection may be either a “quasi-diagonal” assignment of the in-arc
wj to u = j ∈ Y via (d) for some w ∈ B; or an “oﬀ-diagonal” assignment of the out-arc
uj to u ∈ B via (b). Second, observe by (c) and (e) in (11) that selecting a monomial from
column j ∈ Yout corresponds to making sure that the out-degree of j is 1. Thus, the columns
j ∈ Yin ∪ Yout enable us to make sure that an incidence assigment has both in-degree 1 and
out-degree 1 at each u ∈ Y without the use of sieving. This gives us the speed-up from O ∗ (3n )
to O∗ (3n−|Y | ) running time. Observe also that the structure for the quasi-Laplacian QI,O,s
is enabled precisely because Y is an independent set and thus no arc contributes to both
in-degree and out-degree in Y .
The quasi-Laplacian determinant sieve.
characteristic 2, let us study the sum
X X
X
det QI,O,s =
det QI,O,s =
I,O⊆B
I∪O=B
s∈I

I⊆B O⊆B

Recalling that we are working over a ﬁeld of
X

X X

Y

I,O,s
.
qu,σ(u)

(12)

σ:B∪Y →B∗ ∪Yin ∪Yout I⊆B O⊆B u∈B∪Y
σ bijective

Observe that the ﬁrst equality in (12) holds because QI,O,s has by (11) an identically zero
row unless I ∪ O = B and s ∈ I; the second equality holds by deﬁnition of the determinant
in characteristic 2 and changing the order of summation. From (11) and the right-hand side
of (12) it is immediate that (12) is either identically zero or a homogeneous polynomial of
(j)
degree n in the n|E| indeterminates xuv for j ∈ B∗ ∪ Yin ∪ Yout and uv ∈ E.4 We claim that
(12) is not identically zero if and only if G admits at least one spanning cycle. Furthermore,
each spanning cycle in G deﬁnes precisely |B∗ |! distinct monomials in (12).
4
Our algorithm for deciding Hamiltonicity will naturally not work with a symbolic representation of (12)
but rather in a homomorphic image under a random evaluation homomorphism.

11

To establish the claim, ﬁx a bijection σ : B ∪ Y → B∗ ∪ Yin ∪ Yout . Let us write M (σ) for the
set of all incidence assignments µ : B ∪ Y → E that are proper in the sense that all of the
following six requirements hold (cf. (11)):
• (s): µ(s) is an in-arc to s;
• (a): for all u ∈ B with σ(u) ∈ B∗ it holds that µ(u) has both of its vertices in B;
• (b): for all u ∈ B with σ(u) ∈ Yin it holds that µ(u) is an in-arc to σ(u);
• (c): for all u ∈ B with σ(u) ∈ Yout it holds that µ(u) is an out-arc from σ(u);
• (d): for all u ∈ Y with σ(u) ∈ Yin it holds that µ(u) is an in-arc to u and u = σ(u); and
• (e): for all u ∈ Y with σ(u) ∈ Yout it holds that µ(u) is an out-arc from u and u = σ(u).
Observe that each µ ∈ M (σ) deﬁnes a collection of n arcs µ(B ∪ Y ) = {µ(u) : u ∈ B ∪ Y }. Let
µ
µ
(respectively, Zout
) for the set of vertices in B ∪Y with zero in-degree (out-degree)
us write Zin
with respect to the arcs in µ(B ∪ Y ). Since σ is a bijection and thus has a preimage for each
µ
µ
j ∈ Yin ∪ Yout , from (b,c,d,e) above it follows that Zin
⊆ B and Zout
⊆ B. Furthermore, from
(a,b,c,d,e) it follows that for the arcs in µ(B ∪ Y ) the sum of the in-degrees (and the sum of
µ
µ
and Zout
the out-degrees) of the vertices in B is |B| = |B∗ | + |Y |. Thus, we have that Zin
are both empty if and only if for the arcs µ(B ∪ Y ) both the in-degree and the out-degree of
every vertex u ∈ B ∪ Y is 1. (Note that the claim is immediate for u ∈ Y by (b,c,d,e) and
bijectivity of σ.)
Let us now study the right-hand side of (12) for a ﬁxed σ. Using (a,b,c,d,e) and (11) to
rearrange in terms of incidence assignments, we have
X
Y (σ(u)) X X
X X Y I,O,s
1.
(13)
xµ(u)
qu,σ(u) =
I⊆V O⊆V u∈B∪Y

µ∈M (σ) u∈B∪Y

µ
µ
O⊆Zout
I⊆Zin

Since we are working in characteristic 2, all other µ ∈ M (σ) except those for which µ(B ∪ Y )
is a cycle cover will cancel in the right-hand side of (13).
Take the sum of (13) over all bijections σ. Consider an arbitrary cycle cover of B ∪ Y . Let
C be a cycle in this cycle cover. Assuming that C does not contain s, we can realize C in an
incidence assignment µ : B ∪ Y → E either using (1) or (2). If C contains s and µ is proper,
only the realization (1) is possible by (s). To see that realization with a proper µ ∈ M (σ)
for some σ is possible, consider an arbitrary u ∈ B ∪ Y and observe that each image µ(u)
by (b,c,d,e) uniquely determines the image σ(u) ∈ Yin ∪ Yout when µ(u) has one vertex in Y ;
when µ(u) has both vertices in B, an unused σ(u) ∈ B∗ may be chosen arbitrarily so that
µ ∈ M (σ). It follows that any cycle cover with c cycles is realized as exacly |B∗ |! distinct
Q
(σ(u))
monomials u∈B∪Y xµ(u) in (12), each with coeﬃcient 2c−1 . This coeﬃcient is nonzero if
and only if c = 1.
Completing the algorithm. To detect whether the given n-vertex directed graph G admits a Hamiltonian cycle, ﬁrst decompose the vertex set into disjoint V = B ∪ Y with Y an
independent set of size |Y | = α(G) using the algorithm described earlier. Next, in time O∗ (1)
construct an irreducible polynomial of degree 2⌈log2 n⌉ over F2 (see e.g. von zur Gathen and
12

Gerhard [24, §14.9]) to enable arithmetic in the ﬁnite ﬁeld of order q = 22⌈log2 n⌉ ≥ n2 in time
O∗ (1) for each arithmetic operation. Next, assign an independent uniform random value from
(j)
Fq to each indeterminate xuv with j ∈ B∗ ∪ Yin ∪ Yout and uv ∈ E. Finally, using the assigned
values for the indeterminates, compute the left-hand side of (12) using, for example, Gaussian
elimination to compute each determinant det QI,O,s in O∗ (1) operations in Fq . Let us write
r ∈ Fq for the result of this computation. In particular, we can compute r from a given G in
total O ∗ (3|B| ) = O∗ (3n(G)−α(G) ) operations in Fq , and consequently in total O ∗ (3n(G)−α(G) )
time. If (12) is identically zero, then clearly r = 0 with probability 1. If (12) is not identically
zero (and hence a homogeneous polynomial of degree d = n in the indeterminates) then by
the DeMillo–Lipton–Schwartz–Zippel lemma [14, 22, 26] we have r 6= 0 with probability at
least 1 − d/q ≥ 1 − n/n2 ≥ 1 − 1/n = 1 − o(1). Thus we can decide whether G is Hamiltonian
based on whether r 6= 0. In particular this gives probability o(1) of reporting a false negative.
This completes the proof of Theorem 4.
Acknowledgements. The research leading to these results has received funding from the
Swedish Research Council grants VR 2012-4730 “Exact Exponential-Time Algorithms” and
VR 2016-03855 “Algebraic Graph Algorithms” (A.B.), the European Research Council under
the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement 338077 “Theory and Practice of Advanced Search and Enumeration” (P.K.), and grant
NSF CAREER CCF-1149048 (I.K.). Work done in part while the authors were at Dagstuhl
Seminar 17041 in January 2017 and at the Simons Institute for the Theory of Computing in
December 2015.

13

APPENDIX
A

Detecting a k-Leaf Out-Branching

The k-Leaf Out-Branching problems asks, given an n-vertex directed graph G and an integer
k as input, whether G has a spanning out-branching with at least k leaves. Equivalently, we
are asked to detect a spanning out-branching with at most n − k internal vertices.

Let us algebraize the k-Leaf problem by pursuing an analogy with the approach in Sect. 3.
Without loss of generality we may assume that 1 ≤ k ≤ n and n ≥ 2. Iterate over all
choices for a root vertex r ∈ V . Since n ≥ 2 we have that r must be an internal vertex
in any out-branching rooted at r. Introduce an indeterminate yu for each vertex u ∈ V .
Construct the symbolic Laplacian L of G given by (3) and with the assignment xuv = yu to
the indeterminate xuv for each uv ∈ E. Puncture L at r to obtain Lr . Viewing yr det Lr
as a multivariate polynomial over the indeterminates yu , from Theorem 5 it follows that G
has a spanning out-branching rooted at r with at most n − k internal vertices if and only if
yr det Lr (which is a polynomial that is either identically zero or homogeneous of degree n in
the indeterminates yu ) has a monomial with at most n − k of the n indeterminates yu .
This motivates the following parameterized monomial detection problem. Namely, the (n−k)DV problem asks, given as input a polynomial P ∈ Z[y1 , y2 , . . . , yn ] that is homogeneous of
degree n and with nonnegative integer coeﬃcients, whether P has a monomial with at most
n − k distinct indeterminates.

The k-DV problem was discussed in [15] and it was shown that it is W[2]-hard via a reduction
from the parameterized hitting set problem. However, the (n − k)-DV problem is ﬁxedparameter tractable with respect to k. We prove the following:
Theorem 6 (Detecting a monomial with few indeterminates). There is a randomized algorithm that decides the (n − k)-DV problem using O∗ (2k+s ) evaluations of P and with negligible
probability for a false negative, where s ≤ k is the minimum number of indeterminates with
degree greater than 1 taken over all monomials of P with at most n−k distinct indeterminates.
Proof. We introduce a set of extra indeterminates W = w1 , w2 , . . . , wn , and two special
indeterminates a, b. We will substitute these two indeterminates into X and Y and compute
a homogeneous polynomial in {a, b}. The computation can be done either symbolically or
with a suﬃcient number of numerical evaluations and interpolation.
The algorithm iterates the following two steps O ∗ (2k+s ) times:
a. For each i = 1, 2, . . . , n independently, substitute:
either (yi ← a, wi ← b) or (yi ← b, wi ← a), each with probability 1/2.
b. Perform the random substitution on the polynomial P (y1 , y2 , . . . , yn )w1 w2 · · · wn to obtain a homogeneous polynomial of degree 2n in a and b. If the result is not divisible by
(ab)n−k+1 then halt with output YES.
If none of the iterations halts, then halt with output NO.
14

Let us now analyze the algorithm. First, consider the eﬀect of the substitution to a monomial
with at least n − k + 1 of the indeterminates y1 , y2 , . . . , yn .Since the monomial gets multiplied
by w1 w2 · · · wn , the substitution yields a monomial in a, b that is a multiple of (ab)n−k+1 .
Thus, if all monomials of P have at least n − k + 1 indeterminates then by linearity the result
of substitution to P (y1 , y2 , . . . , yn )w1 w2 · · · wn is a multiple of (ab)n−k+1 . Thus, the algorithm
halts with output NO.
Next, consider a monomial with exactly n − k′ indeterminates, among which exactly s have
degree at least 2. Because the monomial has degree n, we have s ≤ k′ . The monomial is thus
of the form
yid11 yid22 · · · yidss yis+1 · · · yin−k′
with d1 , d2 , . . . , ds ≥ 2. Multiplying with w1 w2 · · · wn we thus have
!
!
′
n
n−k


Y
Y
(yit wit )
yid11 −1 · · · yidss −1
wit .
t=1

t=n−k ′ +1

′

Under the random substitution the ﬁrst product evaluates to (ab)n−k . Now note that each of
the remaining indeterminates in the product has randomly and independently been assigned
to a or b, with probability 1/2. There are s + k′ such indeterminates. It follows that with
′
′
′
′
probability at least 2−(k +s) the monomial becomes (ab)n−k ak or (ab)n−k bk . Thus, when
k′ ≥ k the resulting monomial is not divisible by (ab)n−k+1 with probability at least 2−(k+s) .
Furthermore, by linearity the result of the substitution to P (y1 , y2 , . . . , yn )w1 w2 · · · wn is not
divisible either since P has nonnegative coeﬃcients and thus cancellations are not possible.
Repeating O ∗ (2k+s ) times renders negligible the probability of a false negative.
We thus have the following:
Theorem 7 (Detecting a k-leaf out-branching). The k-Leaf Out-Branching problem can be
decided with a randomized algorithm in O∗ (2k+s ) time, where s is the minimum number of
internal vertices with out-degree greater than 1 taken over all out-branchings with at least k
leaves. The algorithm has a negligible probability of reporting a false negative.
Proof. Consider each root vertex r ∈ V in turn and let P be the polynomial yr det Lr introduced in the beginning of this section. For any ﬁxed out-branching, the internal vertices with
out-degree greater than 1 correspond to variables with degree greater than 1 in the associated
monomial. The theorem follows by a direct application of Theorem 6.
Note. As observed by M. Koivisto, the algorithm can be somewhat improved, by skewing
the probabilities in the substitution (yi ← a, wi ← b) or (yi ← b, wi ← a) to p and 1 − p
respectively, where p = k/(k + s). Using a very similar argument one can show that the
problem can be decided with O∗ (ck+s ) evaluations of P , where c−1 = pp (1 − p)1−p . For
example, when s = k/2 the running time becomes O ∗ (1.89s+k ), and when s is some ﬁxed
constant (that is, when a tree has a small number of internal branching vertices) then the
algorithm runs in polynomial time. The worst-case running time of the algorithm is O∗ (2n )
when k = s = n/2, but it gets smaller when k > n/2, nearly matching exhaustive search at
the W[2]-hard side of the range, that is, when n − k is constant.
15

The best known algorithm for the directed k-leaf problem is based on a branch-and-bound
approach and runs in O ∗ (3.72k ) time [13]. Our algorithm runs in O∗ (4k ) time in the worst
case, but it can adapt to properties of the input and actually be faster for instances containing
a k-leaf tree with at most 10k/11 internal vertices of out-degree greater than 1.

B

Corollaries and variants of Theorem 3

This appendix proves corollaries and variants of Theorem 3 to demonstrate the versatility of
the approach.
Boosting the modulus for counting by Chinese remaindering. From number theory
we know (Merten’s First Theorem, cf. Tenenbaum [23, Theorem 7]) that if we take the sum
over the primes p at most q > 2, we have
X ln p
p≤q

p

≥ ln q − 2 .

Thus, using Theorem 3 for all primes p at most q, from the Chinese Remainder Theorem
we obtain that there exists a constant c > 0 such for all large enough integers q we can
in expected time O ∗ (2n(1−cn/(q log q)) ) compute the number of Hamiltonian cycles in a given
n-vertex directed graph modulo an integer M that satisﬁes
 X

Y
1
ln p
⌊n/(3p)⌋
M≥
p
≥ exp n
≥ (e−2 q)n/4 .
4
p
p≤q

p≤q

Counting Hamiltonian cycles when there are few.
diate corollary of modulus-boosting:

The following result is an imme-

Theorem 8 (Counting Hamiltonian cycles when there are few). There is a randomized algorithm and a constant c > 0 such that for all constants d > 1 the following holds: when given
an n-vertex directed graph G with at most dn Hamiltonian cycles as input, the algorithm
5
computes the exact number of Hamiltonian cycles in G in O ∗ (2n(1−c/d ) ) expected time.
Proof. Boost the modulus with q = e2 d4 to observe that M > dn for all large enough n.
Theorem 9 (Counting Hamiltonian cycles with bounded average out-degree). There is a randomized algorithm and a constant c > 0 such that for all constants d > 1 the following holds:
when given an n-vertex directed graph G with average out-degree at most d, the algorithm
5
computes the exact number of Hamiltonian cycles in G in O ∗ (2n(1−c/d ) ) expected time.
Proof. For each vertex u ∈ V (G), let du be the out-degree of u. We have that G hasPat most
Q
1
u∈V du .
u∈V (G) du Hamiltonian cycles. On the other hand, the average degree of G is n
From the inequality between arithmetic and geometric means it follows that there are at most
dn Hamiltonian cycles in G, and Theorem 8 applies.

16

References
[1] Richard Bellman. Dynamic programming treatment of the travelling salesman problem.
J. ACM, 9(1):61–63, January 1962.
[2] Stuart J. Berkowitz. On computing the determinant in small parallel time using a small
number of processors. Information Processing Letters, 18:147–150, 1984.
[3] Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM Journal on
Computing, 43(1):280–299, 2014.
[4] Andreas Björklund. Below All Subsets for Some Permutational Counting Problems .
In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm
Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics
(LIPIcs), pages 17:1–17:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik.
[5] Andreas Björklund, Holger Dell, and Thore Husfeldt. The parity of set systems under
random restrictions with applications to exponential time problems. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan,
July 6-10, 2015, Proceedings, Part I, pages 231–242, Berlin, Heidelberg, 2015. Springer
Berlin Heidelberg.
[6] Andreas Björklund and Thore Husfeldt. The parity of directed hamiltonian cycles. In
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 724–735,
Oct 2013.
[7] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling
salesman problem in bounded degree graphs. ACM Trans. Algorithms, 8(2):18:1–18:13,
April 2012.
[8] Andreas Björklund, Thore Husfeldt, and Isak Lyckberg. Computing the permanent
modulo a prime power. Unpublished manuscript, 2015.
[9] Andreas Björklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting trees
with few leaves. SIAM Journal on Discrete Mathematics, 31(2): 687–713, 2017. Preliminary version in Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina
Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134
of Lecture Notes in Computer Science, pages 243–255. Springer, 2015.
[10] Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Constrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947–967, 2016.
[11] Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via
bases of perfect matchings. In Proceedings of the Forty-fifth Annual ACM Symposium
on Theory of Computing, STOC ’13, pages 301–310, New York, NY, USA, 2013. ACM.
[12] Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of
bounded average degree. Information and Computation, 243:75 – 85, 2015. 40th International Colloquium on Automata, Languages and Programming (ICALP 2013).
17

[13] Jean Daligault, Gregory Gutin, Eun Jung Kim, and Anders Yeo. FPT algorithms and kernels for the directed k-leaf problem. Journal of Computer and System Sciences, 76(2):144
– 152, 2010.
[14] R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing.
Information Processing Letters, 7:193–195, 1978.
[15] Peter Floderus, Andrzej Lingas, Mia Persson, and Dzmitry Sledneu. Detecting monomials with k distinct variables. Information Processing Letters, 115(2):82–86, 2015.
[16] Ariel Gabizon, Daniel Lokshtanov, and Michal Pilipczuk. Fast algorithms for parameterized problems with relaxed disjointness constraints. In Algorithms - ESA 2015: 23rd
Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages
545–556, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
[17] Ira M. Gessel and Richard P. Stanley. Algebraic enumeration. In R. L. Graham,
M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume II, pages
1021–1061. North-Holland, Amsterdam, 1995.
[18] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of
Computer and System Sciences, 62(2):367 – 375, 2001.
[19] Richard M. Karp. Dynamic programming meets the principle of inclusion and exclusion.
Operations Research Letters, 1(2):49 – 51, 1982.
[20] Samuel Kohn, Allan Gottlieb, and Meryle Kohn. A generating function approach to
the traveling salesman problem. In Proceedings of the Annual Conference (ACM’77),
Association for Computing Machinery, pages 294–300, 1977.
[21] Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. ACM Transactions on Algorithms, 12:Art. 31, 18, 2016.
[22] Jacob T. Schwartz. Fast probabilistic algorithms for veriﬁcation of polynomial identities.
Journal of the ACM, 27:701–717, 1980.
[23] Gerald Tenenbaum. Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, Cambridge, 1995.
[24] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge
University Press, Cambridge, 3rd edition, 2013.
[25] Meirav Zehavi. Mixing color coding-related techniques. In Algorithms ESA 2015: 23rd
Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages
1037–1049. Springer Berlin Heidelberg, 2015.
[26] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proc. International
Symposium on Symbolic and Algebraic Computati on, volume 72 of Lecture Notes in
Computer Science, pages 216–226, Berlin, 1979. Springer.

18

