ACiD
Algorithms and Complexity in Durham
A research group in the School of Engineering and Computing Sciences

Seminars from previous years: 2015/16  2014/15  2013/14  2012/13  2011/12  2010/11

 ACiD Seminars 2016/17 Term 1 Thu 20 Oct 2016 12:00 in E245 Vadim Lozin (Warwick) Breaking the boundaries: from structure to algorithms Show Abstract Finding a maximum independent set in a graph is an NP-hard problem. However, restricted to the class of line graphs this problem becomes polynomial-time solvable due to the celebrated matching algorithm of Jack Edmonds. What makes the problem easy in the class of line graphs and what other restrictions can lead to an efficient solution? To answer these questions, we employ the notion of boundary classes of graphs. In this talk, we shed some light on the structure of the boundary separating difficult instances of the problem from polynomially solvable ones and analyze tools to break it. We also discuss similar questions with respect to some other algorithmic problems. Mon 24 Oct 2016 16:00 in E245 Barny Martin (Durham) The Complexity of Quantified Constraints Show Abstract We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is co-NP-hard, and the borderline is given precisely according to whether A enjoys the polynomially-generated powers (PGP) property. This reduces the complexity classification problem for QCSPs to that of CSPs, modulo that co-NP-hard cases might have complexity rising up to Pspace-complete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexity made by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentially-generated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen. Mon 31 Oct 2016 16:00 in E245 Andre Nichterlein (Durham) On parameterized algorithms for polynomial-time solvable problems Show Abstract Parameterized complexity analysis is a flourishing field dealing with the exact solvability of "intractable" problems. Appropriately parameterizing polynomial-time solvable problems helps reducing unattractive polynomial running times. In particular, this "FPT in P" approach sheds new light on what makes a problem far from being solvable in linear time, in the same way as classical FPT algorithms help in illuminating what makes an NP-hard problem far from being solvable in polynomial time. Surprisingly, this very interesting research direction has been too little explored so far; the known results are rather scattered and do not systematically refer to or exploit the toolbox of parameterized algorithm design. In this talk I outline known results, explain some of the corresponding techniques, and highlight similarities and differences to the classical design of parameterized algorithms for NP-hard problems. Mon 7 Nov 2016 16:00 in E245 Argyris Deligkas (Liverpool) The complexity of Greedy Matching Show Abstract Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GreedyMatching. In wide contrast to the maimum weight matching problem, for which many efficient algorithms are known, we prove that GreedyMatching is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GreedyMatching is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider two natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and tractability. On the positive side, we present a randomized approximation algorithm (Rgma) for GreedyMatching on a special class of weighted graphs, called bush graphs. We highlight an unexpected connection between Rgma and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of Rgma is ρ, then for every ε > 0 the randomized Mrg algorithm gives a (ρ − ε)-approximation for the maximum cardinality matching. We conjecture that a tight bound for ρ is 2 ; we prove our conjecture true for two subclasses of bush graphs. Proving a tight bound for the approximation ratio of Mrg on unweighted graphs (and thus also proving a tight value for ρ) is a long-standing open problem. This unexpected relation of our Rgma algorithm with the Mrg algorithm may provide new insights for solving this problem. This is joint work with George Mertzios and Paul Spirakis Mon 14 Nov 2016 16:00 in E245 Wolfram Bentz (Hull) Synchronisation for Automata, Semigroups, and Groups Show Abstract Synchronisation is a property of automata and can be understood as a method of error recovery. An automaton is synchronising if there is an input sequence which always brings the automaton into a known state irrespectively of the original state of the automaton. Such a sequence is called a reset (or synchronising) word. We can translate this question into the realm of semigroup theory by asking if the transition semigroup associated to the automaton contains a constant map. Similarly, we say a permutation group is synchronising if it generates a synchronising semigroup together with any non-invertible transformation. Primitivity of a group is a strong property that is required for synchronisation and usually´´ also forces synchronisation. Our work examines how usual this situation actually is. Our results use an auxiliary graph construction that enables us to approach the problem by combinatorial methods. This is a joint work with Joao Araujo (CEMAT, University of Lisbon), Peter J. Cameron (Mathematical Institute, University of St Andrews), Gordon Royle (Centre for the Mathematics of Symmetry and Computation, University of Western Australia), and Artur Schaefer (Mathematical Institute, University of St Andrews). Mon 21 Nov 2016 16:00 in E245 Nic Georgiou (Durham Maths) Winkler's hat game on graphs Show Abstract Hat games are a popular topic in combinatorics with connections to coding theory, network coding and auctions. In a typical hat game, a team of $n$ players play against a single adversary. The adversary places a coloured hat (from a choice of $q$ different colours) on each player and each player tries to guess the colour of the hat they are wearing by looking at the colours of the hats worn by some of the other players. Many variations on this basic theme exist; we consider the game where all players must guess simultaneously, and the team wins if they have a deterministic strategy where at least one person guesses correctly for each one of the $q^n$ possible configurations of hats. Each player only sees a subset of the hats, as determined by a graph: each vertex in the graph represents a player and each player sees only the hats of his/her neighbours in the graph. If there is a winning strategy for the graph $G$ when the game is played with $q$ different colours, we say that $G$ is $q$-solvable. I will present some constructions for general $q$ which yield two classes of $q$-solvable graphs: i) bipartite, but large, graphs (i.e., number of vertices exponential in $q$); ii) graphs with largest clique of size $\epsilon q$, and number of vertices linear in $q$, for any $\epsilon > 0$; and discuss some related open problems. This is joint work with Maximilien Gadouleau. Mon 28 Nov 2016 16:00 in E245 Victor Dalmau (University Pompeu Fabra, Barcelona) Approximation of MIN CSP Show Abstract An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints (MAX CSP) or, alternatively, to minimize the number of unsatisfied constraints (MIN CSP). This problem is usually parameterized by the set, Gamma, of relations allowed in the constraints, usually called constraint language. It turns out that MAX CSP/MIN CSP is computationally hard for most constraint languages, which motivates the study of approximation algorithms. In this talk we will focus on the approximation of MIN CSPs. We shall start addressing the following question: which constraint languages give rise to a MIN CSPs that is constant-factor approximable? We shall also study some other weaker approximation notions such polynomial loss and robust approximation. Mon 5 Dec 2016 16:00 in E245 (postponed) Mon 12 Dec 2016 16:00 in E245 Stefano Giani (Durham Engineering) Why mesh adaptivity? Show Abstract Mesh adaptivity is becoming a very useful tool to improve the accuracy of finite element simulations. The general idea behind mesh adaptivity is to enrich the finite element space where it is necessary to reduce the error and introducing the smallest number of extra degrees of freedom. In many cases the most advanced adaptive techniques can achieve exponential convergence to the right solution. In the first part of this talk we would like to give an overview of current mesh adaptivity techniques. In the second part we present a different kind of adaptivity based on aggregation that can be used to solve efficiently problems on complicated domains. In the third and final part we explore how finite element aggregation can be used to construct preconditioners. Term 2 Mon 16 Jan 2017 16:00 in E245 Cedric Gerot (Grenoble) When can Box-spline subdivision be factorised into elementary steps? Show Abstract Box-splines are local, possibly anisotropic, piecewise polynomial functions whose integer translates make up a partition of unity. They also satisfy a refinement equation yielding to a subdivision scheme which, if it can be factorised into elementary steps, can be implemented in-place, and be the prediction operator of a biorthogonal multiresolution framework with Box-splines as scaling functions. However, every Box-spline cannot be factorised into elementary steps. We give a necessary and sufficient condition and a sketch of proof which involves linear and commutative algebra. Mon 23 Jan 2017 16:00 in E245 Isolde Adler (Leeds) Wed 25 Jan 2017 13:00 in E245 Kitty Meeks (Glasgow) Mon 30 Jan 2017 16:00 in E245 Viktor Zamaraev (Warwick) On forbidden induced subgraphs for unit disk graphs Show Abstract A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore can be characterized in terms of minimal forbidden induced subgraphs. In spite of quite active study of unit disk graphs very little is known about minimal forbidden induced subgraphs for this class. We found only finitely many minimal non unit disk graphs in the literature. In this paper, we study in a systematic way forbidden induced subgraphs for the class of unit disk graphs. We develop several structural and geometrical tools, and use them to reveal infinitely many new minimal non unit disk graphs. Further, we use these results to investigate the structure of co-bipartite unit disk graphs. In particular, we give a structural characterization of those co-bipartite unit disk graphs whose edges between parts form a C_4-free bipartite graph and show that bipartite complements of these graphs are also unit disk graphs. Our results lead us to propose a conjecture that the class of co-bipartite unit disk graphs is closed under bipartite complementation. Based on joint work with Aistis Atminas. Wed 8 Feb 2016 13:00 in E245 Maciej Koutny (Newcastle) Synthesis of Petri Nets with Whole-place Operations and Localities Show Abstract Synthesising systems from behavioural specifications is an attractive way of constructing implementations which are correct-by-design and thus requiring no costly validation efforts. In this talk, systems are modelled by Petri nets and the behavioural specifications are provided in the form of step transition systems, where arcs are labelled by multisets of executed actions. We focus on the problem of synthesising Petri nets with whole-place operations and localities, which are a class of Petri nets powerful enough to express a wide range of system behaviours, including inhibition of actions, resetting of local states, and locally maximal executions. Mon 13 Feb 2017 16:00 in E245 Iddo Tzameret (Royal Holloway) Mon 20 Feb 2017 16:00 in E245 Stefan Dantchev (Durham) Mon 27 Feb 2017 16:00 in E245 O-joung Kwon (TU Berlin, Germany) Mon 6 Mar 2017 16:00 in E245 Tom Friedetzky (Durham) Tweaking randomised load balancing approaches, part 1 We will be discussing several load balancing mechanisms based on balls-into-bins protocols and random walks. Our focus will be on making standard models more applicable, e.g., by allowing to model tasks sizes and processing speeds, or by attempting to "parallelise" inherently sequential-seeming protocols. This will be more of an overview talk light on proofs (though main ideas and techniques will be discussed). The many authors involved in the various pieces of work will be duly mentioned during the talk. Mon 13 Mar 2017 16:00 in E245 Tom Friedetzky (Durham) Tweaking randomised load balancing approaches, part 2 We will be discussing several load balancing mechanisms based on balls-into-bins protocols and random walks. Our focus will be on making standard models more applicable, e.g., by allowing to model tasks sizes and processing speeds, or by attempting to "parallelise" inherently sequential-seeming protocols. This will be more of an overview talk light on proofs (though main ideas and techniques will be discussed). The many authors involved in the various pieces of work will be duly mentioned during the talk.