commit 274803c5992608e9d70888accaa516100bc837ea
parent cd82388c69aacf5222dc83c588339c58b1c927a7
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 27 Mar 2025 12:07:06 +0100
commit with codex
Diffstat:
33 files changed, 288 insertions(+), 8 deletions(-)
diff --git a/activity_selection_problem b/activity_selection_problem
@@ -0,0 +1,10 @@
+# Activity selection problem
+
+https://en.wikipedia.org/wiki/Activity_selection_problem
+
+Variant you want to maximize the size of selected intervals (not the number of selected activities):
+- also has a [greedy_algorithm]
+
+Up: [optimization_problem]
+
+See also: [project_selection_problem]
diff --git a/alon_scc_lemma b/alon_scc_lemma
@@ -0,0 +1,9 @@
+# Alon SCC lemma
+
+Lemma 2.3 of [alon2001regular]
+
+- [graph_period], [graph_coloring]
+
+See also: [property_testing], [approximate_membership]
+
+Up: [lemma], [strongly_connected_component]
diff --git a/automaton_inclusion b/automaton_inclusion
@@ -4,6 +4,6 @@
[ptime] for [automata_deterministic]
-Up: [automata_problems]
+Up: [automata_problems], [set_inclusion]
See also: [automaton_equivalence], [language_inclusion]
diff --git a/conp b/conp
@@ -0,0 +1,8 @@
+# Conp
+
+[Decision_problems] whose [complementation] is in [nptime]
+
+- [conp_hard]
+- [conp_complete]
+
+See also: [nptime], [np_cap_conp]
diff --git a/directed_edge b/directed_edge
@@ -0,0 +1,9 @@
+# Directed edge
+
+An [ordered_pair] of two [vertices]
+
+Up: [edge]
+
+See also: [graph_directed]
+
+Aliases: directed edges
diff --git a/enumeration_cqs b/enumeration_cqs
@@ -0,0 +1,15 @@
+# Enumeration for CQs
+
+[enumeration_query_answers] is tractable for [CQs] ([linear_preprocessing_constant_delay]) if they are [acyclic_free_connex]
+
+For [SJFCQs], conditional lower bounds:
+- For [cyclic_CQs], [lower_bound] assuming [hyperclique_conjecture]
+- For [acyclic_CQs] that are not [acyclic_free_connex], [lower_bound] assuming [boolean_matrix_multiplication_hypothesis]
+
+With [self_joins]: [enumeration_self_joins]
+
+[enumeration_cqs_extensions]
+
+Up: [enumeration_query_answers] for [conjunctive_query]
+
+See also: [direct_access]
diff --git a/enumeration_ordered b/enumeration_ordered
@@ -1,8 +1,8 @@
# Ordered enumeration
- [enumeration_ordered_cq]
-- [enumeration_ordonnee_mso]
-- [enumeration_ordonnee_chemins]
+- [enumeration_ordered_mso]
+- [enumeration_ordered_paths]
Up: [enumeration], [order]
diff --git a/enumeration_ordered_paths b/enumeration_ordered_paths
@@ -0,0 +1,7 @@
+# Ordered enumeration of paths
+
+- [shortest_path_enumeration]
+ - [eppstein2017kbest]
+ - [eppstein1997finding]
+
+Up: [enumeration_ordered] of [paths]
diff --git a/enumeration_paths b/enumeration_paths
@@ -0,0 +1,7 @@
+# Enumeration paths
+
+[Enumeration] of [paths] in a [graph]
+
+[Practice]: [peng2025hop]
+
+Up: [enumeration_graphs], [paths]
diff --git a/enumeration_query_answers b/enumeration_query_answers
@@ -0,0 +1,9 @@
+# Enumeration query answers
+
+- [enumeration_cqs]
+- [enumeration_self_joins]
+- [enumeration_ucqs]
+
+tool: [query_cover]
+
+Up: [enumeration]
diff --git a/enumeration_ucqs b/enumeration_ucqs
@@ -0,0 +1,21 @@
+# Enumeration for UCQs
+
+- Union of tractable [CQs] is tractable ([linear_preprocessing_constant_delay])
+- A union where every [CQ] is intractable may be tractable! [carmeli2021enumeration]
+ - notion of [union_extension]
+ - covers all known tractable cases
+ - for union of two intractable [CQs], union extensions are known to (conditionally)
+ cover all tractable queries for disjunctions of two queries
+ - assumes hypothesis on finding [4clique]
+ - case of a union of a tractable CQ and an intractable CQ discussed in [bringmann2022unbalanced]
+
+for [linear_preprocessing_constant_delay_constant_memory], not well-known, cf [carmeli2021enumeration] Section 6.3
+- in particular [cheaters_lemma]
+
+important: it is necessary to look at [body_homomorphism] because the [free_variables] may not be the same
+
+open question: [enumeration_ucqs_classifying]
+
+Up: [enumeration] for [union_of_conjunctive_query]
+
+See also: [enumeration_cqs]
diff --git a/generalized_dominating_set b/generalized_dominating_set
@@ -0,0 +1,15 @@
+# Generalized dominating set
+
+for sets sigma, rho of non-negative integers, a set of vertices of a graph S
+such that the neighborhood of each vertex of S contains a number of vertices of
+the set in sigma, and likewise for rho and for vertices not in the set
+
+mentioned in [focke2023tight1]
+- also in [chapelle2010parameterized] [golovach2012parameterized] for [parameterized_complexity] with [treewidth] as parameter
+
+Generalizes:
+- [dominating_set]
+- [independent_set]
+- [independent_dominating_set]
+
+Up: [graph_substructure]
diff --git a/graph_directed b/graph_directed
@@ -1,6 +1,6 @@
# Graph directed
-A [graph] where [edges] are [ordered_pairs]
+A [graph] where [edges] are [directed_edges] [ordered_pairs]
- [directed_acyclic_graph]
- [graph_period]
@@ -8,6 +8,6 @@ A [graph] where [edges] are [ordered_pairs]
Up: [graph]
-See also: [graph_undirected]
+See also: [graph_undirected], [directed_edge]
Aliases: directed graph, directed graphs
diff --git a/graph_mixed b/graph_mixed
@@ -0,0 +1,7 @@
+# Graph mixed
+
+A [graph] featuring both [directed_edges] and [undirected_edges]
+
+Up: [graph]
+
+See also: [graph_directed], [graph_undirected]
diff --git a/graph_undirected b/graph_undirected
@@ -1,8 +1,8 @@
# Graph undirected
-[graph] where [edge]s are [pair]s
+[graph] where [edges] are [undirected_edges]
-See also: [graph_directed]
+See also: [graph_directed], [undirected_edge]
Up: [graph]
diff --git a/hyperclique_hypothesis b/hyperclique_hypothesis
@@ -0,0 +1,13 @@
+# Hyperclique hypothesis
+
+Defined in [bringmann2022unbalanced]
+
+For any k >= 3, detecting a k-[hyperclique] in a (k-1)-[uniform_hypergraph] cannot be done in O(n^{k-1})
+
+- implies in particular [triangle_detection_conjecture]: you cannot detect triangles in O(n^2) in graphs
+
+Up: [hypergraph]
+
+Aliases: hyperclique conjecture
+
+See also: [clique_problem]
diff --git a/join b/join
@@ -0,0 +1,9 @@
+# Join
+
+- [semijoin]
+- [join_tree]
+- [join_path]
+- [self_join]
+- [optimal_joins]
+
+Up: [databases]
diff --git a/join_path b/join_path
@@ -0,0 +1,7 @@
+# Join path
+
+[join_tree] which is a [path]
+
+Up: [join_tree], [path]
+
+See also: [pathwidth]
diff --git a/language_inclusion b/language_inclusion
@@ -3,6 +3,6 @@
- [pattern_language_inclusion]
- [language_inclusion_bounded]
-Up: [formal_language_computational_problems], [inclusion]
+Up: [formal_language_computational_problems], [set_inclusion]
See also: [automaton_inclusion]
diff --git a/mantels_theorem b/mantels_theorem
@@ -0,0 +1,9 @@
+# Mantels theorem
+
+https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem
+
+Generalization: [turan_theorem]
+
+Up: [triangle_free_graph]
+
+See also: [extremal_graph_theory]
diff --git a/minimum_label_cut b/minimum_label_cut
@@ -0,0 +1,9 @@
+# Minimum label cut
+
+You have a [graph] where [edges] are labeled, we want the minimum [subset] of edge labels which is a [cut]
+
+Studied in [zhang2020minimum]
+
+[NP_hard] from [hitting_set]
+
+Up: [minimum_cut]
diff --git a/project_selection_problem b/project_selection_problem
@@ -0,0 +1,12 @@
+# Project selection problem
+
+https://en.wikipedia.org/wiki/Project_selection_problem
+
+you have projects and machines and want to optimize profit (revenue of selected projects minus cost of selected machines), and each project requires a specific subset of machines
+
+reduces to [network_flow]
+
+also works for arbitrary [directed_graphs] not just [bipartite_graphs]
+ - cf https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Project_Selection.pdf
+
+Up: [network_flow]
diff --git a/query_cover b/query_cover
@@ -0,0 +1,13 @@
+# Query cover
+
+a subset of [query] [answers] that can be used for [enumeration]
+
+- [kara2018covers]
+- [koutris2025generalized]
+ - make the cover depend on multiple possible [tree_decompositions]
+ - like [PANDA], like [submodular_width]
+ - uses [entropic_width], defined in [fan2024tight]
+
+Up: [enumeration_query_answers]
+
+See also: [set_cover], [vertex_cover], [edge_cover]
diff --git a/self_join b/self_join
@@ -0,0 +1,12 @@
+# Self join
+
+A *self join* means reusing the same [database_relation] twice in [conjunctive_query]
+
+- for [enumeration], make lower bounds harder
+- for [pqe], makes upper bounds harder
+
+Up: [conjunctive_query], [join]
+
+See also: [sjfcq], [conjunctive_query_self_join_free]
+
+Aliases: self joins, self-join, self-joins
diff --git a/set b/set
@@ -1,6 +1,8 @@
# Set
- [multiset]
+- [subset]
+- [set_inclusion]
Up: [set_theory]
diff --git a/set_cover b/set_cover
@@ -0,0 +1,9 @@
+# Set cover
+
+Given a universe [set], and a collection of [subsets] whose [union] is the universe, find a subcollection with [minimum] [cardinality] whose [union] is equal to the universe
+
+[set_cover_problem]
+
+See also: [hitting_set], [vertex_cover], [edge_cover]
+
+Up: [set]
diff --git a/set_cover_problem b/set_cover_problem
@@ -0,0 +1,14 @@
+# Set cover problem
+
+[Computational_problem] of computing a [minimum_set_cover]
+
+Variant: [set_cover_red_blue]
+
+Duality with [hitting_set]:
+ - Cf https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation
+
+[Approximation]: cf [minimum_set_cover_approximation]
+
+Variants: [set_cover_variants]
+
+Up: [computational_problem] about [set_cover]
diff --git a/set_cover_red_blue b/set_cover_red_blue
@@ -0,0 +1,13 @@
+# Red-blue set cover problem
+
+cf [carr2000red]
+
+You have a universe where some elements are red and others are blue
+
+You have a collection of sets and want to find a subfamily that covers all blue elements but covers a least number of red elements
+
+The question is how well can it be [approximated], compared to [set_cover_approximation]
+
+Up: [set_cover_problem]
+
+See also: [exact_matching]
diff --git a/set_inclusion b/set_inclusion
@@ -0,0 +1,9 @@
+# Set inclusion
+
+A [set] S is *included* into another [set] S' if every [element] of S is also an [element] of S'
+
+Up: [set]
+
+Aliases: inclusion, included
+
+See also: [inclusion_dependency]
diff --git a/shortest_path_enumeration b/shortest_path_enumeration
@@ -0,0 +1,12 @@
+# Shortest path enumeration
+
+- [casel2021shortest] studies [shortest_path] algorithms in an [enumeration] perspective
+ - [single_source_shortest_path]
+ - [all_pairs_shortest_path]
+ - does not cite work by [eppstein]
+- [eppstein1997finding]
+- [eppstein2017kbest]
+
+Up: [shortest_path], [enumeration]
+
+See also: [gawrychowski2024revisiting]
diff --git a/subset b/subset
@@ -0,0 +1,9 @@
+# Subset
+
+A [set] which is [included] into another [set]
+
+Up: [set]
+
+Aliases: subsets
+
+See also: [subset_sum]
diff --git a/subset_sum b/subset_sum
@@ -22,3 +22,5 @@ generalization: [all_subset_sums], compute all the sums
- [subset_sum_counting]
Up: [decision_problem] on [sum]
+
+See also: [subset]
diff --git a/undirected_edge b/undirected_edge
@@ -0,0 +1,9 @@
+# Undirected edge
+
+A [pair] of two [vertices]
+
+Up: [edge]
+
+See also: [graph_undirected]
+
+Aliases: undirected edges, edge undirected
