commit 7f45bfda446bb667deeecb9c078c6fb21bca63e2
parent ed7774f192c1c1de1dd52644b97f3411cf7f7f31
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 19 Mar 2025 15:26:03 +0100
commit with codex
Diffstat:
4 files changed, 15 insertions(+), 1 deletion(-)
diff --git a/bag_cq_containment b/bag_cq_containment
@@ -1,9 +1,11 @@
# Bag cq containment
-bag [query_containment] for [CQs] is [open_problem]
+[computational_complexity] of [query_containment] for [CQs] under [bag_semantics] is [open_problem]
- introduced in [chaudhuri1993optimization]
- withdrawn claim of [Pi_2_p]-hardness
- only known [lower_bound] is [NP_hard]
+Recent discussion: [marcinkowski2025bag]
+
Up: [containment_bag_semantics], [CQs]
diff --git a/graph_operations b/graph_operations
@@ -4,5 +4,6 @@
- [graph_product]
- [edge_contraction]
- [underlying_undirected_graph]
+- [subdivision]
Up: [graph]
diff --git a/pathwidth_directed b/pathwidth_directed
@@ -9,3 +9,5 @@ Relationship to [pathwidth]:
Up: [pathwidth]
See also: [treewidth_directed]
+
+Aliases: directed pathwidth
diff --git a/subdivision b/subdivision
@@ -0,0 +1,9 @@
+# Subdivision
+
+In a [graph], given an [edge], replace this [edge] by a [path] whose intermediate [vertices] are fresh
+
+Up: [graph_operations]
+
+See also: [edge_contraction], [topological_minor]
+
+Aliases: subdivisions
