
We show that any onecounter automaton with $n$ states, if its language is
nonempty, accepts some word of length at most $O(n^2)$. This closes the gap
between the previously known upper bound of $O(n^3)$ and lower bound of
$\Omega(n^2)$. More generally, we prove a tight upper bound on the length of
shortest paths between arbitrary configurations in onecounter transition
systems (weaker bounds have previously appeared in the literature).

We prove that for every class $C$ of graphs with effectively bounded
expansion, given a firstorder sentence $\varphi$ and an $n$element structure
$\mathbb{A}$ whose Gaifman graph belongs to $C$, the question whether $\varphi$
holds in $\mathbb{A}$ can be decided by a family of ACcircuits of size
$f(\varphi)\cdot n^c$ and depth $f(\varphi)+c\log n$, where $f$ is a computable
function and $c$ is a universal constant. This places the modelchecking
problem for classes of bounded expansion in the parameterized circuit
complexity class $paraAC^1$. On the route to our result we prove that the
basic decomposition toolbox for classes of bounded expansion, including
orderings with bounded weak coloring numbers and low treedepth decompositions,
can be computed in $paraAC^1$.

We prove that for every positive integer $k$, there exists an
$\text{MSO}_1$transduction that given a graph of linear cliquewidth at most
$k$ outputs, nondeterministically, some clique decomposition of the graph of
width bounded by a function of $k$. A direct corollary of this result is the
equivalence of the notions of $\text{CMSO}_1$definability and recognizability
on graphs of bounded linear cliquewidth.

In the classic Maximum Weight Independent Set problem we are given a graph
$G$ with a nonnegative weight function on vertices, and the goal is to find an
independent set in $G$ of maximum possible weight. While the problem is NPhard
in general, we give a polynomialtime algorithm working on any $P_6$free
graph, that is, a graph that has no path on $6$ vertices as an induced
subgraph. This improves the polynomialtime algorithm on $P_5$free graphs of
Lokshtanov et al. (SODA 2014), and the quasipolynomialtime algorithm on
$P_6$free graphs of Lokshtanov et al (SODA 2016). The main technical
contribution leading to our main result is enumeration of a polynomialsize
family $\mathcal{F}$ of vertex subsets with the following property: for every
maximal independent set $I$ in the graph, $\mathcal{F}$ contains all maximal
cliques of some minimal chordal completion of $G$ that does not add any edge
incident to a vertex of $I$.

We study the Directed Feedback Vertex Set problem parameterized by the
treewidth of the input graph. We prove that unless the Exponential Time
Hypothesis fails, the problem cannot be solved in time $2^{o(t\log t)}\cdot
n^{\mathcal{O}(1)}$ on general directed graphs, where $t$ is the treewidth of
the underlying undirected graph. This is matched by a dynamic programming
algorithm with running time $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$.
On the other hand, we show that if the input digraph is planar, then the
running time can be improved to $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$.

We propose polynomialtime algorithms that sparsify planar and boundedgenus
graphs while preserving optimal or nearoptimal solutions to Steiner problems.
Our main contribution is a polynomialtime algorithm that, given an unweighted
graph $G$ embedded on a surface of genus $g$ and a designated face $f$ bounded
by a simple cycle of length $k$, uncovers a set $F \subseteq E(G)$ of size
polynomial in $g$ and $k$ that contains an optimal Steiner tree for any set of
terminals that is a subset of the vertices of $f$.
We apply this general theorem to prove that: * given an unweighted graph $G$
embedded on a surface of genus $g$ and a terminal set $S \subseteq V(G)$, one
can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal
Steiner tree $T$ for $S$ and that has size polynomial in $g$ and $E(T)$; * an
analogous result holds for an optimal Steiner forest for a set $S$ of terminal
pairs; * given an unweighted planar graph $G$ and a terminal set $S \subseteq
V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains
an optimal (edge) multiway cut $C$ separating $S$ and that has size polynomial
in $C$.
In the language of parameterized complexity, these results imply the first
polynomial kernels for Steiner Tree and Steiner Forest on planar and
boundedgenus graphs (parameterized by the size of the tree and forest,
respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by
the size of the cutset). Additionally, we obtain a weighted variant of our main
contribution.

