<p>Approximately counting all paths (or cycles) in polynomial time implies NP=RP. There is a very simple reduction to amplify the weight of the longest path/cycle. See <a href="https://doi.org/10.1016/0304-3975(86)90174-X" rel="nofollow noreferrer">https://doi.org/10.1016/0304-3975(86)90174-X</a>, section 5.</p>

CC BY-SA 3.0
2018-01-30T07:55:42.133Z
the reference you cite is for uniform, distributions, and actually generating cycles, from uniform distributions, section 5 deals with the generation of a cycle. Actually counting the number of cycles should be #P hard.
user3483902
CC BY-SA 3.0
2018-01-27T10:08:58.190Z
2018-01-27T10:08:58.190Z
Heng Guo
<p>Counting cycles, and paths in graphs is a hard problem, see questions <a href="https://cstheory.stackexchange.com/questions/12173/complexity-of-counting-paths-in-a-graph"> here, and related question for cycles for a given length $k$,  here</a>. The question is about the approximability of these graph problems, are they easily approximatable? Or do they have more fundamental implications for $NP$ complete problems, or #$P$ counting problems, hardness or otherwise. Any #$P$ hardness for approximately counting paths and cycles(from uniform distributions, or not) would imply, gaps between actually generating cycles paths(approximately) and enumerating the number of paths, and cycles. Also, what can be said about the  $APX$ hardness implications under reasonable hardness reduction assumptions($L$-hardness, others)? </p>

CC BY-SA 3.0
2018-03-01T14:45:49.547Z
You might be interested in the upcoming STOC'18 paper by Brand, Dell and Husfeld. They give an FPT algorithm computing a $(1+\varepsilon)$-approximation of the number of paths of length $k$ in directed graphs. Link to the paper: https://www.holgerdell.com/papers/Extensor-coding.pdf
tranisstor
CC BY-SA 3.0
2018-03-03T05:15:58.107Z
The above paper puts the problem in $W[1]$. for a parameter size on the path of length $k$.
user3483902
<approximation-hardness><approximation>
Approximately counting paths and cycles in a graph
user3483902
# Approximately counting paths and cycles in a graph

(Asked by: username_0 on 2018-01-27)

Counting cycles, and paths in graphs is a hard problem, see questions  [here, and related question for cycles for a given length $k$, here](https://cstheory.stackexchange.com/questions/12173/complexity-of-counting-paths-in-a-graph). The question is about the approximability of these graph problems, are they easily approximatable? Or do they have more fundamental implications for $NP$ complete problems, or #$P$ counting problems, hardness or otherwise. Any #$P$ hardness for approximately counting paths and cycles(from uniform distributions, or not) would imply, gaps between actually generating cycles paths(approximately) and enumerating the number of paths, and cycles. Also, what can be said about the $APX$ hardness implications under reasonable hardness reduction assumptions($L$-hardness, others)?

**Tags:** approximation-hardness, approximation

> **Comments:**
> **username_1**: You might be interested in the upcoming STOC'18 paper by Brand, Dell and Husfeld. They give an FPT algorithm computing a $(1+\varepsilon)$-approximation of the number of paths of length $k$ in directed graphs. Link to the paper: https://www.holgerdell.com/papers/Extensor-coding.pdf  
> **username_0**: The above paper puts the problem in $W[1]$. for a parameter size on the path of length $k$.  

---

## 1 answers

### Answer by username_2 on 2018-01-27. Score: 1

Approximately counting all paths (or cycles) in polynomial time implies NP=RP. There is a very simple reduction to amplify the weight of the longest path/cycle. See <https://doi.org/10.1016/0304-3975(86)90174-X>, section 5.

> **Comments:**
> **username_0**: the reference you cite is for uniform, distributions, and actually generating cycles, from uniform distributions, section 5 deals with the generation of a cycle. Actually counting the number of cycles should be #P hard.  

---

