3
$\begingroup$

Given an $m\times n$ chess board, we place $p$ $2\times 1$ dominoes on the board so that they don't overlap. How many ways can we place them?

When each square of the board is covered by a domino this is the well-known tiling problem. Is there any research on the case where $p$ is small such that we have to leave some empty squares on the board?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ These are still matchings (just not perfect matchings) of the corresponding graph. They are certainly studied, but less is known in general than for the case of perfect matchings. $\endgroup$
    – Sam Hopkins
    Commented Mar 15, 2023 at 12:06
  • $\begingroup$ There are also called packings. $\endgroup$
    – RobPratt
    Commented Mar 15, 2023 at 20:22

2 Answers 2

Reset to default
9
$\begingroup$

If we sum over all $p$, then we obtain the number of monomer-dimer tilings of an $m\times n$ chessboard. This number is known to be #P-complete and hence very likely computationally intractable. For a reference, see citation [7] of the paper by Yong Kung here.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ That paper by Jerrum shows only that the problem is #P-complete for an arbitrary planar graph, which doesn't automatically imply that the problem is #P-complete when restricted to rectangles. $\endgroup$
    – Timothy Chow
    Commented Mar 15, 2023 at 22:36
  • $\begingroup$ @TimothyChow: well also, at any rate, the original question was about fixing some small $p$ and asking how many matchings use exactly $p$ edges. For $p$ fixed we should be able to write this as a function of $m$ and $n$ which I'm guessing has a rational generating function. $\endgroup$
    – Sam Hopkins
    Commented Mar 15, 2023 at 23:20
  • $\begingroup$ @SamHopkins Good point about fixed $p$. If both $p$ and $m$ are fixed then I can believe that there is a rational generating function, but if only $p$ is fixed then I don't immediately see how to proceed. If you can figure this out then I think it would be worth posting as an answer. $\endgroup$
    – Timothy Chow
    Commented Mar 15, 2023 at 23:36
3
$\begingroup$

If you're hoping for a nice formula, or for a fast algorithm that gives you the number exactly, then you're probably out of luck.

You're asking for the coefficients of the matching polynomial of a grid graph. As mentioned in Richard Stanley's answer, it was shown by Jerrum (Two-Dimensional Monomer-Dimer Systems are Computationally Intractable, J. Stat. Phys. 48 (1987)) that this computational problem is $\mathsf{\#P}$-complete for planar graphs. That doesn't quite prove that the problem is $\mathsf{\#P}$-complete for grid graphs, but it seems unlikely that grid graphs are special enough to admit a fast algorithm.

On the other hand, planar graphs are quite friendly when it comes to fixed-parameter tractability. In particular, if you fix $m$, then $m\times n$ grid graphs have bounded treewidth (in fact, treewidth $m$), and a large class of computational problems on planar graphs with bounded treewidth (including this one) are fixed-parameter tractable. See for example On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, by B. Courcelle, J.A. Makowsky, and U. Rotics.

If you're satisfied with approximate counting, then the news is a bit better. The famous paper by Jerrum and Sinclair on Approximating the permanent gives a FPRAS for this problem (see Corollary 4.4).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .