commit e25bbade13a4bec39b049a1894c3925b8f58a73b
parent dd42b18a4f79e2c44a9e8c67deb389a8428c5799
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 16 May 2025 14:03:00 +0200
commit with codex
Diffstat:
6 files changed, 40 insertions(+), 4 deletions(-)
diff --git a/balancing b/balancing
@@ -3,7 +3,7 @@
Limiting the [height] of a representation
- balancing [tree_decomposition]: [balancing_tree_decomposition]
-- balancing [straight_line_program]
+- balancing [straight_line_program]: [SLP_balancing]
- [tree_balancing]
- [depth_reduction] of [arithmetic_circuit]: [depth_reduction_arithmetic_circuit]
- [dymond1988input] for [VPAs]
diff --git a/dag_path_length b/dag_path_length
@@ -0,0 +1,16 @@
+# Dag path length
+
+Given a [DAG] G, a source s and sink t, and a length l, decide whether there is an st-path of length l in G
+
+Generalization of [unary_subset_sum] (corresponds to a specific shape of [DAGs] with a sequence of [bottlenecks] and two parallel paths from one bottleneck to the next
+
+[Conditional_hardness] in [potechin2020lengths] for [NFA_unary_lengths]
+- reduction from [triangle_detection]
+
+Can be solved via [Boolean_matrix_multiplication]
+
+[dag_path_length_mine]
+
+Up: [path_length], [directed_acyclic_graph]
+
+See also: [bringmann2024nfa]
diff --git a/forest b/forest
@@ -7,3 +7,5 @@ Generalization: [pseudoforest]
Up: [data_structure]
Aliases: forests
+
+See also: [forest_algebra]
diff --git a/network_reliability b/network_reliability
@@ -1,8 +1,18 @@
# Network reliability
-- [st_reliability]
-- [network_reliability_fpras]
-- [all_terminal_network_reliability]
+The problem is called *network reliability*. You have a
+graph G and a set T of terminals. You want to count the number of
+subgraphs of G in which the vertices of T are connected.
+
+Can be posed for [directed_graphs] or [undirected_graphs]
+
+- [st_reliability] when |T| = 2
+- [multi_terminal_network_reliability] for larger T
+- [all_terminal_network_reliability] when T contains all vertices
+
+Can also want to count the number of [subgraphs] that are not connected (makes a difference for [approximation]): [network_unreliability]
+
+[FPRAS]: [network_reliability_fpras]
Up: [graph]
diff --git a/network_unreliability b/network_unreliability
@@ -0,0 +1,7 @@
+# Network unreliability
+
+Equivalent to [network_reliability] but not the same notion of [approximation]
+
+special case: [all_terminal_network_unreliability]
+
+Up: [network_reliability]
diff --git a/straight_line_program b/straight_line_program
@@ -4,6 +4,7 @@ essentially a [context_free_grammar] that generates a single [string]: [acyclici
- [enumeration_slp]
- [smallest_grammar_problem]
+- [slp_balancing]
Up: [string_compression]
