15th Scandinavian Symposium and Workshops on Algorithm Theory
June 2224, 2016, Reykjavik, Iceland
Day 1: Wednesday, June 22  

8:40  9:30  Invited Talk: Julia Chuzhoy.
Excluded Grid Theorem: Improved and Simplified.
Session chair: Magnús Halldórsson
One of the key results in Robertson and Seymour’s seminal work on graph minors is the Excluded
Grid Theorem. The theorem states that there is a function f, such that for every positive integer
g, every graph whose treewidth is at least f(g) contains the
(g×g)grid as a minor. This theorem
has found many applications in graph theory and algorithms. An important open question is
establishing tight bounds on f(g) for which the theorem holds. Robertson and Seymour showed
that f(g) ≥ Ω(g^{2}log(g)), and this remains the best current lower bound on f(g). Until recently,
the best upper bound was superexponential in g. In this talk, we will give an overview of a recent
sequence of results, that has lead to the best current upper bound of
f(g) = O(g^{19}polylog(g)).
We will also survey some connections to algorithms for graph routing problems.


9:30  9:40  Break  
Session 1: Approximation and Graphs Session chair: Marcin Pilipczuk 

9:40  10:05  Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding 

10:05  10:30  Approximation Algorithms for NodeWeighted Prizecollecting Steiner Tree problems on Planar Graphs 

10:30  10:55  A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasibipartite Graphs 

10:55  11:15  Coffee Break  
Session 2: Graph Algorithms Session chair: Julia Chuzhoy 

11:15  11:40  A Linear Kernel for Finding Square Roots of Almost Planar Graphs 

11:40  12:05  LinearTime Recognition of Map Graphs with Outerplanar Witness 

12:05  12:30  The pCenter Problem in Tree Networks Revisited 

12:30  14:00  Lunch  
Session 3: Sets Session chair: Rasmus Pagh 

14:00  14:25  A Simple Mergeable Dictionary 

14:25  14:50  Cuckoo Filter: Simplification and Analysis 

14:50  15:15  Randomized Algorithms for Finding a Majority Element 

15:15  15:45  Coffee Break  
Session 4: Strings and Streams Session chair: Nodari Sitchinava 

15:45  16:10  A Framework for Dynamic Parameterized Dictionary Matching 

16:10  16:35  Efficient Summing over Sliding Windows 

16:35  17:00  Lower Bounds for Approximation Schemes for Closest String 

17:00  17:45  Football Break  
17:50  18:20  Business Meeting  
18:20  Reception  
Day 2: Thursday, June 23  
8:40  9:30 
Invited Talk: Dániel Marx.
The Complexity Landscape of FixedParameter Directed Steiner Network Problems.
Session chair: Kazuo Iwama
Given a directed graph G and a list
(s_{1},t_{1}),…,(s_{k},t_{k}) of terminal pairs, the Directed
Steiner Network problem asks for a minimumcost subgraph of G that contains a directed
s_{i} → t_{i} path for every 1 ≤ i ≤ k.
Feldman and Ruhl presented an n^{O(k)} time algorithm for the
problem, which shows that it is polynomialtime solvable for every fixed number k of demands.
There are special cases of the problem that can be solved much more efficiently: for example,
the special case Directed Steiner Tree (when we ask for paths from a root r to terminals
t_{1},…,t_{k}) is known to be fixedparameter
tractable parameterized by the number of terminals,
that is, algorithms with running time of the form f(k)⋅n^{O(1)} exist for the problem. On the
other hand, the special case Strongly Connected Steiner Subgraph (when we ask for a
path from every t_{i} to every other t_{j}) is known to be
W[1]hard parameterized by the number of
terminals, hence it is unlikely to be fixedparameter tractable. In the talk, we survey results on
parameterized algorithms for special cases of Directed Steiner Network, including a recent
complete classification result (joint work with Andreas Feldmann) that systematically explores
the complexity landscape of directed Steiner problems to fully understand which special cases
are FPT or W[1]hard.


9:30  9:40  Break  
Session 5: Parameterized Graph Algorithms Session chair: Dániel Marx 