There are numerous examples of the socalled square root phenomenon in the
field of parameterized algorithms: many of the most fundamental graph problems,
parameterized by some natural parameter $k$, become significantly simpler when
restricted to planar graphs and in particular the best possible running time is
exponential in $O(\sqrt{k})$ instead of $O(k)$ (modulo standard complexity
assumptions). We consider two classic optimization problems parameterized by
the number of terminals. The Steiner Tree problem asks for a minimumweight
tree connecting a given set of terminals T in an edgeweighted graph. In the
Subset Traveling Salesman problem we are asked to visit all the terminals $T$
by a minimumweight closed walk. We investigate the parameterized complexity of
these problems in planar graphs, where the number $k = T$ of terminals is
regarded as the parameter. Our results are the following: (1) Subset TSP can be
solved in time $2^{O(\sqrt{k} \log k)} \cdot n^{O(1)}$ even on edgeweighted
directed planar graphs. (2) Assuming the ExponentialTime Hypothesis, Steiner
Tree on undirected planar graphs cannot be solved in time $2^{o(k)} \cdot
n^{O(1)}$, even in the unitweight setting. (3) Steiner Tree can be solved in
time $n^{O(\sqrt{k})} \cdot W$ on undirected planar graphs with maximum edge
weight $W$. A direct corollary of the combination of our results for Steiner
Tree is that this problem does not admit a parameterpreserving polynomial
kernel on planar graphs unless ETH fails.

A simple digraph is semicomplete if for any two of its vertices $u$ and $v$,
at least one of the arcs $(u,v)$ and $(v,u)$ is present. We study the
complexity of computing two layout parameters of semicomplete digraphs:
cutwidth and optimal linear arrangement (OLA). We prove that: (1) Both
parameters are $\mathsf{NP}$hard to compute and the known exact and
parameterized algorithms for them have essentially optimal running times,
assuming the Exponential Time Hypothesis; (2) The cutwidth parameter admits a
quadratic Turing kernel, whereas it does not admit any polynomial kernel unless
$\mathsf{NP}\subseteq \mathsf{coNP}/\textrm{poly}$. By contrast, OLA admits a
linear kernel. These results essentially complete the complexity analysis of
computing cutwidth and OLA on semicomplete digraphs. Our techniques can be
also used to analyze the sizes of minimal obstructions for having small
cutwidth under the induced subdigraph relation.

We study nowhere dense classes of graphs, recently introduced by Nesetril and
Ossona de Mendez. Firstly, we provide a new proof for the fact that these
classes are uniformly quasiwide, improving previously known bounds between the
two equivalent notions. Secondly, we give a new combinatorial proof of the
result of Adler and Adler stating that nowhere dense classes of graphs are
stable. In contrast to the original proof, our proof is completely finitistic
and yields explicit bounds for ladder indices of firstorder formulas on
nowhere dense classes of graphs.

A successorinvariant firstorder formula is a formula that has access to an
auxiliary successor relation on a structure's universe, but the model relation
is independent of the particular interpretation of this relation. It is well
known that successorinvariant formulas are more expressive on finite
structures than plain firstorder formulas without a successor relation. This
naturally raises the question whether this increase in expressive power comes
at an extra cost to solve the modelchecking problem, that is, the problem to
decide whether a given structure together with some (and hence every) successor
relation is a model of a given formula. It was shown earlier that adding
successorinvariance to firstorder logic essentially comes at no extra cost
for the modelchecking problem on classes of finite structures whose underlying
Gaifman graph is planar [Engelmann et al., 2012], excludes a fixed minor
[Eickmeyer et al., 2013] or a fixed topological minor [Eickmeyer and
Kawarabayashi, 2016; Kreutzer et al., 2016]. In this work we show that the
modelchecking problem for successorinvariant formulas is fixedparameter
tractable on any class of finite structures whose underlying Gaifman graphs
form a class of bounded expansion. Our result generalises all earlier results
and comes close to the best tractability results on nowhere dense classes of
graphs currently known for plain firstorder logic.

