The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes Export

@article{citeulike:2175802, abstract = {Valiant (SIAM J. Comput. 8 (1979) 410-421) showed that the problem of computing the number of simple s-t paths in graphs is \#P-complete both in the case of directed graphs and in the case of undirected graphs. Welsh (Complexity: Knots, Colourings and Counting, Cambridge University Press, Cambridge, 1993, p. 17) asked whether the problem of computing the number of self-avoiding walks of a given length in the complete two-dimensional grid is complete for \#P1, the tally-version of \#P. This paper offers a partial answer to the question of Welsh: it is \#P-complete to compute the number of self-avoiding walks of a given length in a subgraph of a two-dimensional grid. Several variations of the problem are also studied and shown to be \#P-complete. This paper also studies the problem of computing the number of self-avoiding walks in a subgraph of a hypercube. Similar completeness results are shown for the problem. By scaling the computation time to exponential, it is shown that computing the number of self-avoiding walks in hypercubes is a complete problem for \#EXP in the case when a subgraph of a hypercube is specified by its dimension and a boolean circuit that accepts the nodes. Finally, this paper studies the complexity of testing whether a given word over the four-letter alphabet {U,D,L,R} represents a self-avoiding walk in a two-dimensional grid. A linear-space lower bound is shown for nondeterministic Turing machines with a 1-way input head to make this test.}, author = {Liskiewicz, Maciej and Ogihara, Mitsunori and Toda, Seinosuke}, citeulike-article-id = {2175802}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/S0304-3975(03)00080-X}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V1G-47YPXGG-1/2/667fdbc7560bfce17f4e123fcf5700fc}, comment = {* Counting SAW's is hard}, day = {28}, doi = {10.1016/S0304-3975(03)00080-X}, journal = {Theoretical Computer Science}, keywords = {combinatorics, saw}, month = {July}, number = {1-3}, pages = {129--156}, posted-at = {2007-12-27 21:25:38}, priority = {2}, title = {The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes}, url = {http://dx.doi.org/10.1016/S0304-3975(03)00080-X}, volume = {304}, year = {2003} }

TY - JOUR ID - citeulike:2175802 L3 - citeulike-article-id:2175802 N2 - Valiant (SIAM J. Comput. 8 (1979) 410-421) showed that the problem of computing the number of simple s-t paths in graphs is #P-complete both in the case of directed graphs and in the case of undirected graphs. Welsh (Complexity: Knots, Colourings and Counting, Cambridge University Press, Cambridge, 1993, p. 17) asked whether the problem of computing the number of self-avoiding walks of a given length in the complete two-dimensional grid is complete for #P1, the tally-version of #P. This paper offers a partial answer to the question of Welsh: it is #P-complete to compute the number of self-avoiding walks of a given length in a subgraph of a two-dimensional grid. Several variations of the problem are also studied and shown to be #P-complete. This paper also studies the problem of computing the number of self-avoiding walks in a subgraph of a hypercube. Similar completeness results are shown for the problem. By scaling the computation time to exponential, it is shown that computing the number of self-avoiding walks in hypercubes is a complete problem for #EXP in the case when a subgraph of a hypercube is specified by its dimension and a boolean circuit that accepts the nodes. Finally, this paper studies the complexity of testing whether a given word over the four-letter alphabet {U,D,L,R} represents a self-avoiding walk in a two-dimensional grid. A linear-space lower bound is shown for nondeterministic Turing machines with a 1-way input head to make this test. IS - 1-3 JF - Theoretical Computer Science EP - 156 TI - The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes VL - 304 SP - 129 KW - combinatorics KW - saw N1 - * Counting SAW's is hard AU - Liskiewicz, Maciej AU - Ogihara, Mitsunori AU - Toda, Seinosuke PY - 2003/07/28/ UR - http://dx.doi.org/10.1016/S0304-3975(03)00080-X ER -