ACiD
Algorithms and Complexity in Durham
A research group in the Department of Computer Science
Durham University Logo

Seminars from previous years: 2017/18  2016/17  2015/16  2014/15  2013/14  2012/13  2011/12  2010/11

See also NODES activities.

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 word-representable 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 word-representable iff there exists a word w over the alphabet V such that the letters x and y alternate in y iff xy in E. Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colourable graphs and comparability graphs.
After an introduction to the theory of word-representable 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 Diamond-free Graphs
Show Abstract

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. 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 clique-width 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 k-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width 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 clique-width of (H_1,H_2)-free graphs, and our five new classes of bounded clique-width 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 bounded-treewidth 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 self-loop. If is known that reflexive LHOM(H) is polynomial-time solvable if H is an interval graph and it is NP-complete 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 non-interval 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 Exponential-Time 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 PSPACE-complete 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 k-colourings of a graph G has as vertex set the k-colourings 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 k-degenerate 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