# Approximately counting paths and cycles in a graph

Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. 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)?

• 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: holgerdell.com/papers/Extensor-coding.pdf Mar 1 '18 at 14:45
• The above paper puts the problem in $W[1]$. for a parameter size on the path of length $k$. Mar 3 '18 at 5:15