In the Edge Bipartization problem one is given an undirected graph $G$ and an
integer $k$, and the question is whether $k$ edges can be deleted from $G$ so
that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci.,
72(8):13861396, 2006] proposed an algorithm solving this problem in time
$O(2^k m^2)$; today, this algorithm is a textbook example of an application of
the iterative compression technique. Despite extensive progress in the
understanding of the parameterized complexity of graph separation problems in
the recent years, no significant improvement upon this result has been yet
reported.
We present an algorithm for Edge Bipartization that works in time $O(1.977^k
nm)$, which is the first algorithm with the running time dependence on the
parameter better than $2^k$. To this end, we combine the general iterative
compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):13861396,
2006], the technique proposed by Wahlstrom [SODA 2014, 17621781] of using a
polynomialtime solvable relaxation in the form of a Valued Constraint
Satisfaction Problem to guide a boundeddepth branching algorithm, and an
involved Measure & Conquer analysis of the recursion tree.

We introduce the concept of low rankwidth colorings, generalising the notion
of low treedepth colorings introduced by Ne\v{s}et\v{r}il and Ossona de Mendez
in [Grad and classes with bounded expansion I. Decompositions. EJC, 2008]. We
say that a class $\mathcal{C}$ of graphs admits low rankwidth colourings if
there exist functions $N\colon \mathbb{N}\rightarrow\mathbb{N}$ and $Q\colon
\mathbb{N}\rightarrow\mathbb{N}$ such that for all $p\in \mathbb{N}$, every
graph $G\in \mathcal{C}$ can be vertex colored with at most $N(p)$ colors such
that the union of any $i\leq p$ color classes induces a subgraph of rankwidth
at most $Q(i)$.
Graph classes admitting low rankwidth colorings strictly generalize graph
classes admitting low treedepth colorings and graph classes of bounded
rankwidth. We prove that for every graph class $\mathcal{C}$ of bounded
expansion and every positive integer $r$, the class $\{G^r\colon G\in
\mathcal{C}\}$ of $r$th powers of graphs from $\mathcal{C}$, as well as the
classes of unit interval graphs and bipartite permutation graphs admit low
rankwidth colorings. All of these classes have unbounded rankwidth and do not
admit low treedepth colorings. We also show that the classes of interval
graphs and permutation graphs do not admit low rankwidth colorings. As
interesting side properties, we prove that every graph class admitting low
rankwidth colorings has the Erd\H{o}sHajnal property and is $\chi$bounded.

In the multicoloring problem, also known as ($a$:$b$)coloring or $b$fold
coloring, we are given a graph G and a set of $a$ colors, and the task is to
assign a subset of $b$ colors to each vertex of G so that adjacent vertices
receive disjoint color subsets. This natural generalization of the classic
coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to
the Kneser graph $KG_{a,b}$, and gives relaxations approaching the fractional
chromatic number.
We study the complexity of determining whether a graph has an
($a$:$b$)coloring. Our main result is that this problem does not admit an
algorithm with running time $f(b)\cdot 2^{o(\log b)\cdot n}$, for any
computable $f(b)$, unless the Exponential Time Hypothesis (ETH) fails. A
$(b+1)^n\cdot \text{poly}(n)$time algorithm due to Nederlof [2008] shows that
this is tight. A direct corollary of our result is that the graph homomorphism
problem does not admit a $2^{O(n+h)}$ algorithm unless ETH fails, even if the
target graph is required to be a Kneser graph. This refines the understanding
given by the recent lower bound of Cygan et al. [SODA 2016].
The crucial ingredient in our hardness reduction is the usage of detecting
matrices of Lindstr\"om [Canad. Math. Bull., 1965], which is a combinatorial
tool that, to the best of our knowledge, has not yet been used for proving
complexity lower bounds. As a side result, we prove that the running time of
the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for
the rmonomial detection problem are optimal under ETH.

Cutwidth is one of the classic layout parameters for graphs. It measures how
well one can order the vertices of a graph in a linear manner, so that the
maximum number of edges between any prefix and its complement suffix is
minimized. As graphs of cutwidth at most $k$ are closed under taking
immersions, the results of Robertson and Seymour imply that there is a finite
list of minimal immersion obstructions for admitting a cut layout of width at
most $k$. We prove that every minimal immersion obstruction for cutwidth at
most $k$ has size at most $2^{O(k^3\log k)}$.
As an interesting algorithmic byproduct, we design a new fixedparameter
algorithm for computing the cutwidth of a graph that runs in time $2^{O(k^2\log
k)}\cdot n$, where $k$ is the optimum width and $n$ is the number of vertices.
While being slower by a $\log k$factor in the exponent than the fastest known
algorithm, given by Thilikos, Bodlaender, and Serna in [Cutwidth I: A linear
time fixed parameter algorithm, J. Algorithms, 56(1):124, 2005] and [Cutwidth
II: Algorithms for partial $w$trees of bounded degree, J. Algorithms,
56(1):2549, 2005], our algorithm has the advantage of being simpler and
selfcontained; arguably, it explains better the combinatorics of optimumwidth
layouts.

