
It was shown by Grohe et al. that nowhere dense classes of graphs admit
sparse neighbourhood covers of small degree. We show that a monotone graph
class admits sparse neighbourhood covers if and only if it is nowhere dense.
The existence of such covers for nowhere dense classes is established through
bounds on socalled weak colouring numbers.
The core results of this paper are various lower and upper bounds on the weak
colouring numbers and other, closely related generalised colouring numbers. We
prove tight bounds for these numbers on graphs of bounded tree width. We
clarify and tighten the relation between the expansion (in the sense of
"bounded expansion" as defined by Nesetril and Ossona de Mendez) and the
various generalised colouring numbers. These upper bounds are complemented by
new, stronger exponential lower bounds on the generalised colouring numbers.
Finally, we show that computing weak rcolouring numbers is NPcomplete for all
r>2.

Luks's algorithm (JCSS 1982) to test isomorphism of bounded degree graphs in
polynomial time is one of the most important results in the context of the
Graph Isomorphism Problem and has been repeatedly used as a basic building
block for many other algorithms. In particular, for graphs of logarithmic
degree, Babai's quasipolynomial isomorphism test (STOC 2016) essentially boils
down to Luks's algorithm, and any improvement of Babai's algorithm requires an
improved isomorphism test for graphs of (poly)logarithmic degree.
In this work, we obtain such an improvement: we give an algorithm that solves
the Graph Isomorphism Problem in time $n^{\mathcal{O}((\log d)^{c})}$, where
$n$ is the number of vertices of the input graphs, $d$ is the maximum degree of
the input graphs, and $c$ is an absolute constant. The best previous
isomorphism test for graphs of maximum degree $d$ due to Babai, Kantor and Luks
(FOCS 1983) runs in time $n^{\mathcal{O}(d/ \log d)}$. Our result generalizes
the quasipolynomialtime algorithm for the general isomorphism problem due to
Babai.

We give a new fpt algorithm testing isomorphism of $n$vertex graphs of tree
width $k$ in time $2^{k\operatorname{polylog} (k)}\operatorname{poly} (n)$,
improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and
Saurabh (FOCS 2014), which runs in time $2^{\mathcal{O}(k^5\log
k)}\operatorname{poly} (n)$. Based on an improved version of the
isomorphisminvariant graph decomposition technique introduced by Lokshtanov et
al., we prove restrictions on the structure of the automorphism groups of
graphs of tree width $k$. Our algorithm then makes heavy use of the group
theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for
bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism
test. In fact, we even use Babai's algorithm as a black box in one place.
We also give a second algorithm which, at the price of a slightly worse
running time $2^{\mathcal{O}(k^2 \log k)}\operatorname{poly} (n)$, avoids the
use of Babai's algorithm and, more importantly, has the additional benefit that
it can also used as a canonization algorithm.

We prove that for every positive integer $k$, there exists an
$\text{MSO}_1$transduction that given a graph of linear cliquewidth at most
$k$ outputs, nondeterministically, some clique decomposition of the graph of
width bounded by a function of $k$. A direct corollary of this result is the
equivalence of the notions of $\text{CMSO}_1$definability and recognizability
on graphs of bounded linear cliquewidth.

We establish new, and surprisingly tight, connections between propositional
proof complexity and finite model theory. Specifically, we show that the power
of several propositional proof systems, such as Horn resolution, boundedwidth
resolution, and the polynomial calculus of bounded degree, can be characterised
in a precise sense by variants of fixedpoint logics that are of fundamental
importance in descriptive complexity theory. Our main results are that Horn
resolution has the same expressive power as least fixedpoint logic, that
boundedwidth resolution captures existential least fixedpoint logic, and that
the polynomial calculus with bounded degree over the rationals solves precisely
the problems definable in fixedpoint logic with counting. By exploring these
connections further, we establish finitemodeltheoretic tools for proving
lower bounds for the polynomial calculus over the rationals and over finite
fields.

