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)?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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 $\endgroup$– tranisstorMar 1, 2018 at 14:45
-
$\begingroup$ The above paper puts the problem in $W[1]$. for a parameter size on the path of length $k$. $\endgroup$– user3483902Mar 3, 2018 at 5:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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. $\endgroup$ Jan 30, 2018 at 7:55