<p>Let <span class="math-container">$k$</span> and <span class="math-container">$n$</span> denote positive integers.</p>
<p>In the <span class="math-container">$k$</span>-GridTiling problem, for every pair of indices <span class="math-container">$(i,j)\in \{1, \dots, k\}^2$</span> we get a subset <span class="math-container">$S_{ij}\subseteq \{1, \dots, n\}^2$</span>  of pairs of the first <span class="math-container">$n$</span> consecutive positive integers. We are tasked with determining if it is possible to select a pair <span class="math-container">$p_{ij}\in S_{ij}$</span> from each subset, such that</p>
<ul>
<li>for any fixed <span class="math-container">$i$</span>, the second coordinates of <span class="math-container">$p_{ij}$</span> pairs are the same for all <span class="math-container">$j$</span>, and</li>
<li>for any fixed <span class="math-container">$j$</span>, the first coordinates of the <span class="math-container">$p_{ij}$</span> pairs are the same for all <span class="math-container">$i$</span>.</li>
</ul>
<p>In the <span class="math-container">$k$</span>-IncreasingGridTiling problem, we are given the same input, and now tasked with determining if it is possible to select a pair <span class="math-container">$p_{ij}\in S_{ij}$</span> from each subset, such that</p>
<ul>
<li>for any fixed <span class="math-container">$i$</span>, the second coordinates of <span class="math-container">$p_{i1}, \dots, p_{ik}$</span> are non-decreasing, and</li>
<li>for any fixed <span class="math-container">$j$</span>, the first coordinates of <span class="math-container">$p_{1j}, \dots, p_{kj}$</span> are non-decreasing.</li>
</ul>
<p><strong>Question:</strong> What are the fastest known algorithms for <span class="math-container">$k$</span>-GridTiling and <span class="math-container">$k$</span>-IncreasingGridTiling, in terms of the dependence on <span class="math-container">$k$</span>?</p>
<p><strong>Additional Context:</strong> 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 <span class="math-container">$k$</span>-Clique on <span class="math-container">$n$</span> vertices to <span class="math-container">$k$</span>-GridTiling on a universe of size <span class="math-container">$n$</span>, and from <span class="math-container">$k$</span>-GridTiling on a universe of size <span class="math-container">$n$</span> to <span class="math-container">$4k$</span>-IncreasingGridTiling with a universe of size <span class="math-container">$O(kn^2)$</span>, so these problems are both W[1]-hard.</p>

CC BY-SA 4.0
2023-04-21T21:04:03.590Z
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.
Laakeri
CC BY-SA 4.0
2023-04-24T02:58:32.773Z
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.
Naysh
<ds.algorithms><graph-algorithms><co.combinatorics><time-complexity><parameterized-complexity>
What are the fastest known parameterized algorithms for Grid Tiling?
Naysh
# What are the fastest known parameterized algorithms for Grid Tiling?

(Asked by: username_0 on 2023-04-21)

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.

**Tags:** ds.algorithms, graph-algorithms, co.combinatorics, time-complexity, parameterized-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  

---

## 0 answers

