# Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $$\#P$$ and remain hard for grid graphs?

Since there seem to be multiple definitions of grid graphs in the literature, let us specify the following families:

1. Grid: a finite node-induced subgraph of the infinite two-dimensional integer grid.
2. Solid grid: a grid graph all of whose bounded faces have area one, i.e., a grid graph with no "holes"; see [1].
3. Rectangular grid: the Cartesian product of $$P_n \square P_m$$. Special case is the square grid with $$n=m$$.
4. Periodic rectangular grid: the 4-regular graph that results from the Cartesian product $$C_n \square C_m$$. Special case is the periodic square grid with $$n=m$$.

For problems defined on families 3 and 4, suppose that the input is the numbers $$n$$ and $$m$$ in unary. My question concerns all 4 families above, but I'd be particularly interested in any $$\#P$$-hardness proofs for the more restricted families, especially the periodic square grid.

a) Welsh [2] states that problems defined on restricted families such as 3 and 4 can be difficult to treat from a complexity standpoint, because "there are too few inputs", which I guess means only a single instance for each $$n$$ and $$m$$. Are there any by now common methods / reductions to deduce complexity for such problems with "too few inputs"?

b) Ref [3] shows that counting self-avoiding walks in family 1 is #P-complete. Are there any known results for the more restricted families?

c) Ref [1] shows that it is easy to find Hamiltonian cycles in family 2. Does this imply anything about the hardness of counting Hamiltonian cycles?

## References

[1] W. Lenhart and C. Umans, "Hamiltonian Cycles in Solid Grid Graphs," Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97). IEEE Computer Society, USA, pp. 496.

[2] Welsh, D. (1993). Complexity: Knots, Colourings and Countings (London Mathematical Society Lecture Note Series), Cambridge University Press, pp. 17.

[3] Maciej Liśkiewicz, Mitsunori Ogihara, Seinosuke Toda, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes, Theoretical Computer Science, Volume 304, Issues 1–3, 2003, Pages 129-156

• Regarding your comment (a), note that no sparse language is NP-complete or co-NP complete unless P=NP (wikipedia), and every sparse language is in P/POLY. So problems on graphs in your classes 3 and 4 (with n and m in unary) are going to be hard to classify (other than possibly showing they are in P). Mar 31, 2021 at 16:05
• @NealYoung Thanks, I'll read up on Mahaney's thm. So if I understand correctly, I could require instead that $n$ and $m$ are given in binary, but in that case the problem would not be #P anymore. I think the comment in last paragraph on page 5 of this paper describes a similar situation for a decision problem. arxiv.org/abs/0905.2419 Apr 1, 2021 at 14:36