ACiD Seminars 2018/19 
Term 1 
Thurs 11 Oct 2018 13:00 in E360 

Thurs 18 Oct 2018 13:00 in E360 
Maximilien Gadouleau (Durham)
Decision problems for digraphs inspired by Boolean networks
Show Abstract
Abstract: This talk aims to introduce some of my research and to get interest from researchers in algorithms and complexity (notably of graph problems); as such, it will be fairly relaxed and informal. A Boolean network is a function from {0,1}^n to itself. It is an abstract model for a network of interacting entities, where each entity has a Boolean state that evolves over time according to a deterministic update function. The architecture of the Boolean network is given by its interaction graph, which indicates which update function depends on which states. The main general problem is: how does the interaction graph of a Boolean network affect its dynamics? In this talk, we are interested in the problem of finding a Boolean network with a given interaction graph that satisfies some interesting dynamical properties (e.g. many fixed points, or nilpotence). This yields some new decision problems on digraphs, whose complexities are so far unknown.

Thurs 25 Oct 2018 13:00 in E360 
Sergey Kitaev (Strathclyde)
The role of computer experiments in the theory of wordrepresentable groups [view slides]
Show Abstract
Letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word xyxy... (of even or odd length) or a word yxyx (of even or odd length). A graph G=(V,E) is wordrepresentable iff there exists a word w over the alphabet V such that the letters x and y alternate in y iff xy in E. Wordrepresentable graphs generalise several important classes of graphs such as circle graphs, 3colourable graphs and comparability graphs.
After an introduction to the theory of wordrepresentable graphs, in this talk, I will discuss the impact on the theory of computer experiments.

Thurs 1 Nov 2018 13:00 in E360 
** ACiD meeting! **

Thurs 8 Nov 2018 13:00 in E360 
Konrad Dabrowski (Durham)
Colouring Diamondfree Graphs
Show Abstract
The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) kcolouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)free graphs. Our proof is based on combining known results together with proving that the cliquewidth is bounded for (diamond,P_1+2P_2)free graphs. Our technique for handling this case is to reduce the graph under consideration to a kpartite graph that has a very specific decomposition. As a byproduct of this general technique we are also able to prove boundedness of cliquewidth for four other new classes of (H_1,H_2)free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of cliquewidth of (H_1,H_2)free graphs, and our five new classes of bounded cliquewidth reduce the number of open cases from 10 to 5.
Joint work with François Dross and Daniël Paulusma.

Thurs 15 Nov 2018 13:00 in E360 
Pawel Rzazewski (Warsaw)
Finding list homomorphisms from boundedtreewidth graphs to reflexive graphs: a complete complexity characterization
Show Abstract
In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v)⊂V(H) for every vertex v ∈ V(G). The task is to find a homomorphism φ:V(G) > V(H) respecting the lists, that is, we have that φ(v) ∈ L(v) for every v ∈ V(H) and if u and v are adjacent in G, then φ(u) and φ(v) are adjacent in H. If H is a fixed graph, then the problem is denoted by LHOM(H). We consider the reflexive version of the
problem, where we assume that every vertex in H has a selfloop. If is known that reflexive LHOM(H) is polynomialtime solvable if H is an interval graph and it is NPcomplete otherwise [Feder and Hell, JCTB 1998].
We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time V(H)^tw(G)} * n^O(1) by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of certain decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every noninterval reflexive graph H that
 If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i^*(H)^tw(G) * n^O(1).
 Assuming the Strong ExponentialTime Hypothesis (SETH), the problem cannot be solved in time (i^*(H)ε)^tw(G) * n^O(1) for any ε>0.
Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHOM(H) parameterized by treewidth.
The results are obtained as a joint work with László Egri and Dániel Marx.

Thurs 22 Nov 2018 13:00 in E360

Judith Clymo (Leeds)
Solving Quantified Boolean Formulas
Show Abstract
Quantied Boolean logic is an extension of propositional logic in which variables may be existentially or universally quantified. Determining the truth of a quantified Boolean formula (QBF) is the canonical PSPACEcomplete problem and classes of QBF also characterise the polynomial hierarchy. Industrial problems such as planning with uncertainty and safety criteria for complex systems can be naturally modelled as QBF so, following on from the success of SAT solvers, QBF solvers have received a lot of attention and development in recent years. We introduce some approaches to solving QBF and the proof systems that abstract these algorithms. By using descriptions of proof systems as two player games we can make comparisons and reveal connections between them.

Thurs 29 Nov 2018 13:00 in E360 

Thurs 6 Dec 2018 13:00 in E360 
Carl Feghali (Bergen)
Paths between colourings of sparse graphs
Show Abstract
The reconfiguration graph R_k(G) of the kcolourings of a graph G has as vertex set the kcolourings of G and two vertices of R_k(G) are joined by an edge if the corresponding colourings differ on the colour of exactly one vertex. Given a kdegenerate graph G, a conjecture of Cereceda from 2008 states that R_{k+2}(G) has diameter O(V(G)^2). I will give a short proof of an existing theorem that addresses the conjecture for graphs with bounded maximum average degree. I will also discuss some progress on the conjecture for planar graphs.

