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

$\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 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 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.