1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Apr 21, 2023 at 21:04
  • $\begingroup$ 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. $\endgroup$
    – Naysh
    Commented Apr 24, 2023 at 2:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.