<p>Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in <span class="math-container">$\#P$</span> and remain hard for grid graphs?</p>
<p>Since there seem to be multiple definitions of grid graphs in the literature, let us specify the following families:</p>
<ol>
<li><em>Grid</em>: a finite node-induced subgraph of the infinite two-dimensional integer grid.</li>
<li><em>Solid grid</em>: a grid graph all of whose bounded faces have area one, i.e., a grid graph with no &quot;holes&quot;; see [1].</li>
<li><em>Rectangular grid</em>: the Cartesian product of <span class="math-container">$P_n \square P_m$</span>. Special case is the <em>square grid</em> with <span class="math-container">$n=m$</span>.</li>
<li><em>Periodic rectangular grid</em>: the 4-regular graph that results from the Cartesian product <span class="math-container">$C_n \square C_m$</span>. Special case is the <em>periodic square grid</em> with <span class="math-container">$n=m$</span>.</li>
</ol>
<p>For problems defined on families 3 and 4, suppose that the input is the numbers <span class="math-container">$n$</span> and <span class="math-container">$m$</span> in unary. My question concerns all 4 families above, but I'd be particularly interested in any <span class="math-container">$\#P$</span>-hardness proofs for the more restricted families, especially the periodic square grid.</p>
<h2>Comments:</h2>
<p>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 &quot;there are too few inputs&quot;, which I guess means only a single instance for each <span class="math-container">$n$</span> and <span class="math-container">$m$</span>. Are there any by now common methods / reductions to deduce complexity for such problems with &quot;too few inputs&quot;?</p>
<p>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?</p>
<p>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?</p>
<h2>References</h2>
<p>[1] W. Lenhart and C. Umans,  &quot;Hamiltonian Cycles in Solid Grid Graphs,&quot; Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97). IEEE Computer Society, USA, pp. 496.</p>
<p>[2] Welsh, D. (1993). Complexity: Knots, Colourings and Countings (London Mathematical Society Lecture Note Series), Cambridge University Press, pp. 17.</p>
<p>[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</p>

CC BY-SA 4.0
2021-03-31T16:05:36.020Z
Regarding your comment (a), note that no sparse language is NP-complete or co-NP complete unless P=NP ([wikipedia](https://en.wikipedia.org/wiki/Sparse_language)), 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).
Neal Young
CC BY-SA 4.0
2021-04-01T14:36:43.127Z
@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. https://arxiv.org/abs/0905.2419
delete000
<cc.complexity-theory><complexity-classes><counting-complexity>
Counting on grid graphs
delete000
# Counting on grid graphs

(Asked by: username_0 on 2020-08-07)

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.

## Comments:

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

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity

> **Comments:**
> **username_1**: Regarding your comment (a), note that no sparse language is NP-complete or co-NP complete unless P=NP ([wikipedia](https://en.wikipedia.org/wiki/Sparse_language)), 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).  
> **username_0**: @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. https://arxiv.org/abs/0905.2419  

---

## 0 answers

