Algorithms and Complexity in Durham

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) Fractional domatic number and minimum degree The domatic number of a graph G is the maximum number of pairwise disjoint dominating sets of G. We are interested in the LP-relaxation of this parameter, which is called the fractional domatic number of G. We study its extremal value in the class of graphs of minimum degree d. The fractional domatic number of a graph of minimum degree d is always at most d+1, and at least (1-o(1))d/ln d as d goes to infinity. This is asymptotically tight even within the class of split graphs. Our main result concerns the case d=2. We show that, excluding 8 exceptional graphs, the fractional domatic number of every connected graph of minimum degree at least 2 is at least 5/2. We also show that this bound cannot be improved if only finitely many graphs are excluded, even when restricting to bipartite graphs of girth at least 6. This proves in a stronger sense a conjecture by Gadouleau, Harms, Mertzios, and Zamaraev (2024). This also extends and generalises results from McCuaig and Shepherd (1989), from Fujita, Kameda, and Yamashita (2000), and from Abbas, Egerstedt, Liu, Thomas, and Whalen (2016). Finally, we show that planar graphs of minimum degree at least 2 and girth at least g have fractional domatic number at least 3-O(1/g) as g goes to infinity. We present these results and provide insights into the proof. This is a joint work with Quentin Chuet, Hugo Demaret, Hoang La and François Pirot.
Tues 28th January 2025 13:00 MCS 3052 and online	Catarina Carvalho (Herts) Digraphs with caterpillar duality We search for the class of digraphs whose obstruction sets, in the digraph homomorphism problem, consist of caterpillars. The conjecture being that this class of digraphs should be the same as the class of digraphs that are preserved by majority and set function polymorphisms. This is work in progress.
Tues 4th February 2025 13:00 MCS 3052 and online	Sophie Huczynska (St. Andrews) Applications of difference families in cryptography and communications Difference families are combinatorial structures consisting of subsets of a group with strong uniformity conditions on their differences. Many different problems in cryptography (eg algebraic manipulation detection codes) and communications (eg optical orthogonal codes, comma-free codes) may be modelled in terms of these structures and their generalizations. Moreover, they are of strong theoretical interest, having links with graph theory and combinatorial designs. In this talk, I will discuss internal and external difference families and their applications, and describe a recently-developed framework for constructing them. (Joint work with Laura Johnson and Maura Paterson).
Thursday 6th February 2025 11:00 in the VisLab (MCS 1022).	Special Seminar! H.H. (Alison) Liu, (Utrecht University) Online Busy Time Scheduling with Untrusted Prediction In this work, we study the online busy time scheduling problem with infinite processors, where each job j has a release time r_j, a processing time p_j, and a deadline d_j. Busy time scheduling aims to use multiple processors to schedule jobs concurrently to minimize the time a machine has to process jobs. We consider the case proposed by Koehler and Khuller, where a single machine has unlimited processors. Moreover, we consider the case where the online algorithm can access prediction, which might be imperfect, on when the machine should be active. We present an algorithm, Multiplier, that dynamically adjusts its strategy for reserving time windows for potential future jobs according to the prediction it receives and how much it trusts the prediction. We show that Multiplier is (1 + 4/(1+λ) )-consistent and (1 + 4/(1−λ) )-robust with a trust parameter lambda \in [0, 1). This is a joint work with Rick van de Bovenkamp.
Tues 11th February 2025 13:00 MCS 3052 only	Sanidhay Bhambay (Durham Business) Optimal Scheduling in a Quantum Switch With a growing number of quantum networks in operation, there is a pressing need for performance analysis of quantum switching technologies. A quantum switch establishes, distributes, and maintains entanglements across a network. In contrast to a classical switching fabric, a quantum switch is a two-sided queueing network. The switch generates Link-Level Entanglements (LLEs), which are then fused to process the network’s entanglement requests. Our proof techniques analyse a two-time scale separation phenomenon at the fluid scale for a general switch topology. This allows us to demonstrate that the optimal fluid dynamics are given by a scheduling algorithm that solves a certain average reward Markov Decision Process.
Tues 18th February 2025 13:00 MCS 3052 and online	Jorik Jooken (KU Leuven) Computer-assisted graph theory: a case study of minimal obstructions to H-coloring In this talk, I will give an introduction to computer-assisted graph theory. This is a branch of graph theory which is concerned with the question how computers and algorithms can help to solve questions in graph theory where a purely manual approach is not sufficient. To illustrate one of the uses of computer-assisted graph theory, I will talk about recent results that we obtained in the context of minimal obstructions to H-coloring. For given graphs G and H, we say that G is H-colorable if there exists an edge-preserving mapping from vertices of G to vertices of H. A graph G is a minimal obstruction to H-coloring if G is not H-colorable, but every proper induced subgraph of G is H-colorable. I will show how algorithms were used to prove that for certain classes of graphs there are only finitely many minimal obstructions to H-coloring, whereas for other classes of graphs there are infinitely many such graphs. Additionally, we precisely characterize this finite set. This talk is mainly based on joint work with Jan Goedgebeur, Karolina Okrasa, Paweł Rzążewski and Oliver Schaudt. Paper available at: https://doi.org/10.4230/LIPIcs.MFCS.2024.55
Tues 25th February 2025 13:00 MCS 3052 and online	Henry Austin (Durham) The Power of Two Chances: Fast Self-Stabilizing Leader Election in Population Protocols The Population model is a well-established model for anonymous asynchronous distributed computing. In this talk, we consider Self Stabilizing Leader Election, the problem of designating a unique leader beginning from an arbitrarily bad initial configuration. Recent research in the area has been split into two strands: reducing the state complexity of time optimal algorithms and reducing the run time of state optimal algorithms. In this talk, we will discuss recent algorithmic developments in both strands and present a new protocol solving the problem in optimal time using only $O(n^2 \log{n})$ bits of state, dramatically improving the state of the art $O(n^{\log{n}})$ bits. This algorithm depends on several novel techniques for collision detection and provides a black box framework for the acceleration of self stabilizing population protocols under certain conditions. As a consequence of this result we obtain a subcubic upper bound on the bit complexity of the self-stabilizing computation of arbitrary functions between multi-sets of bounded support in time optimal population protocols. This talk is based on joint work with Petra Berenbrink, Tom Friedetzky, Thorsten Götte and Lukas Rasmus Hintze.
Tues 4th March 2025 13:00 MCS 3052 and online	ACiD Meeting!
Tues 11th March 2025 13:00 MCS 3052 and online	Siani Smith (Loughborough) Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs The d-Cut problem asks whether a graph admits an edge cut such that each vertex is contained in at most d cut edges. For example, the case d=1 gives the Matching Cut problem. We study the complexity of d-Cut in graphs of bounded diameter and H-free graphs. In the first case, we obtain complete dichotomies for graphs of bounded diameter and graphs of bounded radius. For H-free graphs, we obtain almost-complete dichotomies. This is joint work with Felicia Lucke, Ali Momeni and Daniel Paulusma.
Tues 18th March 2025 13:00 MCS 3052 and online	Jungho Ahn (Durham) A coarse Erdös-Pósa theorem for constrained cycles An induced packing of cycles in a graph G is a set of vertex-disjoint cycles such that G has no edge between distinct cycles of the set. The classic Erdős-Pósa theorem asserts that for every positive integer k, every graph contains k vertex-disjoint cycles or a set of O(klog k) vertices which intersects every cycle of G. We generalise this classic Erdős-Pósa theorem to induced packings of cycles of length at least ell for any integer ell. We show that there exists a function f(k,ell)=O(ellklog k) such that for all positive integers k and ell with ell>2, every graph G contains an induced packing of k cycles of length at least ell or a set X of at most f(k,ell) vertices such that the closed neighbourhood of X intersects every cycle of length at least ell in G. Furthermore, we extend the result to long cycles containing prescribed vertices. For a graph G and a subset S of V(G), an S-cycle in G is a cycle containing a vertex in S. We show that for all positive integers k and ell with ell>2, every graph G, and every subset S of V(G), G contains an induced packing of k S-cycles of length at least ell or a set X of at moat ellk^{O(1)} vertices such that the closed neighbourhood of X intersects every S-cycle of length at least ell in G. Our proofs are constructive and yield XP algorithms, parameterized by ell, which finds either the induced packing of the constrained cycles or the set X. This is based on joint works with Pascal Gollin, Tony Huynh, and O-joung Kwon.
Tues 20th May 2025 13.00 MCS 3052	Sara Riva (Lille) and Marius Rolland (LIS – Marseille) TBA