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 NPhard problem.
However, restricted to the class of line graphs this problem becomes
polynomialtime 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 coNPhard, and the borderline is given precisely according to whether A enjoys the polynomiallygenerated powers (PGP) property. This reduces the complexity classification problem for QCSPs to that of CSPs, modulo that coNPhard cases might have complexity rising up to Pspacecomplete. 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 exponentiallygenerated 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 polynomialtime solvable problems
Show Abstract
Parameterized complexity analysis is a flourishing field dealing with the exact solvability of "intractable" problems. Appropriately parameterizing polynomialtime 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 NPhard 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 NPhard 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 NPhard and APXcomplete, 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 NPhard 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 NPhardness 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 longstanding 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 
Stefano Giani (Durham Engineering)
tba
Show Abstract

Mon 21 Nov 2016 16:00 in E245 
Nic Georgiou (Durham Maths)
tba
Show Abstract

Mon 28 Nov 2016 16:00 in E245 
Cedric Gerot (Grenoble)
tba
Show Abstract

Mon 5 Dec 2016 16:00 in E245 
Maciej Koutny (Newcastle)
tba
Show Abstract

Mon 12 Dec 2016 16:00 in E245 

Term 2 
Thu 20 Jan 2017 12:00 in E245 

Mon 23 Jan 2017 16:00 in E245 

Mon 30 Jan 2017 16:00 in E245 

Mon 6 Feb 2017 16:00 in E245 
Iddo Tzameret (Royal Holloway)
tba
Show Abstract

Mon 13 Feb 2017 16:00 in E245 

Mon 20 Feb 2017 16:00 in E245 
Tom Friedetzky (Durham)
Tweaking randomised load balancing approaches, part 1
Show Abstract
We will be discussing several load balancing mechanisms based on
ballsintobins 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
sequentialseeming 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 27 Feb 2017 16:00 in E245 
Tom Friedetzky (Durham)
Tweaking randomised load balancing approaches, part 2
Show Abstract
We will be discussing several load balancing mechanisms based on
ballsintobins 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
sequentialseeming 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 6 Mar 2017 16:00 in E245 

Mon 13 Mar 2017 16:00 in E245 
