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.

Improve this question
$\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
    Apr 21 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
    Apr 24 at 2:58

0

Reset to default

Your Answer

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