The slides of some of the talks can be found here.
Saturday 7th January 2017, Horton Lecture Theatre 1
10.20 – 10.50 coffee/tea break (McCrea 219)
10.50 – 11.00 Welcome
11.00 – 11.30 Noga Alon Universal Tournaments
11.35 – 12.05 Jorgen Bang-Jensen 2-partitions of digraphs
12.10 – 12.40 Anders Yeo Perfect Forests in Digraphs
12.40 – 14.30 lunch break (McCrea 219)
14.30 – 15.00 Michael Krivelevich Long cycles in locally expanding graphs, with applications
15.05 – 15.35 Eunjung Kim A polynomial kernel for distance-hereditary vertex deletion
15.35 – 16.10 coffee/tea break (McCrea 219)
16.10 – 16.40 Benny Sudakov Rainbow cycles and trees in properly edge- colored complete graphs
16.45 – 17.15 Mark Jones Enforcing Information Flow Policies Through Chain- And Tree-based Enforcement Schemes
18.30 Dinner (Large Board Room, Founders) Only if you have reserved a seat!
Sunday 8th January 2018, McCrea 219
9.30 – 10.00 Fedor Fomin Finding Detours is Fixed-parameter Tractable
10.05 – 10.35 Stefan Szeider Backdoors for Constraint Satisfaction
10.35 – 11.00 coffee/tea break (McCrea 237)
11.00 – 11.30 Saket Saurabh Gregory: The “Tree” of Knowledge
11.35 – 12.05 Igor Razgon Well quasi-orderability vs. cliquewidth
12.10 – 12.40 Daniel Karapetyan Practically efficient algorithms for the Workflow Satisfiability Problem and its optimisation version
Abstracts:
Noga Alon, Universal Tournaments
Tournaments have been the subject of much of the work of Gutin. In the spirit of his work I will discuss the problem, raised by Moon in the 60s, of estimating the minimum possible number of vertices in a tournament that contains every k-vertex tournament as an induced subgraph. The main result is that this number is (1+o(1))2^{(k-1)/2}, improving earlier estimates of several researchers. The proof combines combinatorial and probabilistic techniques with group theoretic tools.
Joergen Bang-Jensen, 2-partitions of digraphs
We report on recent results with various coauthors on the complexity of deciding whether a given digraph D has a vertex partition into two digraphs D’ and D” such that these have pre-specified properties. These could be: minimum out-degree at least k, being strongly connected, acylic and lots of others. Among the results on which we report is a complete classification of the complexity for 120 natural such problems. This part is joint work with Havet and Cohen.
Fedor Fomin, Finding Detours is Fixed-parameter Tractable
We consider the following natural “above guarantee” parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k.
Joint work with Ivona Bezáková, Radu Curticapean, and Holger Dell.
Mark Jones, Enforcing Information Flow Policies Through Chain- And Tree-based Enforcement Schemes
In an information flow policy, users have different access permissions based on their position in a hierarchy or partial order. In most enforcement schemes that use symmetric cryptographic primitives, each user is assigned a single secret and derives decryption keys using this secret and publicly available information. Recent work has challenged this approach by developing schemes, based on chain or tree partitions of the information flow policy, that do not require public information for key derivation, the trade-off being that a user may need to be assigned more than one secret. In this talk, we show how to construct chain- and tree-based cryptographic enforcement schemes, and give polynomial -time algorithms to find such enforcement schemes using the minimum number of secrets.
Daniel Karapetyan, Practically efficient algorithms for the Workflow Satisfiability Problem and its optimisation versions
We consider an interesting satisfiability problem finding applications in access control. The problem is known to be fixed parameter tractable (FPT) but existing algorithms are relatively inefficient in practise. Our new algorithm more than doubled the value of the parameter that could be practically tackled. The key idea of this new approach is also incorporated into a Pseudo-Boolean formulation, with promising results. In the second part of the talk, we discuss single- and bi-objective optimisation extensions of the problem. While providing much greater modelling power, these extensions are still FPT, and our algorithms need only small modification to be used for them. Some conclusions of this research may be applicable to other FPT problems.
Eunjung Kim, A polynomial kernel for distance-hereditary vertex deletion
A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. Distance hereditary graphs are exactly the graphs with rank-width at most 1. The Distance-Hereditary Vertex Deletion problem asks, given a graph G on n vertices and an integer k, whether there is a set S of at most k vertices in G such that G−S is distance-hereditary. It was shown by Eiben, Ganian, and Kwon (MFCS’ 16) that Distance-Hereditary Vertex Deletion can be solved in time 2^O(k)n^O(1), and they asked whether the problem admits a polynomial kernelization. We show that this problem admits a polynomial kernel, answering this question positively. For this, we use a similar idea for obtaining an approximate solution for Chordal Vertex Deletion due to Jansen and Pilipczuk (SODA’ 17) to obtain an approximate solution with O(k^4) vertices when the problem is a Yes-instance, and use Mader’s S-path theorem to hit all obstructions containing exactly one vertex of the approximate solution. Then we exploit the structure of split decompositions of distance-hereditary graphs to reduce the total size. Using Mader’s S-path theorem in the context of kernelization might be of independent interest.
Michael Krivelevich, Long cycles in locally expanding graphs, with applications
We provide sufficient conditions for the existence of long cycles in locally expanding graphs. Time permitting, we will present applications of our conditions and techniques to Ramsey theory, random graphs and positional games.
Igor Razgon, Well quasi-orderability vs. cliquewidth
Well quasi-orderability is an important topic of structural graph theory. The famous result of Robertson and Seymour showing that the class of all graphs is well quasi ordered (WQO) by the graph minors relation inspired researchers to consider other order relations on graphs. One such relation is `induced subgraph’. This relation is easy to show to be non-WQO, however many hereditary graph classes are WQO. Up to some moment all known WQO classes were of bounded cliquewidth and this led researchers to a question whether this situation is true in general (that is whether a class of graphs that is WQO under the induced subgraph relation is of bounded cliquewidth). A wide belief was that it is indeed the case. V.Lozin,V.Zamaraev,and myself have demonstrated the first counterexample: a hereditary class of unbounded cliquewidth which is WQO by the induced subgraph relation. A preliminary version of our result appeared in WG15.
In this talk I will overview the result and state several interesting open problems.
Saket Saurabh, Gregory: The “Tree” of Knowledge
In this talk I will document my association with Gregory via algorithms for
finding trees with certain properties. This will include some old and some
more modern developments in the area.
finding trees with certain properties. This will include some old and some
more modern developments in the area.
Benny Sudakov, Rainbow cycles and trees in properly edge-colored complete graphs
A rainbow subgraph of a properly edge-colored complete graph is a subgraph all of whose edges have different colors. One reason to study such subgraphs arises from the canonical version of Ramsey’s theorem, proved by Erdős and Rado. Another motivation comes from problems in design theory. In this talk we discuss several old conjectures about finding spanning rainbow cycles and trees in properly edge-colored complete
graphs and present some recent progress on these problems.
Joint work with A. Pokrovskiy and in part with N. Alon
Stefan Szeider, Backdoors for Constraint Satisfaction
We will review some recent parameterised complexity results for the Constraint Satisfaction Problem (CSP), considering parameters that arise from strong backdoor sets. A strong backdoor set of a CSP instance is a set of variables with the property that any instantiation of these variables moves the instance into a polynomial-time tractable class. We will focus on tractable classes defined by restricting the involved constraint relations.
Joint work with R. Ganian, S. Gaspers, N. Misra, S. Ordyniak, M.S. Ramanujan, and S. Živný.
Anders Yeo, Perfect Forests in Digraphs
A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs & Combinatorics, 2001) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices.
We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott’s theorem to digraphs in a non-trivial way.