wiki_research

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

independent_set_counting (449B)

      1 # Independent set counting
      2 
      3 - [sharp_bis] is the problem of counting independent sets on [bipartite_graphs]
      4   - it is open whether it admits an [fpras] 
      5 - [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is]
      6 
      7 By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly
      8 
      9 Up: [counting_problem], [independent_set]
     10 
     11 See also: [maximal_independent_set_counting], [maximum_independent_set_counting]