The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves
the following problem in linear fixedparameter time: given a tree
decomposition of a graph of (possibly suboptimal) width $k$, compute an
optimumwidth tree decomposition of the graph. In this work, we prove that this
problem can also be solved in MSO in the following sense: for every positive
integer $k$, there is an MSO transduction from tree decompositions of width $k$
to tree decompositions of optimum width. Together with our recent results [LICS
2016], this implies that for every $k$ there exists an MSO transduction which
inputs a graph of treewidth $k$, and nondeterministically outputs its tree
decomposition of optimum width. We also show that MSO transductions can be
implemented in linear fixedparameter time, which enables us to derive the
algorithmic result of Bodlaender and Kloks as a corollary of our main result.

We prove that whenever $G$ is a graph from a nowhere dense graph class
$\mathcal{C}$, and $A$ is a subset of vertices of $G$, then the number of
subsets of $A$ that are realized as intersections of $A$ with $r$neighborhoods
of vertices of $G$ is at most $f(r,\epsilon)\cdot A^{1+\epsilon}$, where $r$
is any positive integer, $\epsilon$ is any positive real, and $f$ is a function
that depends only on the class $\mathcal{C}$. This yields a characterization of
nowhere dense classes of graphs in terms of neighborhood complexity, which
answers a question posed by Reidl et al. As an algorithmic application of the
above result, we show that for every fixed $r$, the parameterized Distance$r$
Dominating Set problem admits an almost linear kernel on any nowhere dense
graph class. This proves a conjecture posed by Drange et al., and shows that
the limit of parameterized tractability of Distance$r$ Dominating Set on
subgraphclosed graph classes lies exactly on the boundary between nowhere
denseness and somewhere denseness.

Consider the Maximum Weight Independent Set problem for rectangles: given a
family of weighted axisparallel rectangles in the plane, find a maximumweight
subset of nonoverlapping rectangles. The problem is notoriously hard both in
the approximation and in the parameterized setting. The best known
polynomialtime approximation algorithms achieve superconstant approximation
ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and HarPeled, Discrete &
Comp. Geometry 2012], even though there is a $(1+\epsilon)$approximation
running in quasipolynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and
Ene, FOCS 2016]. When parameterized by the target size of the solution, the
problem is $\mathsf{W}[1]$hard even in the unweighted setting [Marx, FOCS
2007].
To achieve tractability, we study the following shrinking model: one is
allowed to shrink each input rectangle by a multiplicative factor $1\delta$
for some fixed $\delta>0$, but the performance is still compared against the
optimal solution for the original, nonshrunk instance. We prove that in this
regime, the problem admits an EPTAS with running time $f(\epsilon,\delta)\cdot
n^{\mathcal{O}(1)}$, and an FPT algorithm with running time $f(k,\delta)\cdot
n^{\mathcal{O}(1)}$, in the setting where a maximumweight solution of size at
most $k$ is to be computed. This improves and significantly simplifies a PTAS
given earlier for this problem [Adamaszek et al., APPROX 2015], and provides
the first parameterized results for the shrinking model. Furthermore, we
explore kernelization in the shrinking model, by giving efficient kernelization
procedures for several variants of the problem when the input rectangles are
squares.

A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not
contained in $S$ has a neighbor in $S$. A dominating set $S$ is a connected
dominating set if the subgraph $G[S]$ induced by $S$ is connected. A connected
dominating set $S$ is a minimal connected dominating set if no proper subset of
$S$ is also a connected dominating set. We prove that there exists a constant
$\varepsilon > 10^{50}$ such that every graph $G$ on $n$ vertices has at most
$O(2^{(1\varepsilon)n})$ minimal connected dominating sets. For the same
$\varepsilon$ we also give an algorithm with running time
$2^{(1\varepsilon)n}\cdot n^{O(1)}$ to enumerate all minimal connected
dominating sets in an input graph $G$.

