wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

counting_simple_path_approximate (448B)

      1 # Approximate counting of simple paths
      2 
      3 Given a [graph], can we do [approximate_counting] for the [counting_problem] of [counting_simple_paths]?
      4 
      5 No: there is no [FPRAS] unless [RP] = [NP], cf [yamamoto2017approximately]
      6 
      7 This applies for [undirected_graphs] and for [directed_graphs], and with fixed endpoints or without fixed endpoints
      8 
      9 Up: [counting_simple_path]
     10 
     11 Aliases: approximate counting simple paths, approximate counting of simple paths