Algorithms and Complexity in Durham

Seminars from previous years: 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 2023/24: Please email [email protected] for information on joining.

Tues 3rd October 2023 13:00 MCS 2068 and online	Max Gadouleau (Durham) Words fixing the kernel network and maximum independent sets in graphs The simple greedy algorithm to find a maximal independent set of a graph can be viewed as a sequential update of a Boolean network, where the update function at each vertex is the conjunction of all the negated variables in its neighbourhood. In general, the convergence of the so-called kernel network is complex. A word (sequence of vertices) fixes the kernel network if applying the updates sequentially according to that word always leads to a fixed point whatever the initial configuration. We prove that determining whether a word fixes the kernel network is coNP-complete. We also consider the so-called permis, which are permutation words that fix the kernel network. We exhibit large classes of graphs that have a permis, but we also construct many graphs without a permis. This is joint work with David C. Kutner.
Tues 10th October 2023 13:00 MCS 2068	ACiD Meeting!
Tues 17th October 2023 13:00 MCS 2068 and online	Rachael Colley (University of Glasgow) Measuring and Controlling Divisiveness in Rank Aggregation In rank aggregation, members of a population each rank a number of issues to decide which are collectively preferred. In this talk we will focus instead on identifying divisive issues that express disagreements among the preferences of individuals. We analyse the properties of our divisiveness measures and their relation to existing notions of polarisation. We also study their robustness under incomplete preferences and algorithms for control and manipulation of divisiveness. Our results advance our understanding of how to quantify disagreements in collective decision-making. Joint work with Umberto Grandi, César Hidalgo, Mariana Macedo, and Carlos Navarrete
Tues 24th October 2023 13:00 MCS 2068	Naveen Garg (IIT Delhi) Capacitated Facility Location with Outliers In this talk I will present a simple local search algorithm for capacitated facility location when facility costs are uniform. Our algorithm is a 3.732-approximation and improves the 4-approximation of Kao. In the second part of the talk, I will consider the setting when we are permitted not to serve L clients (outliers). We extend the local search algorithm to obtain the first constant factor approximation for this problem. Our local search algorithm requires only 2 operations and is a 6.372-approximation.
Tues 31st October 2023 13:00 MCS 2068 and online	Mengxiao Zhang (Durham) Multi-unit Auction over a Social Network Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus on designing mechanisms for multi-unit diffusion auctions. Despite numerous attempts at this problem, existing mechanisms either fail to be incentive compatible (IC) or achieve only an unsatisfactory level of social welfare (SW). Here, we propose a novel graph exploration technique to realise multi-item diffusion auction. This technique ensures that potential competition among buyers stay “localised” so as to facilitate truthful bidding. Using this technique, we design multi-unit diffusion auction mechanisms MUDAN and MUDAN-$m$. Both mechanisms satisfy, among other properties, IC and $1/m$-weak efficiency. We also show that they achieve optimal social welfare for the class of rewardless diffusion auctions. While MUDAN addresses the bottleneck case when each buyer demands only a single item, MUDAN-$m$ handles the more general, multi-demand setting. We further demonstrate that these mechanisms achieve near-optimal social welfare through experiments.
Tues 7th November 2023 13:00 MCS 2068
Tues 14th November 2023 13:00 MCS 2068	Joachim Spoerhase (Sheffield) Parameterized Approximation Schemes for Clustering with General Norm Objectives This paper considers the well-studied algorithmic regime of designing a (1+epsilon)-approximation algorithm for a k-clustering problem that runs in time f(k,epsilon)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable previous results of this kind include EPASes in the high-dimensional Euclidean setting for k-center as well as k-median, and k-means. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space. Our main contribution is a clean, simple, and unified algorithm that yields an EPAS for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, l-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and which is (almost) entirely oblivious to the underlying objective and metric space. Key to our approach is a new concept that we call bounded epsilon-scatter dimension — an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension. This is joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, and Roohani Sharma
Tues 21st November 2023 13:00 MCS 2068	Silvia Butti (Oxford) Promise Valued CSPs: an algebraic framework for approximation problems The Promise Valued Constraint Satisfaction Problem (PVCSP) extends the CSP framework in two independent directions. In the promise setting, each constraint comes in a strong version and a weak version, and the task is to distinguish whether the input is satisfiable in the strong sense, or it is not satisfiable even in the weak sense. In the valued setting, each constraint has a cost, and the goal is to decide whether there exists an assignment whose total cost is smaller than a given threshold. PVCSPs combine and generalize both Promise and Valued CSPs and are general enough to include all constant-factor approximation problems for Max-CSP, such as approximate satisfiability of Boolean CNF-formulas. In this talk I will discuss a recently developed algebraic framework for obtaining complexity reductions between PVCSPs, heavily inspired by the highly successful algebraic approach to Promise CSPs. I will then show how some well-known inapproximability results can be explained in a new light using this framework. Joint work with Libor Barto, Alexandr Kazda, Caterina Viola, and Standa Živný.
Tues 28th November 2023 13:00 MCS 2068	Robert Lieck (Durham) What do Music, Hyper-Graph Search, and Markov Chain Monte Carlo have in common? Music presents a range of interesting challenges to conventional inference methods. Some aspects can be modelled as a sequence of discrete events (similar to language/text) using probabilistic context-free grammars (PCFGs). Others require generalising 1) from discrete to continuous variables and/or 2) from sequential to non-sequential structures. While PCFGs have O(n^3 k) complexity (n: sequence length, k: alphabet size), exact solutions quickly become intractable in continuous and non-sequential settings requiring heuristics and approximate inference methods. In this talk, I will briefly highlight why music is such a multifaceted and fascinating problem to work on. I will then present some past [1], present and future work and challenges for inference with discrete-continuous, hierarchical, probabilistic models. [1] Lieck R, Rohrmeier M (2021) Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks. In: Advances in Neural Information Processing Systems 34.
Tues 5th December 2023 13:00 MCS 2068	Lorenzo Ciardo (Oxford) Promise CSPs: a linear-algebraic view Testing whether a graph is 3-colourable is a classic NP-complete computational problem. On the other hand, the complexity of distinguishing whether a graph is 3-colourable or not even, say, 100-colourable is a long-standing open question in computational graph theory. The focus of this talk shall be on a class of problems, known as Promise CSPs, that generalise the “3 vs. 100” colouring problem. I will describe a framework for capturing the power of several polynomial-time relaxations of Promise CSPs under a unique umbrella. This approach, based on linear algebra, unifies the study of the standard relaxation models such as linear and semidefinite programming, Gaussian elimination, and combinatorial consistency. As the main application of the linear-algebraic approach, I will make use of results from tensor theory and spectral graph theory to obtain lower bounds against the power of relaxations, by showing that they are not strong enough to solve the “3 vs. 100” problem. Based on a joint work with Standa Živný.
Tues 9th January 2024 13:00 MCS 2068
Tues 16th January 2024 13:00 MCS 2068	Noleen Köhler (Leeds) Bandwidth Parameterized by Cluster Vertex Deletion Number Given a graph G and an integer b, Bandwidth asks whether there exists a bijection pi from V(G) to {1, …,\|V(G)\|} such that max_{{u, v} in E(G)} \| pi(u) – pi(v) \| \leq b. This is a classical NP-complete problem, known to remain NP complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the treedepth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number of the input graph. In this paper, we make progress towards the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number $\omega$ of the input graph, thus generalizing the previously mentioned result for vertex cover. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results generalize some of the previous results and narrow some of the complexity gaps. This is joint work with Tatsuya Gima, Eun Jung Kim, Nikolaos Melissinos and Manolis Vasilakis.
Tues 23rd January 2024 13:00 MCS 2068	ACiD Meeting!
Tues 30th January 2024 13:00 MCS 2068	David Cushing (University of Manchester) Prolog whispering, constraint logic programming and how to win on the UK National Lottery Originating in 1972 through Alain Colmerauer and Philippe Rousse, the Prolog programming language deviates from conventional languages by articulating the programmer’s intent through object relations and queries on the resultant amalgamated knowledge base, rather than a linear sequence of operations. Prolog operates by loading in a list of axioms as input, and then responds at the command line to queries that ask the language to achieve particular goals, given those axioms. It gained some notoriety through IBM’s implementation of ‘Watson’, which was a system designed to play the game show Jeopardy. Through a very efficiently implemented constraint logic programming module, it also has one of the worlds fastest sudoku solver. The talk emphasises the process of writing code to open up a dialogue with Prolog. We discuss the implementation of fundamental techniques such as symmetry breaking, which aids in efficient exploration of the solution space. Furthermore, we delve into the theory of constraint propagation and its significance in refining and optimising the search process. We aim to give insights into the art of “Prolog whispering”, encouraging the adoption of this approach. Along the way I will outline how Prolog has helped us discover new simple Lie algebras, win on the lottery, and how we are currently using it to solve International Mathematical Olympiad problems.
Tues 6th February 2024 13:00 MCS 2068
Tues 13th February 2024 13:00 MCS 2068
Tues 20th February 2024 13:00 MCS 2068 only	Jakub Oprsal (University of Birmingham) NP-hardness of promise colouring graphs and hypergraphs via homotopy A colouring of a graph with k colours is an assignment of colours to vertices so that no edge is monochromatic. It is well-known that if there is a polynomial time algorithm for finding a colouring with 3 colours even when we are promised that such a colouring exists, then the computational classes P and NP collapse. This raises a question of whether we can efficiently colour graphs that are promised satisfy a stronger condition, e.g., those that allow a homomorphism (an edge-preserving map) to an odd cycle? In a proof based on topological ideas (first used to show lower bounds of chromatic number of Kneser graphs by Lovász), we will show that this strengthening the promise does not make the problem easier, and we will discuss a similar application of homotopy in showing hardness of certain promise hypergraph colouring.
Tues 27th February 2024 13:00 MCS 2068 only	Marianne Johnson (Manchester) Can you guess what it is? Consider a guessing-game with two participants: the teacher and the learner. The teacher has an object they wish the learner to discover. By asking a series of questions, the learner formulates a hypothesis that matches their observations so far; if their hypothesis is incorrect, the teacher supplies a piece of information that distinguishes the hypothesis from the true object. Play continues in this manner until the learner discovers the object… In this talk I will discuss a specific instance of this general set up, in which the object to be discovered is the function computed by a finite-state weighted automaton with weights drawn from a semiring S. In the case where S is the Boolean semiring, Angluin’s L* algorithm allows the learner to successfully construct an automaton that computes the target function (or in other words, recognises a given regular language) using only membership and equivalence queries. This algorithm has been modified to apply in some other settings, including by van Heerdt, Kupke, Rot, and Silva in the case where S is a principal ideal domain (subject to the ability to solve S-linear systems of equations). In joint work with Laure Daviaud, we take a step back to consider the basic ideas behind this algorithms in the case where the weights are drawn from an arbitrary semiring. We show that (aside from some very natural issues already identified) there is an extremely fundamental problem: over some sem irings (including the natural numbers, non-negative reals, and the tropical semiring) there are functions computed by finite-state automata for which all possible hypothesis automata (i.e. those generated by the process of the algorithm) fail to compute the target function. In other words, over such semirings, there are functions where there is simply no hope to `guess what it is’ by this method. We provide several equivalent characterisations of the functions for which a correct hypothesis exists, and classify functions with respect to how “guessable’’ they are (corresponding to the existence and abundance of solutions of certain systems of S-linear equations).
Tues 5th March 2024 13:00 MCS 2068	David Fairbairn (Durham Maths) NP-Completeness of the Combinatorial Distance Matrix Realisation Problem The Combinatorial Distance Matrix Realisation Problem is the problem of determining whether a K x K distance matrix is realised by a subset of K vertices in some combinatorial graph of a given size N >= K. In this talk we show the pre-existing results for the problem when N = K and a trivial bound for which there is always a realisation of the distance matrix. We then present our results that show that the problem when N = K + 1, N = K + 2 are polynomial time solvable, and that the problem is NP-Complete when N = K + 3. Furthermore, in showing the NP-Completeness in the case N = K + 3, we provide a construction which can be generalised to show that the problem is NP-Complete for all N >= K + 3. Time permitting, we will introduce the motivations for our study of this problem within the context of Multi-Agent Path-Finding.
Tues 12th March 2024 13:00 MCS 2068	Natasha Shakhlevich (Leeds) Network Flow Techniques for Pre-emptive Scheduling: Revising and Extending Horn’s Conditions Network flow models are widely used in scheduling research since the 70s. A prominent example is the highly cited paper “Some simple scheduling algorithms” by Horn (1974). In that paper, Horn proposed a network flow model for pre-emptive processing of jobs by parallel machines, subject to job deadlines. Another result, formulated by Horn in isolation from the network flow model, is a set of inequalities for checking the feasibility of a problem instance. Both results provide a foundation for subsequent research on enhanced versions of the problem, including the version with arbitrary release dates and deadlines, uniform machines, scheduling with controllable processing times and inverse optimization, to name a few. In our work we demonstrate that the two results, network flow model and a set of inequalities for the feasibility check, are linked via the min cost max flow theorem. It gives a solid methodology for modelling quite intricate scheduling problems via network flows, for example, an extended model with resource constraints.