In this paper, we relate a beautiful theory by Lov\'asz with a popular
heuristic algorithm for the graph isomorphism problem, namely the color
refinement algorithm and its $k$dimensional generalization known as the
WeisfeilerLeman algorithm. We prove that two graphs $G$ and $H$ are
indistinguishable by the color refinement algorithm if and only if, for all
trees $T$, the number $\mathsf{hom}(T,G)$ of homomorphisms from $T$ to $G$
equals the corresponding number $\mathsf{hom}(T,H)$ for $H$.
There is a natural system of linear equations whose nonnegative integer
solutions correspond to the isomorphisms between two graphs. The nonnegative
real solutions to this system are called fractional isomorphisms, and two
graphs are fractionally isomorphic if and only if the color refinement
algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we
drop the nonnegativity constraints, that is, if we look for arbitrary real
solutions, then a solution to the linear system exists if and only if, for all
$t$, the two graphs have the same number of length$t$ walks.
We lift the results for trees to an equivalence between numbers of
homomorphisms from graphs of tree width $k$, the $k$dimensional
WeisfeilerLeman algorithm, and the level$k$ SheraliAdams relaxation of our
linear program. We also obtain a partial result for graphs of path width $k$
and solutions to our system where we drop the nonnegativity constraints.
A consequence of our results is a quasilinear time algorithm to decide
whether, for two given graphs $G$ and $H$, there is a tree $T$ with
$\mathsf{hom}(T,G)\neq\mathsf{hom}(T,H)$.

The graph similarity problem, also known as approximate graph isomorphism or
graph matching problem, has been extensively studied in the machine learning
community, but has not received much attention in the algorithms community:
Given two graphs $G,H$ of the same order $n$ with adjacency matrices $A_G,A_H$,
a wellstudied measure of similarity is the Frobenius distance \[
\mathrm{dist}(G,H):=\min_{\pi}\A_G^\piA_H\_F, \] where $\pi$ ranges over all
permutations of the vertex set of $G$, where $A_G^\pi$ denotes the matrix
obtained from $A_G$ by permuting rows and columns according to $\pi$, and where
$\M\_F$ is the Frobenius norm of a matrix $M$. The (weighted) graph
similarity problem, denoted by SIM (WSIM), is the problem of computing this
distance for two graphs of same order. This problem is closely related to the
notoriously hard quadratic assignment problem (QAP), which is known to be
NPhard even for severely restricted cases.
It is known that SIM (WSIM) is NPhard; we strengthen this hardness result by
showing that the problem remains NPhard even for the class of trees.
Identifying the boundary of tractability for WSIM is best done in the framework
of linear algebra. We show that WSIM is NPhard as long as one of the matrices
has unbounded rank or negative eigenvalues: hence, the realm of tractability is
restricted to positive semidefinite matrices of bounded rank. Our main result
is a polynomial time algorithm for the special case where one of the matrices
has a bounded clustering number, a parameter arising from spectral graph
drawing techniques.

We study the classification problems over string data for hypotheses
specified by formulas of monadic secondorder logic MSO. The goal is to design
learning algorithms that run in time polynomial in the size of the training
set, independently of or at least sublinear in the size of the whole data set.
We prove negative as well as positive results. If the data set is an
unprocessed string to which our algorithms have local access, then learning in
sublinear time is impossible even for hypotheses definable in a small fragment
of firstorder logic. If we allow for a linear time preprocessing of the
string data to build an index data structure, then learning of MSOdefinable
hypotheses is possible in time polynomial in the size of the training set,
independently of the size of the whole data set.