Thurs 13 Dec 2018 13:00 in E360 
Joanna Ochremiak (Cambridge)
Proof complexity meets algebra
Show Abstract
Many natural computational problems, such as satisfiability and systems of equations, can be expressed in a unified way as constraint satisfaction problems (CSPs). In this talk I will show that the usual reductions preserving the complexity of the constraint satisfaction problem preserve also its proof complexity. As an application, I will present gap theorems, which say that CSPs that admit small size refutations in some classical proof systems are exactly the constraint satisfaction problems which can be solved by Datalog. This is joint work with Albert Atserias.

Term 2 
Thurs 17 Jan 2019 13:00 in E360 

Thurs 24 Jan 2019 13:00 in E360 
Sebastian Ordyniak (Sheffield)
Recent Advances on the Parameterized Complexity of Integer Linear Programming
Show Abstract
Integer Linear Programming (ILP) is probably the archetypical NPcomplete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomialtime if the constraint matrix is totally unimodular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.
The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a nonzero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. wellknown decompositional parameters such as treedepth, treewidth, and cliquewidth, we will show that the well known blockstructured ILPs (e.g., nfold, twostage stochastic, 4block Nfold, and treefold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.

Thurs 31 Jan 2019 13:00 in E360 

Thurs 7 Feb 2019 13:00 in E360 

Thurs 14 Feb 2019 13:00 in E360 

Thurs 21 Feb 2019 13:00 in E360 
Lawrence Mitchell (Durham)
Robust multigrid solvers for the incompressible NavierStokes equations
Show Abstract
At the core of the numerical simulation of physical systems is the task of inverting discrete representations (matrices) of the continuous equations.
A key goal is to find methods to invert these operators that are both fast (at worst O(n log n) in the number of degrees of freedom), and robust to parameters in the equations. In most cases, we achieve the former by exploiting sparsity in the discretisation to define a hierarchy of scales: the multigrid method is a prototypical example of this.
Addressing the second point is more delicate, and a lot depends on the form of the equations in question. For nearly singular symmetric operators, a robust approach is developed by Lee, Wu, Xu, and Zikatanov (2007). To make use of this theory in practical applications requires one to characterise the basis of the singular part of the operator. I will discuss some recent breakthroughs in this characterisation and finish with some numerically motivated conjectures regarding finite element bases on tetrahedral meshes.
This is joint work with Patrick Farrell, L. Ridgway Scott, and Florian Wechsung. Some parts are presented in https://arxiv.org/abs/1810.03315.

Thurs 28 Feb 2019 13:00 in E360 
Nicolas Bousquet (Grenoble)
Maximum cliques in disk graphs
Show Abstract
In this talk, we present a polynomialtime algorithm that takes as input a finite set of points of $\mathbb R3$ and that computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give a randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii.

Thurs 7 Mar 2019 13:00 in E360 
Marianne Johnson (Manchester)
Upper triangular tropical matrix identities
Show Abstract
Matrices over the tropical semifield arise in models of discrete event systems, optimisation and scheduling problems. In contrast to the case of upper triangular matrices over a field of characteristic 0, it is known that the semigroup of all n x n upper triangular matrices over the tropical semifield satisfy nontrivial semigroup identities. For example, in the case n=2 Izhakian and Margolis have shown that the identity ABBA AB ABBA = ABBA BA ABBA holds for all 2 x 2 upper triangular tropical matrices A and B.
In this talk I will discuss the following questions, relating to some joint work with Laure Daviaud, Mark Kambites, and Ngoc Mai Tran:
* Given a pair of words over a fixed alphabet {A, B}, how to decide if these form an identity for the semigroup of 2 x 2 upper triangular tropical matrices?
* Given a single word over a fixed alphabet {A, B}, how to decide if there exists another word with which it forms an identity for the semigroup of 2 x 2 upper triangular tropical matrices?
The answers to these questions can be readily expressed in terms of certain lattice polytope computations. The case of 2x2 upper triangular matrices is of particular interest to semigroup theorists, because the identities satisfied turn out to be precisely those satisfied by the bicyclic monoid.

Thurs 14 Mar 2019 13:00 in E360 
Sayan Bhattacharya (Warwick)
Some recent advances in dynamic graph algorithms
Show Abstract
Many realworld networks such as the ones arising out of facebook and twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge nsertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of some recent developments in dynamic graph algorithms, focussing primarily on dynamic algorithms for graph coloring and maximum matching.

Thurs 21 Mar 2019 13:00 in E360 
Laurent Bulteau (MarnelaVallée)
Parameterized Algorithms for Consensus String Problems
Show Abstract
Consensus String Problems aim at combining information from different
input strings into a single median "consensus" string. Several variants
of the problem have been considered in the past, where one aims at
minimizing either the maximum distance ("radius") or the sum of
distances ("sum") between the consensus and the input strings. In some
cases, one may also trim the ends of input strings, or even declare a
few of them as "outliers", whose distance can be ignored.
Even though the problem is hard, depending on the dimensions, many
special cases (parameterizations) become tractable using FPT algorithms.
In this study we explore the parameterized complexity of the problem
where both sum and radius constraints are given, giving more flexibility
for an optimal solution. We also introduce the variant where one
considers circular strings, that can be rotated to find a better consensus.
