commit 06a682a00437558ae9e39e19cbf037d436c20b11
parent 8e881ad35026ec3d65daf150f247978aad0acb62
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 28 Sep 2026 16:01:56 +0200
commit with codex
Diffstat:
9 files changed, 34 insertions(+), 5 deletions(-)
diff --git a/approximation_additive b/approximation_additive
@@ -8,3 +8,5 @@
See also: [approximation_multiplicative]
Up: [approximation]
+
+Aliases: Additive approximation
diff --git a/approximation_multiplicative b/approximation_multiplicative
@@ -1,4 +1,4 @@
-# Approximation multiplicative
+# Multiplicative approximation
Possible for [sharp_satisfiability] for [disjunctive_normal_form], and many other problems
@@ -7,3 +7,5 @@ Another example is [arenas2021nfa]
See also: [approximation_additive], [fpras]
Up: [approximation]
+
+Aliases: Multiplicative approximation
diff --git a/homomorphism_closed b/homomorphism_closed
@@ -12,6 +12,6 @@ Special case:
Up: [closure] under [homomorphism]
-Aliases: closed under homomomorphism, homomorphism closed query, homomorphism closed queries, homomorphism-closed query, homomorphism-closed queries
+Aliases: closed under homomomorphism, homomorphism closed query, homomorphism closed queries, homomorphism-closed query, homomorphism-closed queries, hom closed query, hom closed queries, hom-closed query, hom-closed queries
-See also: [infinite_UCQ]
+See also: [infinite_UCQ], [monotone_query]
diff --git a/hypertree_width_variants b/hypertree_width_variants
@@ -5,6 +5,8 @@
- makes [tree_decomposition_computation] easier
- [query_decomposition]
+all are within a factor 3 of each other, cf [adler2007hypertree] and [gottlob2007generalized]
+
Up: [width_measure] for [hypergraph]
See also: [hyperpath_width]
diff --git a/infinite_ucq b/infinite_ucq
@@ -8,4 +8,4 @@ There are precisely the [homomorphism_closed] queries
Up: [homomorphism_closed], [UCQ]
-Aliases: infinite UCQs
+Aliases: infinite UCQs, UCQinf
diff --git a/query b/query
@@ -11,6 +11,7 @@
- [query_match]
- [minimal_match]
- [connected_query]
+- [monotone_query]
## Problems
diff --git a/query_relevance b/query_relevance
@@ -4,6 +4,10 @@ Given a [database] D, a [Boolean_query] Q, and a [fact] f of D, we say that f is
See [bienvenu2026how]
+For [CQs], relevance is [Sigma_P_2_complete] in [combined_complexity]
+
+For [acyclic_CQs], relevance is [NP_complete] in [combined_complexity]
+
Up: [provenance]
Aliases: relevance
diff --git a/treewidth_computation b/treewidth_computation
@@ -0,0 +1,18 @@
+# Treewidth computation
+
+The [computational_problem] of computing the [treewidth]
+
+[flum2002query]
+- it can be [FPT_linear] (exp in k)
+- it can be in [XP], in n^{k+2}
+
+[Treewidth] is [NP_hard] to compute when k is given as input
+- already on [cubic_graphs], cf [bodlaender2023treewidth]
+
+[Approximation]: see [treewidth_approximation]
+
+Open whether it is tractable to compute on [planar_graphs]
+
+Up: [treewidth], [computational_problem]
+
+See also: [tree_decomposition_computation], [hypertreewidth_computation], [generalized_hypetreewidth_computation]
diff --git a/union_of_conjunctive_queries_disequality b/union_of_conjunctive_queries_disequality
@@ -4,4 +4,4 @@ A [disjunction] of [CQs_with_disequalities]
Up: [UCQ], [query_disequality]
-Aliases: union of conjunctive query inequality, Union of conjunctive queries inequality, UCQ inequality, UCQ disequality, unions of conjunctive query disequality
+Aliases: union of conjunctive query inequality, Union of conjunctive queries inequality, UCQ inequality, UCQ disequality, unions of conjunctive query disequality, UCQneq
