| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949811 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
We consider the time complexity of problems of counting paths and cycles in a graph, respectively. We first show that these two problems are #P-hard. Then, we show an inapproximability result: there is no FPRAS for approximately counting paths and cycles in a graph, respectively unless RP=NP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Masaki Yamamoto,