We study an extension of firstorder logic that allows to express cardinality
conditions in a similar way as SQL's COUNT operator. The corresponding logic
FOC(P) was introduced by Kuske and Schweikardt (LICS'17), who showed that query
evaluation for this logic is fixedparameter tractable on classes of structures
(or databases) of bounded degree. In the present paper, we first show that the
fixedparameter tractability of FOC(P) cannot even be generalised to very
simple classes of structures of unbounded degree such as unranked trees or
strings with a linear order relation.
Then we identify a fragment FOC1(P) of FOC(P) which is still sufficiently
strong to express standard applications of SQL's COUNT operator. Our main
result shows that query evaluation for FOC1(P) is fixedparameter tractable
with almost linear running time on nowhere dense classes of structures. As a
corollary, we also obtain a fixedparameter tractable algorithm for counting
the number of tuples satisfying a query over nowhere dense classes of
structures.

The dichotomy conjecture for the parameterized embedding problem states that
the problem of deciding whether a given graph $G$ from some class $K$ of
"pattern graphs" can be embedded into a given graph $H$ (that is, is isomorphic
to a subgraph of $H$) is fixedparameter tractable if $K$ is a class of graphs
of bounded tree width and $W[1]$complete otherwise.
Towards this conjecture, we prove that the embedding problem is
$W[1]$complete if $K$ is the class of all grids or the class of all walls.

We consider a declarative framework for machine learning where concepts and
hypotheses are defined by formulas of a logic over some background structure.
We show that within this framework, concepts defined by firstorder formulas
over a background structure of at most polylogarithmic degree can be learned in
polylogarithmic time in the "probably approximately correct" learning sense.

In recent years, we have seen several approaches to the graph isomorphism
problem based on "generic" mathematical programming or algebraic (Gr\"obner
basis) techniques. For most of these, lower bounds have been established. In
fact, it has been shown that the pairs of nonisomorphic CFIgraphs (introduced
by Cai, F\"urer, and Immerman in 1992 as hard examples for the combinatorial
WeisfeilerLeman algorithm) cannot be distinguished by these mathematical
algorithms. A notable exception were the algebraic algorithms over the field
GF(2), for which no lower bound was known. Another, in some way even stronger,
approach to graph isomorphism testing is based on solving systems of linear
Diophantine equations (that is, linear equations over the integers), which is
known to be possible in polynomial time. So far, no lower bounds for this
approach were known.
Lower bounds for the algebraic algorithms can best be proved in the framework
of proof complexity, where they can be phrased as lower bounds for algebraic
proof systems such as Nullstellensatz or the (more powerful) polynomial
calculus. We give new hard examples for these systems: families of pairs of
nonisomorphic graphs that are hard to distinguish by polynomial calculus
proofs simultaneously over all prime fields, including GF(2), as well as
examples that are hard to distinguish by the
systemsoflinearDiophantineequations approach.
In a previous paper, we observed that the CFIgraphs are closely related to
what we call "group CSPs": constraint satisfaction problems where the
constraints are membership tests in some coset of a subgroup of a cartesian
power of a base group (Z_2 in the case of the classical CFIgraphs). Our new
examples are also based on group CSPs (for Abelian groups), but here we extend
the CSPs by a few nongroup constraints to obtain even harder instances for
graph isomorphism.

Orderinvariant formulas access an ordering on a structure's universe, but
the model relation is independent of the used ordering. Order invariance is
frequently used for logicbased approaches in computer science. Orderinvariant
formulas capture unordered problems of complexity classes and they model the
independence of the answer to a database query from lowlevel aspects of
databases. We study the expressive power of orderinvariant monadic
secondorder (MSO) and firstorder (FO) logic on restricted classes of
structures that admit certain forms of tree decompositions (not necessarily of
bounded width).
While orderinvariant MSO is more expressive than MSO and, even, CMSO (MSO
with modulocounting predicates), we show that orderinvariant MSO and CMSO are
equally expressive on graphs of bounded tree width and on planar graphs. This
extends an earlier result for trees due to Courcelle. Moreover, we show that
all properties definable in orderinvariant FO are also definable in MSO on
these classes. These results are applications of a theorem that shows how to
lift up definability results for orderinvariant logics from the bags of a
graph's tree decomposition to the graph itself.

We survey an abstract theory of connectivity, based on symmetric submodular
set functions. We start by developing Robertson and Seymour's fundamental
duality between branch decompositions (related to the betterknown tree
decompositions) and socalled tangles, which may be viewed as highly connected
regions in a connectivity system. We move on to studying canonical
decompositions of connectivity systems into their maximal tangles. Last, but
not least, we will discuss algorithmic aspect of the theory.

Tangles of graphs have been introduced by Robertson and Seymour in the
context of their graph minor theory. Tangles may be viewed as describing
"kconnected components" of a graph (though in a twisted way). They play an
important role in graph minor theory. An interesting aspect of tangles is that
they cannot only be defined for graphs, but more generally for arbitrary
connectivity functions (that is, integervalued submodular and symmetric set
functions).
However, tangles are difficult to deal with algorithmically. To start with,
it is unclear how to represent them, because they are families of separations
and as such may be exponentially large. Our first contribution is a data
structure for representing and accessing all tangles of a graph up to some
fixed order.
Using this data structure, we can prove an algorithmic version of a very
general structure theorem due to Carmesin, Diestel, Harman and Hundertmark (for
graphs) and Hundertmark (for arbitrary connectivity functions) that yields a
canonical tree decomposition whose parts correspond to the maximal tangles.
(This may be viewed as a generalisation of the decomposition of a graph into
its 3connected components.)

This paper is a short introduction to the theory of tangles, both in graphs
and general connectivity systems. An emphasis is put on the correspondence
between tangles of order k and kconnected components. In particular, we prove
that there is a onetoone correspondence between the triconnected components
of a graph and its tangles of order 3.

We introduce a new decomposition of a graphs into quasi4connected
components, where we call a graph quasi4connected if it is 3connected and it
only has separations of order 3 that remove a single vertex. Moreover, we give
a cubic time algorithm computing the decomposition of a given graph.
Our decomposition into quasi4connected components refines the wellknown
decompositions of graphs into biconnected and triconnected components. We
relate our decomposition to Robertson and Seymour's theory of tangles by
establishing a correspondence between the quasi4connected components of a
graph and its tangles of order 4.

An assignment of colours to the vertices of a graph is stable if any two
vertices of the same colour have identically coloured neighbourhoods. The goal
of colour refinement is to find a stable colouring that uses a minimum number
of colours. This is a widely used subroutine for graph isomorphism testing
algorithms, since any automorphism needs to be colour preserving. We give an
$O((m+n)\log n)$ algorithm for finding a canonical version of such a stable
colouring, on graphs with $n$ vertices and $m$ edges. We show that no faster
algorithm is possible, under some modest assumptions about the type of
algorithm, which captures all known colour refinement algorithms.

We give an algorithm that, for every fixed k, decides isomorphism of graphs
of rank width at most k in polynomial time. As the clique width of a graph is
bounded in terms of its rank width, we also obtain a polynomial time
isomorphism test for graph classes of bounded clique width.

We give a new, simplified and detailed account of the correspondence between
levels of the SheraliAdams relaxation of graph isomorphism and levels of
pebblegame equivalence with counting (higherdimensional WeisfeilerLehman
colour refinement). The correspondence between basic colour refinement and
fractional isomorphism, due to Tinhofer (1986, 1991) and Ramana, Scheinerman
and Ullman (1994), is reinterpreted as the base level of SheraliAdams and
generalised to higher levels in this sense by Atserias and Maneva (2012) and
Malkin (2014), who prove that the two resulting hierarchies interleave.
In carrying this analysis further, we here give
(a) a precise characterisation of the levelk SheraliAdams relaxation in
terms of a modified counting pebble game;
(b) a variant of the SheraliAdams levels that precisely match the kpebble
counting game;
(c) a proof that the interleaving between these two hierarchies is strict.
We also investigate the variation based on boolean arithmetic instead of
real/rational arithmetic and obtain analogous correspondences and separations
for plain kpebble equivalence (without counting). Our results are driven by
considerably simplified accounts of the underlying combinatorics and linear
algebra.

We investigate the power of graph isomorphism algorithms based on algebraic
reasoning techniques like Gr\"obner basis computation. The idea of these
algorithms is to encode two graphs into a system of equations that are
satisfiable if and only if if the graphs are isomorphic, and then to (try to)
decide satisfiability of the system using, for example, the Gr\"obner basis
algorithm. In some cases this can be done in polynomial time, in particular, if
the equations admit a bounded degree refutation in an algebraic proof systems
such as Nullstellensatz or polynomial calculus. We prove linear lower bounds on
the polynomial calculus degree over all fields of characteristic different from
2 and also linear lower bounds for the degree of Positivstellensatz calculus
derivations.
We compare this approach to recently studied linear and semidefinite
programming approaches to isomorphism testing, which are known to be related to
the combinatorial WeisfeilerLehman algorithm. We exactly characterise the
power of the WeisfeilerLehman algorithm in terms of an algebraic proof system
that lies between degreek Nullstellensatz and degreek polynomial calculus.

We generalize the structure theorem of Robertson and Seymour for graphs
excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological
subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a
topological subgraph has a tree decomposition where each part is either "almost
embeddable" to a fixed surface or has bounded degree with the exception of a
bounded number of vertices. Furthermore, we prove that such a decomposition is
computable by an algorithm that is fixedparameter tractable with parameter
$H$.
We present two algorithmic applications of our structure theorem. To
illustrate the mechanics of a "typical" application of the structure theorem,
we show that on graphs excluding $H$ as a topological subgraph, Partial
Dominating Set (find $k$ vertices whose closed neighborhood has maximum size)
can be solved in time $f(H,k)\cdot n^{O(1)}$ time. More significantly, we show
that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can
be solved in time $n^{f(H)}$. This result unifies and generalizes two
previously known important polynomialtime solvable cases of Graph Isomorphism:
boundeddegree graphs and $H$minor free graphs. The proof of this result needs
a generalization of our structure theorem to the context of invariant treelike
decomposition.

Colour refinement is a basic algorithmic routine for graph isomorphism
testing, appearing as a subroutine in almost all practical isomorphism solvers.
It partitions the vertices of a graph into "colour classes" in such a way that
all vertices in the same colour class have the same number of neighbours in
every colour class. Tinhofer (Disc. App. Math., 1991), Ramana, Scheinerman, and
Ullman (Disc. Math., 1994) and Godsil (Lin. Alg. and its App., 1997)
established a tight correspondence between colour refinement and fractional
isomorphisms of graphs, which are solutions to the LP relaxation of a natural
ILP formulation of graph isomorphism.
We introduce a version of colour refinement for matrices and extend existing
quasilinear algorithms for computing the colour classes. Then we generalise the
correspondence between colour refinement and fractional automorphisms and
develop a theory of fractional automorphisms and isomorphisms of matrices.
We apply our results to reduce the dimensions of systems of linear equations
and linear programs. Specifically, we show that any given LP L can efficiently
be transformed into a (potentially) smaller LP L' whose number of variables and
constraints is the number of colour classes of the colour refinement algorithm,
applied to a matrix associated with the LP. The transformation is such that we
can easily (by a linear mapping) map both feasible and optimal solutions back
and forth between the two LPs. We demonstrate empirically that colour
refinement can indeed greatly reduce the cost of solving linear programs.

We show that the query containment problem for monadic datalog on finite
unranked labeled trees can be solved in 2fold exponential time when (a)
considering unordered trees using the axes child and descendant, and when (b)
considering ordered trees using the axes firstchild, nextsibling, child, and
descendant. When omitting the descendantaxis, we obtain that in both cases the
problem is EXPTIMEcomplete.

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez,
form a large variety of classes of "sparse graphs" including the class of
planar graphs, actually all classes with excluded minors, and also bounded
degree graphs and graph classes of bounded expansion.
We show that deciding properties of graphs definable in firstorder logic is
fixedparameter tractable on nowhere dense graph classes. At least for graph
classes closed under taking subgraphs, this result is optimal: it was known
before that for all classes C of graphs closed under taking subgraphs, if
deciding firstorder properties of graphs in C is fixedparameter tractable,
then C must be nowhere dense (under a reasonable complexity theoretic
assumption).
As a byproduct, we give an algorithmic construction of sparse neighbourhood
covers for nowhere dense graphs. This extends and improves previous
constructions of neighbourhood covers for graph classes with excluded minors.
At the same time, our construction is considerably simpler than those. Our
proofs are based on a new gametheoretic characterisation of nowhere dense
graphs that allows for a recursive version of localitybased algorithms on
these classes. On the logical side, we prove a "rankpreserving" version of
Gaifman's locality theorem.