9:40  10:05  Coloring Graphs having Few Colorings over Path Decompositions 

10:05  10:30  Parameterized Algorithms for Recognizing Monopolar and 2Subcolorable Graphs 

10:30  10:55  On Routing Disjoint Paths in Bounded Treewidth Graphs 

10:55  11:15  Coffee Break  
Session 6: Hard Problems Session chair: Petteri Kaski 

11:15  11:40  Colouring Diamondfree Graphs 

11:40  12:05  Below All Subsets for Some Permutational Counting Problems 

12:05  12:30  Extension Complexity, MSO Logic, and Treewidth 

12:30  13:00  Lunch  
13:30  23:00  Excursion and Conference Dinner
We will tour the Reykjanes peninsula. This includes bubbling geothermal areas, dramatic coastline, lighthouse, and the "bridge between two continents". We end with a conference dinner (from 7:30pm) at the harbor restaurant Vitinn in the village of Sandgerði.


Day 3: Friday, June 24  
8:40  9:30 
Invited Talk: Christos Papadimitriou.
Computation as a Scientific Weltanschauung.
Session chair: Luca Aceto
Computation as a mechanical reality is young – almost exactly seventy years of age – and yet the
spirit of computation can be traced several millennia back. Any moderately advanced civilization
depends on calculation (for inventory, taxation, navigation, land partition, among many others)
– our civilization is the first one that is conscious of this reliance.
Computation has also been central to science for centuries. This is most immediately apparent
in the case of mathematics: the idea of the algorithm as a mathematical object of some significance
was pioneered by Euclid in the 4^{th} century BC, and advanced by Archimedes a century later.
But computation plays an important role in virtually all sciences: natural, life, or social. Implicit
algorithmic processes are present in the great objects of scientific inquiry – the cell, the universe,
the market, the brain – as well as in the models developed by scientists over the centuries for
studying them. This brings about a very recent – merely a few decades old – mode of scientific
inquiry, which is sometime referred to as the lens of computation: When students of computation
revisit central problems in science from the computational viewpoint, often unexpected progress
results. This has happened in statistical physics through the study of phase transitions in terms
of the convergence of Markov chainMonte Carlo algorithms, and in quantum mechanics through
quantum computing.
This talk will focus on three other manifestations of this phenomenon. Almost a decade ago,
ideas and methodologies from computational complexity revealed a subtle conceptual flaw in the
solution concept of Nash equilibrium, which lies at the foundations of modern economic thought.
In the study of evolution, a new understanding of centuryold questions has been achieved through
surprisingly algorithmic ideas. Finally, current work in theoretical neuroscience suggests that the
algorithmic point of view may be invaluable in the central scientific question of our era, namely
understanding how behavior and cognition emerge from the structure and activity of neurons
and synapses.


9:30  9:40  Break  
Session 7: Online Algorithms Session chair: Alan Borodin 

9:40  10:05  Optimal Online Escape Path against a Certificate 

10:05  10:30  Lagrangian Duality based Algorithms in Online EnergyEfficient Scheduling 

10:30  10:55  Online Dominating Set 

10:55  11:15  Coffee Break  
Session 8: Sorting Scheduling and Games Session chair: Páll Melsted 

11:15  11:40  Sorting Under Forbidden Comparisons 

11:40  12:05  A Plane 1.88Spanner for Points in Convex Position 

12:05  12:30  Estimating The Makespan of The TwoValued Restricted Assignment Problem 

12:30  14:00  Lunch  
Session 9: Approximation and Geometry Session chair: Timothy Chan 

14:00  14:25  Total Stability in Stable Matching Games 

14:25  14:50  Approximating the Integral Fréchet Distance 

14:50  15:15  Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts 

15:15  15:45  Coffee Break  
Session 10: Geometry Session chair: David Eppstein 

15:45  16:10  A ClusteringBased Approach to Kinetic Closest Pair 

16:10  16:35  Constrained Geodesic Center of a Simple Polygon 

16:35  17:00  TimeSpace Tradeoffs for Triangulating a Simple Polygon 

17:00  Happy Hour 