Strip packing is a classical packing problem, where the goal is to pack a set
of rectangular objects into a strip of a given width, while minimizing the
total height of the packing. The problem has multiple applications, e.g. in
scheduling and stockcutting, and has been studied extensively.
When the dimensions of objects are allowed to be exponential in the total
input size, it is known that the problem cannot be approximated within a factor
better than $3/2$, unless $\mathrm{P}=\mathrm{NP}$. However, there was no
corresponding lower bound for polynomially bounded input data. In fact,
Nadiradze and Wiese [SODA 2016] have recently proposed a $(1.4 + \epsilon)$
approximation algorithm for this variant, thus showing that strip packing with
polynomially bounded data can be approximated better than when exponentially
large values in the input data are allowed. Their result has subsequently been
improved to a $(4/3 + \epsilon)$ approximation by two independent research
groups [FSTTCS 2016, arXiv:1610.04430]. This raises a question whether strip
packing with polynomially bounded input data admits a quasipolynomial time
approximation scheme, as is the case for related twodimensional packing
problems like maximum independent set of rectangles or twodimensional
knapsack.
In this paper we answer this question in negative by proving that it is
NPhard to approximate strip packing within a factor better than $12/11$, even
when admitting only polynomially bounded input data. In particular, this shows
that the strip packing problem admits no quasipolynomial time approximation
scheme, unless $\mathrm{NP} \subseteq \mathrm{DTIME}(2^{\mathrm{polylog}(n)})$.

Suppose $\mathcal{F}$ is a finite family of graphs. We consider the following
metaproblem, called $\mathcal{F}$Immersion Deletion: given a graph $G$ and
integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result
in a graph that does not contain any graph from $\mathcal{F}$ as an immersion.
This problem is a close relative of the $\mathcal{F}$Minor Deletion problem
studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to
remove all minor models of graphs from $\mathcal{F}$.
We prove that whenever all graphs from $\mathcal{F}$ are connected and at
least one graph of $\mathcal{F}$ is planar and subcubic, then the
$\mathcal{F}$Immersion Deletion problem admits: a constantfactor
approximation algorithm running in time $O(m^3 \cdot n^3 \cdot \log m)$; a
linear kernel that can be computed in time $O(m^4 \cdot n^3 \cdot \log m)$; and
a $O(2^{O(k)} + m^4 \cdot n^3 \cdot \log m)$time fixedparameter algorithm,
where $n,m$ count the vertices and edges of the input graph.
These results mirror the findings of Fomin et al. [FOCS 2012], who obtained a
similar set of algorithmic results for $\mathcal{F}$Minor Deletion, under the
assumption that at least one graph from $\mathcal{F}$ is planar. An important
difference is that we are able to obtain a linear kernel for
$\mathcal{F}$Immersion Deletion, while the exponent of the kernel of Fomin et
al. for $\mathcal{F}$Minor Deletion depends heavily on the family
$\mathcal{F}$. In fact, this dependence is unavoidable under plausible
complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This
reveals that the kernelization complexity of $\mathcal{F}$Immersion Deletion
is quite different than that of $\mathcal{F}$Minor Deletion.

We introduce a new technique for designing fixedparameter algorithms for cut
problems, namely randomized contractions. We apply our framework to obtain the
first FPT algorithm for the Unique Label Cover problem and new FPT algorithms
with exponential speed up for the Steiner Cut and Node Multiway CutUncut
problems. More precisely, we show the following:
 We prove that the parameterized version of the Unique Label Cover problem,
