Seminars1819

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.

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.

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.

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.

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.

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.

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.

Integer Linear Programming (ILP) is probably the archetypical NP-complete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomial-time if the constraint matrix is totally uni-modular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.

The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a non-zero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width, we will show that the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.

At the core of the numerical simulation of physical systems is the task of inverting discrete representations (matrices) of the continuous equations.

A key goal is to find methods to invert these operators that are both fast (at worst O(n log n) in the number of degrees of freedom), and robust to parameters in the equations. In most cases, we achieve the former by exploiting sparsity in the discretisation to define a hierarchy of scales: the multigrid method is a prototypical example of this.

Addressing the second point is more delicate, and a lot depends on the form of the equations in question. For nearly singular symmetric operators, a robust approach is developed by Lee, Wu, Xu, and Zikatanov (2007). To make use of this theory in practical applications requires one to characterise the basis of the singular part of the operator. I will discuss some recent breakthroughs in this characterisation and finish with some numerically motivated conjectures regarding finite element bases on tetrahedral meshes.

This is joint work with Patrick Farrell, L. Ridgway Scott, and Florian Wechsung. Some parts are presented in https://arxiv.org/abs/1810.03315.

In this talk, we present a polynomial-time algorithm that takes as input a finite set of points of $\mathbb R3$ and that computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give a randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii.

Matrices over the tropical semifield arise in models of discrete event systems, optimisation and scheduling problems. In contrast to the case of upper triangular matrices over a field of characteristic 0, it is known that the semigroup of all n x n upper triangular matrices over the tropical semifield satisfy non-trivial semigroup identities. For example, in the case n=2 Izhakian and Margolis have shown that the identity ABBA AB ABBA = ABBA BA ABBA holds for all 2 x 2 upper triangular tropical matrices A and B.

In this talk I will discuss the following questions, relating to some joint work with Laure Daviaud, Mark Kambites, and Ngoc Mai Tran:

* Given a pair of words over a fixed alphabet {A, B}, how to decide if these form an identity for the semigroup of 2 x 2 upper triangular tropical matrices?

* Given a single word over a fixed alphabet {A, B}, how to decide if there exists another word with which it forms an identity for the semigroup of 2 x 2 upper triangular tropical matrices?

The answers to these questions can be readily expressed in terms of certain lattice polytope computations. The case of 2×2 upper triangular matrices is of particular interest to semigroup theorists, because the identities satisfied turn out to be precisely those satisfied by the bicyclic monoid.

Many real-world networks such as the ones arising out of facebook and twitter, webpages and hyperlinks etc. evolve with the passage of time. This motivates the study of dynamic graph algorithms, where we have to maintain the solution to a given optimization problem when the input graph keeps changing via a sequence of updates (edge nsertions/deletions). The goal is to design algorithms whose update times (time taken to handle an edge insertion/deletion) are significantly faster than recomputing the solution from scratch after each update in the input graph. In this talk, I will present a high level overview of some recent developments in dynamic graph algorithms, focussing primarily on dynamic algorithms for graph coloring and maximum matching.

Consensus String Problems aim at combining information from different input strings into a single median “consensus” string. Several variants of the problem have been considered in the past, where one aims at minimizing either the maximum distance (“radius”) or the sum of distances (“sum”) between the consensus and the input strings. In some cases, one may also trim the ends of input strings, or even declare a few of them as “outliers”, whose distance can be ignored. Even though the problem is hard, depending on the dimensions, many special cases (parameterizations) become tractable using FPT algorithms. In this study we explore the parameterized complexity of the problem where both sum and radius constraints are given, giving more flexibility for an optimal solution. We also introduce the variant where one considers circular strings, that can be rotated to find a better consensus.