Stefanie Gerke (Royal Holloway, University of London)
The k-th shortest s-t path in weighted complete graphs
Suppose we weight the edges of the complete graph Kn with independent exponential Exp(1) random weights, pick two distinct vertices s and t, and then successively construct and then remove the edges of minimal weight s-t paths. We describe asymptotically the distributions of the weights of the first k paths obtained in this process. This is joint work with Paul Balister.
John Lapinskas (University of Bristol)
When does approximate counting have the same running time as decision?
It is obvious that if one can approximately count size-k independent sets (for example) up to multiplicative error, then one can decide whether any size-k independent set exists. In many settings, there are foundational results saying that the opposite is also true, and that efficient decision algorithms for hard complexity classes would imply efficient approximate counting algorithms for those same classes; for example, a polynomial-time decision algorithm for SAT would imply an FPRAS for #SAT, and a sub-exponential time algorithm for 3-SAT would imply a sub-exponential time approximation algorithm for #3-SAT. In fine-grained complexity, where we care about not broad categories like “polynomial” or “sub-exponential” but exact running times, the picture is more complicated. A wide class of problems in the area can be viewed as counting edges of a k-uniform hypergraph which is a “natural” function of the instance, using an existing decision algorithm to detect these edges – for example, this is true for counting size-k independent sets, weight-k solutions to CSPs, k-SUM and k-OV. For all problems in this class, it is known that any algorithm for a “colourful” version of the decision problem can be bootstrapped into an approximate counting algorithm with the same running time up to a factor of logO(k)(n). In this talk based on preliminary work, we will address two further questions. First: the dependence on k in logO(k)(n) is potentially quite severe – can it be mitigated? And second: does the same bootstrapping result hold for algorithms for the usual version of the decision problem, without the need for a “colourful” version? We will answer both questions with “it depends”, presenting algorithms when the answer is “yes” and oracle lower bounds when the answer is “no”.
Bridget Webb (The Open University)
Fraïssé limits of Steiner triple systems
A mathematical structure is homogeneous if every isomorphism between two of its substructures
can be extended to an automorphism of the whole. Fraïssé’s theorem says that if a countably infinite
class of finite structures obeys certain properties, and so is an amalgamation class, then there is a
homogeneous countably infinite structure, its Fraïssé limit, whose finitely generated substructures
are precisely the elements of the amalgamation class. For example, the Fraïssé limit of the class of
all graphs is the well-known Rado graph.
In this talk we will look at homogeneous Steiner triple systems, including some recent work
with Daniel Horsley (Monash) where we construct uncountably many homogeneous Steiner triple
systems as Fraïssé limits of amalgamation classes of finite Steiner triple systems avoiding specified
subsystems. These systems are in some ways analogous to the Hensen graphs, however, unlike the
case for graphs, it is unknown whether it is possible to completely classify all homogeneous Steiner
triple systems. We will consider future avenues of research that may help shed light on this difficult
problem.
Richard Mycroft (University of Birmingham)
Spanning trees and tree-like graphs in dense directed graphs
There are numerous recent developments and enticing open problems concerning the question of which oriented trees (or other tree-like structures) can be found in dense directed graphs or tournaments. I will give an overview of some of these questions, before describing recent work with Tassio Naia, in which we show that every oriented tree whose maximum degree is not too large is contained in every directed graph of large minimum semidegree on the same number of vertices. Further development of our methods yields similar result for a wide range of `tree-like’ structures.
Fiona Skerman (Uppsala University)
Partially observing graphs - when can we infer underlying community structure?
Suppose edges in an underlying graph G appear independently with some probability in our observed graph G' - or alternately that we can query uniformly random edges. We describe how high a sampling probability we need to infer the modularity of the underlying graph.
Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1.
In the talk I will spend time on intuition for the behaviour of modularity, how it can be approximated, links to other graph parameters and to present some open problems.
Joint work with Colin McDiarmid. Based on https://arxiv.org/abs/2112.13190.
Erik Jan van Leeuwen (Utrecht University)
Algorithms for planar graphs: From bidimensionality to Steiner Tree
This talk surveys some of the recent techniques to solve parameterized optimization problems on planar graphs, with a focus on the Steiner Tree problem. Many problems on planar graphs, such as deciding whether an n-vertex graph has a vertex cover of size at most k, are known to be decidable in 2O(√k) nO(1) time. Such subexponential-time algorithms do not exist on general graphs, unless the Exponential Time Hypothesis fails. The standard techniques to obtain subexponential-time algorithms on planar graphs, such as bidimensionality, are not applicable to the Steiner Tree problem. In the talk, I will describe the recent progress on this problem for various relevant parameters, and then focus on the case that all terminals can be covered by the boundary of k faces. Erickson et al. [Math. Oper. Res., 1987] showed that this problem can be solved in nO(k) time and nO(k) space. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts.
In recent joint work with Sandor Kisfaludi-Bak and Jesper Nederlof [SODA 2019/ACM TALG 2020], we show a subexponential-time algorithm for this problem with running time 2O(k) nO(√k) using only polynomial space. Furthermore, we show that the running time of the algorithm is almost tight: we prove that there is no f(k) no(√k) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails.
Zoe O'Connor (National Records Scotland)
Census Coverage Adjustment Methodology
Although every effort is made to ensure that everyone is counted in a census, inevitably some people and households are missed. In order to produce a complete census dataset, we must statistically create extra records to fill in these gaps.
We estimate how many people we have missed using key demographic categories such as age-sex bands, ethnicity groups, and household size. The challenge, and the focus for this talk, is how to create new, plausible records which fit these constraints.
In this talk we consider two different methods: the statistical method used in 2011, and a potential alternative for future censuses using combinatorial optimisation.
Ewan Colman (University of Edinburgh)
Counting walks on a temporal network to reveal the drivers of disease propagation
In a temporal network, where edges appear and disappear over time, the importance of a node can be measured using a weighted sum of time-respecting walks. Using a stochastic model to generate networks, we derive formulae that tell us how much of that importance is due to temporal factors, and how much is due to the structure of connections. We apply this to a network of contacts in a hospital ward.
Jason Smith (Nottingham Trent University)
Using Combinatorics to Classify Functional Brain Data
Can we determine what stimulus a brain has received using the spikes of the neurons? Neuron spiking data sets tend to be very large and very noisy, making it difficult to extract information. We will introduce a technique which uses tools from combinatorics and topology to select key neurons, and their neighbourhoods. Using this technique we can extract important information from the spike trains, which we can feed into machine learning classification methods to determine what stimulus the brain has received.