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)
TBA

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 
Marianne Johnson (Manchester)
TBA

Thurs 28 Feb 2019 13:00 in E360 

Thurs 7 Mar 2019 13:00 in E360 

Thurs 14 Mar 2019 13:00 in E360 
Sayan Bhattacharya (Warwick)

Thurs 21 Mar 2019 13:00 in E360 
