1
$\begingroup$

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)?

$\endgroup$
  • $\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$ – tranisstor Mar 1 '18 at 14:45
  • $\begingroup$ The above paper puts the problem in $W[1]$. for a parameter size on the path of length $k$. $\endgroup$ – user3483902 Mar 3 '18 at 5:15
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user3483902 Jan 30 '18 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.