6
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Neal Young
    Mar 31, 2021 at 16:05
  • 1
    $\begingroup$ @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 $\endgroup$
    – delete000
    Apr 1, 2021 at 14:36

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.