# What are the fastest known parameterized algorithms for Grid Tiling?

Let $$k$$ and $$n$$ denote positive integers.

In the $$k$$-GridTiling problem, for every pair of indices $$(i,j)\in \{1, \dots, k\}^2$$ we get a subset $$S_{ij}\subseteq \{1, \dots, n\}^2$$ of pairs of the first $$n$$ consecutive positive integers. We are tasked with determining if it is possible to select a pair $$p_{ij}\in S_{ij}$$ from each subset, such that

• for any fixed $$i$$, the second coordinates of $$p_{ij}$$ pairs are the same for all $$j$$, and
• for any fixed $$j$$, the first coordinates of the $$p_{ij}$$ pairs are the same for all $$i$$.

In the $$k$$-IncreasingGridTiling problem, we are given the same input, and now tasked with determining if it is possible to select a pair $$p_{ij}\in S_{ij}$$ from each subset, such that

• for any fixed $$i$$, the second coordinates of $$p_{i1}, \dots, p_{ik}$$ are non-decreasing, and
• for any fixed $$j$$, the first coordinates of $$p_{1j}, \dots, p_{kj}$$ are non-decreasing.

Question: What are the fastest known algorithms for $$k$$-GridTiling and $$k$$-IncreasingGridTiling, in terms of the dependence on $$k$$?

Additional Context: These problems are often used as a source of conditional hardness for the parameterized complexity of problems on planar graphs. There is a reduction from $$k$$-Clique on $$n$$ vertices to $$k$$-GridTiling on a universe of size $$n$$, and from $$k$$-GridTiling on a universe of size $$n$$ to $$4k$$-IncreasingGridTiling with a universe of size $$O(kn^2)$$, so these problems are both W[1]-hard.

• How fine-grained are you looking? It seems that $n^{O(k)}$ is obvious and by the reduction from clique you mentioned you cannot do better than that. Apr 21 at 21:04
• This question cares about the exact asymptotic time complexity of the problems. Of course I'm interested in the exact constant in the exponent (the smallest $c$ such that the problem can be solved in $n^{ck+o(k)}$ time), since, as you noted, from the context provided it's obvious that known algorithms for this problem take $n^{\Omega(k)}$ time. Apr 24 at 2:58