Seminars
Seminars from previous years: 2023/24 2022/23 2021/22 2020/21 2019/20 2018/19 2017/18 2016/17 2015/16 2014/15 2013/14 2012/13 2011/12 2010/11
ACiD Seminars 2024/25.
| Tues 8th October 2024 13:00 MCS 3052 and online | ACiD Meeting! |
| Tues 15th October 2024 13:00 MCS 3052 and online | |
| Tues 22nd October 2024 13:00 MCS 3052 and online | Danny Vagnozzi (Durham) Algebraic aspects of graph isomorphism: the finite field approach In a paper by Berkholz and Grohe (2015), a series of hierarchies of isomorphism invariant equivalence classes of graphs was introduced; namely the polynomial calculus (PC), the monomial calculus (MC), and the Nullstellensatz calculus (NC). Though these have been formulated in the language of proof systems with algebraic rules, they can be seen as a geometric interpretation of the well-studied Sherali-Adams hierarchies which naturally extend to the realm of finite fields. The authors conjectured that for any fixed field, these hierarchies are all equivalent; namely, each level can be simulated by a fixed level of some other hierarchy. We prove this claim for fields of characteristic 0. For fields of positive characteristic, we only prove the equivalence between the MC and NC hierarchies. |
| Tues 29th October 2024 13:00 MCS 3052 and online | Kristina Asimi (Durham) Promise Model Checking Problems The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure (also called model). In this talk, I will present joint work in which we study a class of problems that generalises the CSP simultaneously in two directions: we fix a set L of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak. Given a sentence which only uses symbols from L, the task is to distinguish whether the sentence is true in the strong sense, or it is false even in the weak sense. We call such a problem a Promise Model Checking Problem. We classify the computational complexity of these problems for the existential positive equality-free fragment of first-order logic, i.e., L = {\exists,\land,\lor}, and we prove some upper and lower bounds for the positive equality-free fragment, L = {\exists,\forall,\land,\lor}. In the final part of the talk, I will introduce recent work on Model Checking Problem over the positive equality-free fragment, which also provides the complexity of a specific Promise Model Checking Problem not covered in our paper. |
| Tues 5th November 2024 13:00 MCS 3052 and online | Tala Eagling-Vose (Durham) On diameter, width parameters and forbidden substructures We consider those graph classes characterised by forbidding some subgraph alongside some other structural restriction, in particular bounded diameter. Notably, there are NP-complete problems that are restricted to graphs with a diameter of 2, providing both algorithmic and graph-theoretic motivation to this problem. Towards this, we consider, for various width parameters and containment relations, the question: For which graphs H and diameters d do the class of H-free graphs of diameter d have bounded width? For graph minors such characterisations have been determined for both treewidth and pathwidth, which we extend to treedepth before considering the analogous settings on subgraphs and induced subgraphs. In particular, the subgraph relation presents a far more complex picture with characterisations varying significantly based on the specific diameter. This is joint work with Konrad Dabrowski, Noleen Köhler, Sebastian Ordyniak and Daniël Paulusma. |
| Tues 12th November 2024 13:00 MCS 3052 and online | Benedikt Pago (Cambridge) Limitations of Affine Integer Relaxations for CSP Solving Bulatov and Zhuk have shown that every finite-domain constraint satisfaction problem (CSP) is either NP-complete or in P. It is still open, however, whether there exists a single “universal” polynomial time algorithm that solves all CSPs in P. A potential approach is to formulate such CSPs uniformly as systems of linear equations and solve them over the integers, which is possible in polynomial time. We show that various known algorithms based on this technique fail to solve all tractable CSPs. In fact, they do not even solve all CSPs with Maltsev templates. These algorithms include Z-affine k-consistency, BLP+AIP, every fixed level of the BA^k-hierarchy, and the CLAP algorithm. In particular, we refute a conjecture by Dalmau and Oprsal (LICS 2024) that there is a fixed constant k such that the Z-affine k-consistency algorithm solves all tractable finite-domain CSPs. This is joint work with Moritz Lichter from RWTH Aachen University. |
| Tues 19th November 2024 13:00 MCS 3052 and online | Felicia Lucke (Durham) Matching Cut and Variants in H-free graphs The problem Matching Cut asks for an edge set of a graph which is both an edge cut and a matching. A matching is a set of edges in which no two edges share an endpoint. Consider a partition of the vertices of a graph into two sets R and B, then the edges with one endpoint in R and one in B form an edge cut. In the last years several variants of the problem have been considered: for a Disconnected Perfect Matching problem the matching cut is contained in a perfect matching, while in the Perfect Matching Cut problem the matching cut is a perfect matching. Even more recently the optimisation variants Minimum and Maximum Matching Cut which ask for a matching cut with the minimum/maximum number of edges have been introduced. We consider the complexity of the Matching Cut variants in different graph classes, especially in H-free graphs, which are the graphs that do not contain a graph H as an induced subgraph. We give an overview of recent complexity results and point out some interesting differences between the variants. |
| Tues 26th November 2024 13:00 MCS 3052 and online | Giacomo Paesani (Sapienza, Rome) New results for the Eternal Vertex Cover problem on graph classes In this talk, we consider the Eternal Vertex Cover problem, a dynamic variant of the classical {\sc Vertex Cover} problem that can be modelled as a 2-player game. This problem is NP-hard in general and we aim to understand the computational complexity of EVC when restricting to graph classes. We provide a number of new results for some classes of (in)finite graphs. This is joint work with Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati Girish Nanoti, Sebastian Ordyniak and Mateusz Rychlicki. |
| Tues 3rd December 2024 13:00 MCS 3052 and online | Erik Jan van Leeuwen (Utrecht) Complexity Framework for Forbidden Subgraphs and Beyond For any finite set H = H1,…,Hp of graphs, a graph is H-subgraph-free if it does not contain any of H1,…,Hp as a subgraph. We give a new framework that precisely classifies if problems are “efficiently solvable” or “computationally hard” for H-subgraph-free graphs, depending on H. To illustrate the broad applicability of our framework, we study partitioning, covering and packing problems, network design problems and width parameter problems. We apply the framework to obtain a dichotomy (depending on H) between polynomial-time solvability and NP-completeness of those problems. For other problems we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Along the way we unify and strengthen known results from the literature. We also discuss recent insights into the complexity on H-subgraph-free graphs of problems that do not fall within the framework. This talk is based on joint work with Hans Bodlaender, Matthew Johnson, Barnaby Martin, Jelle Oostveen, Sukanya Pandey, Daniel Paulusma, and Siani Smith. |
| Tues 10th December 2024 13:00 MCS 3052 and online | No seminar (Thomas Erlebach inaugural lecture ~4pm) |
| Tues 14th January 2025 13:00 MCS 3052 only | Laura Larios-Jones (Glasgow) Reachability in temporal graphs under perturbation Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors in reporting, temporal graphs derived from data are unlikely to perfectly reflect reality, especially with respect to the precise times at which edges appear. To reflect this uncertainty, we consider a model in which some number zeta of edge appearances may have their labels perturbed by plus/minus delta for some delta. Within this model, we investigate temporal reachability and consider the problem of determining the maximum number of vertices any vertex can reach under these perturbations. We show this problem to be intractable in general but efficiently solvable when zeta is sufficiently large. We also give algorithms which solve this problem in several restricted settings. We complement this with some contrasting results concerning the complexity of related temporal eccentricity problems under perturbation. |
| Tues 21st January 2025 13:00 online only | Hugo Demaret (École Polytechnique) |
| Tues 28th January 2025 13:00 MCS 3052 and online | Catarina Carvalho (Herts) |
| Tues 4th February 2025 13:00 MCS 3052 and online | Sophie Huczynska (St. Andrews) |
| Tues 11th February 2025 13:00 MCS 3052 and online | Sanidhay Bhambay (Durham Business) |
| Tues 18th February 2025 13:00 MCS 3052 and online | Jorik Jooken (KU Leuven) |
| Tues 25th February 2025 13:00 MCS 3052 and online | Henry Austin (Durham) |
| Tues 4th March 2025 13:00 MCS 3052 and online | |
| Tues 11th March 2025 13:00 MCS 3052 and online | Siani Smith (Loughborough) |
| Tues 18th March 2025 13:00 MCS 3052 and online |