CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Discrete algorithms II
Org: Marcin Pilipczuk (University of Warsaw, Poland)

Sparsity and algorithms  [PDF]

Many algorithmically hard graph problems become tractable when the class of inputs is restricted sparse graphs, such as graphs of bounded treewidth, graphs of bounded degree or planar graphs. To study sparse graphs and algorithms on them in a more general and unified setting, Nešetřil and Ossona de Mendez introduced graph classes of bounded expansion and nowhere dense graph classes, which generalise all of the previously mentioned notions (and many more). We will review the basic notions of this general sparsity theory and give an overview of some of the most important algorithmic results.

Polynomial Planar Directed Grid Theorem  [PDF]

The grid theorem (Robertson, Seymour 1986) is a central results in the study of graph minors. The relation between treewidth and grid minors is particularly tight for planar graphs. The grid theorem for directed graphs was proved in 2015 by Kawarabayashi and Kreutzer but the bounds is very big.

We establish a polynomial bound for the directed grid theorem on planar digraphs. Additionally, we also give ``treewidth sparsifier'' for directed graphs, which has been already considered in undirected graphs. This result allows us to obtain an Eulerian subgraph of bounded degree in $D$ that still has high directed treewidth.

SÁNDOR KISFALUDI-BAK, Eindhoven University of Technology
ETH-tight exact algorithm for Euclidean TSP  [PDF]

We study exact algorithms for the Euclidean traveling salesman problem (Euclidean TSP) in $\mathbb{R}^d$. In the early 1990s algorithms with $n^{O(\sqrt{n})}$ running time were presented for the planar case, and some years later an algorithm with $n^{O(n^{1-1/d})}$ running time was presented for any fixed $d\geq 2$. A recent lower bound states that the problem admits no $2^{O(n^{1-1/d-\varepsilon})}$ algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a $2^{O(n^{1-1/d})}$ algorithm for any fixed $d\geq 2$, and by showing that a $2^{o(n^{1-1/d})}$ algorithm does not exist unless ETH fails.

JESPER NEDERLOF, Eindhoven University of Technology
Towards Faster Exponential Time Algorithms for Subset Sum  [PDF]

The Subset Sum problem asks whether a given set of $n$ positive integers contains a subset of elements that sum up to a given target $t$. Horowitz and Sahni [J. ACM 1974] gave an algorithm for this problem that uses $O^*(2^{n/2})$ time and space. Two natural questions arise. First, can we improve the running time to $O^*(2^{(0.5-\delta)n})$ time for some constant $\delta>0$? Second, is exponential space required to improve over the trivial $O^*(2^n)$ time algorithm: Is there a $O^*(2^{(1-\delta)n})$ time algorithm using space polynomial bounded in the input size?

In this talk we discuss the partial progress on both problems.

MARCIN PILIPCZUK, University of Warsaw
On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs  [PDF]

The "square root phenomenon" observes that many fundamental graph problems become significantly simpler when restricted to planar graphs and the best possible running time is exponential in $\mathcal{O}(\sqrt{k})$ instead of $\mathcal{O}(k)$. We consider two classic optimization problems parameterized by the number $k$ of terminals: Steiner Tree and Subset TSP. We show that Subset TSP can be solved in time $2^{\mathcal{O}(\sqrt{k}\log k)}\cdot n^{\mathcal{O}(1)}$ even on edge-weighted directed planar graphs, while assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs cannot be solved in time $2^{o(k)}\cdot n^{\mathcal{O}(1)}$, even in the unit-weight setting. Joint work with Dániel Marx and Michał Pilipczuk.