Seminars1920

Matroids are abstract structures that encapsulate a notion of dependence appearing in graph theory, linear algebra, and discrete geometry. A matroid is said to be representable over a field F if it has a representation as a set of vectors in a vector space over F, where the notion of dependence is linear dependence. Characterising when a matroid is representable over a certain field, or set of fields, is one of the oldest problems in matroid theory. From an algorithmic point of view, such classes of representable matroids are often the underlying structure conducive to efficient algorithms. In this talk, I will review some known results in the area, and discuss recent progress towards finding characterisations of particular classes of matroids that are representable over all fields in some set. Prior familiarity with matroids will not be assumed.

In the Q-Boolean-2-CSP Deletion problem, the input is a totally quantified boolean 2-CSP and an integer k and the objective is to decide whether there is a set of at most k constraints whose deletion makes the resulting quantified 2-CSP true. This problem generalizes several well-studied problems such as graph bipartization, (directed) multiway cut, quantified H-coloring (for appropriate H) and max 2-SAT. In this talk, I will present some recent developments in the parameterized complexity of this problem and discuss some exciting related open problems. Based on joint work with Daniel Marx.

Imagine a network where every user is very aggressive about forwarding the messages they receive (like hyperactive WhatsApp users). The users are polite enough in that they do not send the message back to the users they have just received the message from in the previous round. However, as busy social media users, they quickly forget this interaction and forward the same message if they get it again in the future – potentially circulating the same message till the end of social media civilisation! Consider any arbitrary finite graph modelling such a network and a user who begins the process by flooding (we call this Amnesiac Flooding) one such message. The natural question is will Amnesiac flooding ever stop i.e. will this message stop getting circulated? In general, flooding is about the simplest of distributed algorithms achieving broadcast of messages to all nodes but termination is a critical property to achieve. We analyse both the termination of Amnesiac Flooding and termination times and get somewhat surprising results.

In this talk, we consider several classical and novel algorithmic problems for graph groups, which are also known as right-angled Artin groups or RAAGs. Many of these problems are closely related to graph theoretic problems, and their computational complexity is of intrinsic interest. Moreover, we are interested in these problems from the point of view of applications to cryptography. This is a joint work with R. Flores (Seville) and T. Koberda (Virginia).

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size of a semitotal dominating set of a graph is squeezed between its domination number and its total domination number. In the talk, I will report on the systematic study on the computational complexity of Semitotal Dominating Set, the problem of finding, given a graph G, a minimum size semitotal dominating set of G. In particular, I will show that the problem is solvable in polynomial time for graphs of bounded mim-width and present several open problems. Joint work with Esther Galby and Bernard Ries

It is well known that the problem of finding a 3-colouring of a given 3-colourable graph is NP-hard. A graph G has circular chromatic number at most 2+1/k iff G admits a homomorphism to a cycle on 2k+1 vertices. Every such graph G is clearly 3-colourable. We prove that, for any positive k, the problem of finding a 3-colouring of a given graph with circular chromatic number at most 2+1/k is NP-hard. This is joint work with Jakub Oprsal.

Population protocols are a model of distributed computing, where n agents with limited computational power and memory interact randomly, in order to jointly perform a global task. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. We establish that if agents have Omega(\log\log n) states, the expected time complexity of leader election is Theta(n \log n). Unlike existing protocols, ours does not decrease the set of candidate leaders monotonically. Our protocol has both optimal time and space complexity. Joint work with George Giakkoupis and Peter Kling.

I will present several applications of topology in graph colouring and related problems, from classical lower bounds on chromatic numbers of graphs, through toy examples in statistical physics, to recent results in hardness of approximation. Surprisingly, even though the questions are purely combinatorial, topology turns out to give elegant solutions, and is sometimes provably unavoidable, in some technical sense. No knowledge of topology assumed. Based on joint work with Stanislav Zivny, Andrei Krokhin, and Jakub Oprsal.

The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice based cryptography. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of ‘structured’ LWE. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a Ring LWE instance. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE), which can be seen as a non-commutative version of Ring LWE. The proposed construction is both more efficient than Module LWE and conjecturally more secure than Ring LWE, the best of both worlds.

Several important graph transversal problems can also be viewed as graph modification problems. For example 3-Colouring can be viewed as deciding whether some independent set can be deleted from a graph to leave it bipartite whilst Independent Odd Cycle transver- sal is the problem of deciding whether there exists such a set of size at most k. Similarly, Near-Bipartiteness is the problem of deciding whether some independent set of vertices can be deleted from a graph to obtain a forest whilst Independent Feedback Vertex Set requires deciding whether there exists such a set of size at most k.

All these problems are NP-complete even after restricting the input to classes of H-free graphs for many graphs H (a graph is H-free if it does not contain H as an induced subgraph). However, this may change once we bound some graph parameter in addition (which may imply the graph class is no longer hereditary). For example, it can be observed that the computational complexity of all problems restricted to claw-free graphs jumps from being NP-complete to being constant-time solvable if we assume any constant upper bound on the diameter of the graph. Starting from this initial observation, we determine the complexity of the above problems for H-free graphs, exploiting the effect of additionally bounding the diameter of the input graph in order to obtain new polynomial-time results.

The talk is based on joint work with: Barnaby Martin and Daniel Paulusma

An instance of the constraint satisfaction problem (CSP) consists of a set of constraints on a set of variables, and the goal is to decide if there exists an assignment to the variables satisfying all of the constraints. One obtains a rich family of problems by parameterizing by the so-called constraint language, a set of relations that may be used to pose constraints. The so-called algebraic approach to constraint satisfaction, whereby universal algebraic methods and techniques are used to gain insight into the complexity of such problems, has led to the establishment of comprehensive dichotomy theorems; these theorems completely describe the complexity of all problems within some large family (with respect to inclusion in some complexity class). Such theorems have been given for the vanilla CSP as well as for many different variations thereof.

In this talk, we describe three cases where there was a failure to establish a dichotomy theorem, and moreover, where (in each case) the failure can be evidenced by a single concrete computational problem that can be described simply (and apprehended by any undergraduate student!). For each case, we survey the background behind and the state-of-the-art of the problem, and also discuss how the problem points to the development of further and broader theory.

Parental advisory warning: this talk may include explicit content in the form of conjectures, speculation, and cash awards.

In 1996, Markossian, Gasparian and Reed introduced the class of beta-perfect graphs, a subclass of even-hole-free graphs for which the greedy colouring algorithm produces an optimal colouring in polynomial time. A forbidden induced subgraph characterisation of beta-perfect graphs is unknown. It is also not known if there exists a polynomial-time algorithm for deciding whether a given graph is beta-perfect. A number of classes of graphs have been shown to be beta-perfect, and their corresponding recognition problems are solvable in polynomial time.

In this talk, we present a class of beta-perfect graphs that generalises both chordal graphs and a class of beta-perfect graphs given in the paper of Markossian, Gasparian and Reed. We also present a characterisation of beta-perfect ‘hyperholes’; a small step towards understanding how the class of beta-perfect graphs behaves with respect to clique-cutset operations.

This talk is based on joint work with Kristina Vuskovic.

Abstract: In this talk we will describe a size lower bound for the size of `proofs’ of the nonexistence of a k-clique in a graph in a particular proof system. No prior knowledge will be assumed.