commit 311b804970c1562c809915c92bb02ce8a7b40b24
parent 0638bdfaa4307836449974ed533dad36ed8a94c0
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 24 Oct 2025 07:48:57 +0200
commit with codex
Diffstat:
6 files changed, 27 insertions(+), 1 deletion(-)
diff --git a/gql b/gql
@@ -2,5 +2,6 @@
- [francis2023researchers]: explanation GQL
- [francis2023gpc] introduces [gpc] which is equivalent to GQL but easier to understand
+- [figueira2025complexity] studies the [computational_complexity] of [query_evaluation]
Up: [graph_query_languages_standards]
diff --git a/graph_family b/graph_family
@@ -40,6 +40,8 @@ A (generally [infinite]) set of [graphs]
- [friendship_graph]
- [berge_graph]
+- [leaf_power]
+
May have the property of being [graph_class_hereditary]
Up: [graph]
diff --git a/leaf b/leaf
@@ -4,6 +4,6 @@
Up: [tree]
-See also: [internal_node]
+See also: [internal_node], [leaf_power]
Aliases: leaves
diff --git a/leaf_power b/leaf_power
@@ -0,0 +1,12 @@
+# Leaf power
+
+A [graph] where there exists a [tree] and threshold k such that the [edges] of the graph connect the [vertices] at [distance] at most k in the tree
+
+[Hamiltonian_path] on them is in [PTIME] for each fixed k but [NP_hard] in general
+https://cstheory.stackexchange.com/questions/52305/complexity-of-finding-a-path-visiting-all-leaves-on-a-tree-while-respecting-a-di/52315
+
+Variant: [pairwise_compatibility_graph], i.e., the distance is between two thresholds
+
+Recognizing these graphs is [NP_hard] [duprelatour2025recognizing]
+
+Up: [graph_family]
diff --git a/unambiguous_sigma2 b/unambiguous_sigma2
@@ -0,0 +1,9 @@
+# Unambiguous sigma2
+
+The [Sigma2] class with a unique choice of existential
+
+Studied in [gilboa2025complexity]
+
+See also: [up]
+
+Up: [sigma2]
diff --git a/up b/up
@@ -14,3 +14,5 @@ Generalizations:
[Complement]: [coUP]
Up: [nptime], [unambiguous_computation], [complexity_class]
+
+See also: [unambiguous_sigma2]
