| DATE: | Friday, April 20th |
| TIME: | 11:00 AM - 12:00 PM |
| PLACE: | McConnell 103 |
| TITLE: | Self-Avoiding Walks |
| SPEAKER: | Mitsunori Ogihara, Department of Computer Science, University of Rochester Rochester, NY, USA |
Valiant (SIAM Journal on Computing, volume 8, pages 410--421) showed that the problem of counting the number of s-t paths in graphs (both in the case of directed graphs and in the case of undirected graphs) is complete for #P under polynomial time one-Turing reductions (namely, some post-computation is needed to recover the value of a #P-function). Valiant then asked whether the problem of counting the number of self-avoiding walks of length n in the two-dimensional grid is complete for #P1, i.e., the tally-version of #P. This talk presents a partial answer to Valiant's question by showing that the problem of counting the number of self-avoiding walks in two-dimensional grid graphs is #P-complete. There are a number of possible specifications of the problem: (a) one, two, or none of the terminal points of the walks may be fixed and (b) the length of the path may be specified. It is shown that the problem is complete regardless of how many of the terminal points may be fixed as long as the length is unspecified. It is unknown whether the problem is still complete if the length is specified.
Also, this talk presents similar results on hypercube graphs. This time the problem is #P-complete even the length of the walks is specified. By scaling up the proof, it can be shown that the problem is complete for #EXPTIME if the graph is specified by a pair of Boolean circuits, one accepting the nodes and the other the edges.
This is joint work with Seinosuke Toda.