commit f79149402b0e15ec5b5debdd84246447289b18b8
parent 36727df3fee19c76fe111e9945d814d3dc951c0b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 12 Feb 2026 17:09:44 +0100
commit with codex
Diffstat:
3 files changed, 15 insertions(+), 5 deletions(-)
diff --git a/independent_set b/independent_set
@@ -19,11 +19,7 @@ An *independent set* is a [subset] of [vertices] of an [undirected_graph] such t
## [counting]
-- [sharp_bis] is the problem of counting independent sets on [graph_bipartite]
- - it is open whether it admits an [fpras]
-- [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is]
-
-By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly
+[independent_set_counting]
## [linear_relaxation]
diff --git a/independent_set_counting b/independent_set_counting
@@ -0,0 +1,11 @@
+# Independent set counting
+
+- [sharp_bis] is the problem of counting independent sets on [bipartite_graphs]
+ - it is open whether it admits an [fpras]
+- [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is]
+
+By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly
+
+Up: [counting_problem], [independent_set]
+
+See also: [maximal_independent_set_counting], [maximum_independent_set_counting]
diff --git a/maximal_independent_set_counting b/maximal_independent_set_counting
@@ -5,5 +5,8 @@
- mentioned in [livshits2021counting]
- [sharpp_hard] even on [chordal_graphs]:
- [okamoto2008counting]
+- [approximate_counting]: cf [goldberg2016approximately] on [bipartite_graphs]
Up: [counting_problem], [maximal_independent_set]
+
+See also: [maximum_independent_set_counting], [independent_set_counting]
