SWAT 2016

15th Scandinavian Symposium and Workshops on Algorithm Theory
June 22-24, 2016, Reykjavik, Iceland

Conference Program

All talks are in room V102, ground floor, at Reykjavik University.

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) ≥ Ω(g2log(g)), and this remains the best current lower bound on f(g). Until recently, the best upper bound was super-exponential 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(g19polylog(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
Zachary Friggstad, Mohsen Rezapour and Mohammad Salavatipour
10:05 - 10:30 Approximation Algorithms for Node-Weighted Prize-collecting Steiner Tree problems on Planar Graphs
Mateusz Lewandowski, Jarosław Byrka and Carsten Moldenhauer
10:30 - 10:55 A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
Zachary Friggstad, Jochen Koenemann and Mohammad Shadravan
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
Petr Golovach, Dieter Kratsch, Daniel Paulusma and Anthony Stewart
11:40 - 12:05 Linear-Time Recognition of Map Graphs with Outerplanar Witness
Matthias Mnich, Ignaz Rutter and Jens M. Schmidt
12:05 - 12:30 The p-Center Problem in Tree Networks Revisited
Aritra Banik, Binay Bhattacharya, Sandip Das, Tsunehiko Kameda and Zhao Song
12:30 - 14:00 Lunch
Session 3: Sets
Session chair: Rasmus Pagh
14:00 - 14:25 A Simple Mergeable Dictionary
Adam Karczmarz
14:25 - 14:50 Cuckoo Filter: Simplification and Analysis
David Eppstein
14:50 - 15:15 Randomized Algorithms for Finding a Majority Element
Pawel Gawrychowski, Jukka Suomela and Przemysław Uznański
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
Arnab Ganguly, Wing-Kai Hon and Rahul Shah
16:10 - 16:35 Efficient Summing over Sliding Windows
Ran Ben Bassat, Gil Einziger, Roy Friedman and Yaron Kassner
16:35 - 17:00 Lower Bounds for Approximation Schemes for Closest String
Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh
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 Fixed-Parameter Directed Steiner Network Problems.
Session chair: Kazuo Iwama
Given a directed graph G and a list (s1,t1),…,(sk,tk) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G that contains a directed si → ti path for every 1 ≤ i ≤ k. Feldman and Ruhl presented an nO(k) time algorithm for the problem, which shows that it is polynomial-time 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 t1,…,tk) is known to be fixed-parameter tractable parameterized by the number of terminals, that is, algorithms with running time of the form f(k)⋅nO(1) exist for the problem. On the other hand, the special case Strongly Connected Steiner Subgraph (when we ask for a path from every ti to every other tj) is known to be W[1]-hard parameterized by the number of terminals, hence it is unlikely to be fixed-parameter 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
Andreas Björklund
10:05 - 10:30 Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen
10:30 - 10:55 On Routing Disjoint Paths in Bounded Treewidth Graphs
Alina Ene, Matthias Mnich, Marcin Pilipczuk and Andrej Risteski
10:55 - 11:15 Coffee Break
Session 6: Hard Problems
Session chair: Petteri Kaski
11:15 - 11:40 Colouring Diamond-free Graphs
Konrad Kazimierz Dabrowski, François Dross and Daniel Paulusma
11:40 - 12:05 Below All Subsets for Some Permutational Counting Problems
Andreas Björklund
12:05 - 12:30 Extension Complexity, MSO Logic, and Treewidth
Petr Kolman, Martin Koutecky and Hans Raj Tiwary
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 4th 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 chain-Monte 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 century-old 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
Elmar Langetepe and David Kübel
10:05 - 10:30 Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling
Kim Thang Nguyen
10:30 - 10:55 Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene Favrholdt, Michal Kotrbčík and Kim S. Larsen
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
Indranil Banerjee and Dana Richards
11:40 - 12:05 A Plane 1.88-Spanner for Points in Convex Position
Ahmad Biniaz, Anil Maheshwari, Michiel Smid, Prosenjit Bose, Mahdi Amani and Jean-Lou De Carufel
12:05 - 12:30 Estimating The Makespan of The Two-Valued Restricted Assignment Problem
Klaus Jansen, Kati Land and Marten Maack
12:30 - 14:00 Lunch
Session 9: Approximation and Geometry
Session chair: Timothy Chan
14:00 - 14:25 Total Stability in Stable Matching Games
Sushmita Gupta, Kazuo Iwama and Shuichi Miyazaki
14:25 - 14:50 Approximating the Integral Fréchet Distance
Christian Scheffer, Jorg Sack and Anil Maheshwari
14:50 - 15:15 Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts
Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari and Michiel Smid
15:15 - 15:45 Coffee Break
Session 10: Geometry
Session chair: David Eppstein
15:45 - 16:10 A Clustering-Based Approach to Kinetic Closest Pair
Timothy M. Chan and Zahed Rahmati
16:10 - 16:35 Constrained Geodesic Center of a Simple Polygon
Eunjin Oh, Wanbin Son and Hee-Kap Ahn
16:35 - 17:00 Time-Space Trade-offs for Triangulating a Simple Polygon
Boris Aronov, Simon Pratt, Matias Korman, André van Renssen and Marcel Roeloffzen
17:00 Happy Hour