which is the base of the Unique Games Conjecture, can be solved in 2^{O(k^2\log
\Sigma)}n^4\log n deterministic time (even in the stronger, vertexdeletion
variant) where k is the number of unsatisfied edges and \Sigma is the size of
the alphabet. As a consequence, we show that one can in polynomial time solve
instances of Unique Games where the number of edges allowed not to be satisfied
is upper bounded by O(\sqrt{\log n}) to optimality, which improves over the
trivial O(1) upper bound.
 We prove that the Steiner Cut problem can be solved in 2^{O(k^2\log
k)}n^4\log n deterministic time and \tilde{O}(2^{O(k^2\log k)}n^2) randomized
time where k is the size of the cutset. This result improves the double
exponential running time of the recent work of Kawarabayashi and Thorup
(FOCS'11).
 We show how to combine considering `cut' and `uncut' constraints at the
same time. More precisely, we define a robust problem Node Multiway CutUncut
that can serve as an abstraction of introducing uncut constraints, and show
that it admits an algorithm running in 2^{O(k^2\log k)}n^4\log n deterministic
time where k is the size of the cutset. To the best of our knowledge, the only
known way of tackling uncut constraints was via the approach of Marx,
O'Sullivan and Razgon (STACS'10), which yields algorithms with double
exponential running time.
An interesting aspect of our technique is that, unlike important separators,
it can handle real weights.

The generalised colouring numbers $\mathrm{adm}_r(G)$, $\mathrm{col}_r(G)$,
and $\mathrm{wcol}_r(G)$ were introduced by Kierstead and Yang as
generalisations of the usual colouring number, also known as the degeneracy of
a graph, and have since then found important applications in the theory of
bounded expansion and nowhere dense classes of graphs, introduced by
Ne\v{s}et\v{r}il and Ossona de Mendez. In this paper, we study the relation of
the colouring numbers with two other measures that characterise nowhere dense
classes of graphs, namely with uniform quasiwideness, studied first by Dawar
et al. in the context of preservation theorems for firstorder logic, and with
the splitter game, introduced by Grohe et al. We show that every graph
excluding a fixed topological minor admits a universal order, that is, one
order witnessing that the colouring numbers are small for every value of $r$.
Finally, we use our construction of such orders to give a new proof of a result
of Eickmeyer and Kawarabayashi, showing that the modelchecking problem for
successorinvariant firstorder formulas is fixedparameter tractable on
classes of graphs with excluded topological minors.

Dynamic programming on path and tree decompositions of graphs is a technique
that is ubiquitous in the field of parameterized and exponentialtime
algorithms. However, one of its drawbacks is that the space usage is
exponential in the decomposition's width. Following the work of Allender et al.
[Theory of Computing, '14], we investigate whether this space complexity
explosion is unavoidable. Using the idea of reparameterization of Cai and
Juedes [J. Comput. Syst. Sci., '03], we prove that the question is closely
related to a conjecture that the Longest Common Subsequence problem
parameterized by the number of input strings does not admit an algorithm that
simultaneously uses XP time and FPT space. Moreover, we complete the complexity
landscape sketched for pathwidth and treewidth by Allender et al. by
considering the parameter treedepth. We prove that computations on treedepth
decompositions correspond to a model of nondeterministic machines that work in
polynomial time and logarithmic space, with access to an auxiliary stack of
maximum height equal to the decomposition's depth. Together with the results of
Allender et al., this describes a hierarchy of complexity classes for
polynomialtime nondeterministic machines with different restrictions on the
access to working space, which mirrors the classic relations between treewidth,
pathwidth, and treedepth.

We prove a conjecture of Courcelle, which states that a graph property is
definable in MSO with modular counting predicates on graphs of constant
treewidth if, and only if it is recognizable in the following sense:
constantwidth tree decompositions of graphs satisfying the property can be
recognized by tree automata. While the forward implication is a classic fact
known as Courcelle's theorem, the converse direction remained open

We prove the following theorem. Given a planar graph $G$ and an integer $k$,
it is possible in polynomial time to randomly sample a subset $A$ of vertices
of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of
treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph
$H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole
vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot
n^{\mathcal{O}(1)})^{1}$, where $n$ is the number of vertices of $G$.
Together with standard dynamic programming techniques for graphs of bounded
treewidth, this result gives a versatile technique for obtaining (randomized)
subexponential parameterized algorithms for problems on planar graphs, usually
with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)}
n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as
searching for a small, connected pattern with a prescribed property in a large
host graph, examples of such problems include Directed $k$Path, Weighted
$k$Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up
to this point, it was open whether these problems can be solved in
subexponential parameterized time on planar graphs, because they are not
amenable to the classic technique of bidimensionality. Furthermore, all our
results hold in fact on any class of graphs that exclude a fixed apex graph as
a minor, in particular on graphs embeddable in any fixed surface.