wiki_research

commit 4ce11943c0f699fa7daaca77b44fcfa1aae3a1d4
parent a6676189a654e53930891fae8668d80b1afb001b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 25 Sep 2026 18:09:25 +0200

commit with codex

Diffstat:
dv_graph
 | 
11
+++++++++++
graph_sandwich_problem
 | 
2
++
intersection_graph
 | 
3
+++
leaf_power
 | 
6
+++++-
mim_width
 | 
2
++
np_hard
 | 
2
++
path_graph
 | 
2
+-
rdv_graph
 | 
13
+++++++++++++
uv_graph
 | 
13
+++++++++++++

9 files changed, 52 insertions(+), 2 deletions(-)
diff --git a/dv_graph b/dv_graph
@@ -0,0 +1,11 @@
+# DV graph
+
+Aka "directed path graphs", but not the same as [path_graphs] of course: the [intersection_graphs] of [directed_paths] in a [tree]
+
+[hamiltonian_cycle_problem] shown [NP_hard] on such graphs in [narasimhan1989note]
+
+Up: [intersection_graph]
+
+Aliases: DV graphs
+
+See also: [RDV_graph], [UV_graph]
diff --git a/graph_sandwich_problem b/graph_sandwich_problem
@@ -1,5 +1,7 @@
 # Graph sandwich problem
 
+https://en.wikipedia.org/wiki/Graph_sandwich_problem
+
 For a [graph_class] C, given two [graphs] (V, E_1) and (V, E_2) with E_1
 subseteq E_2, decide if there is E_1 subseteq E subseteq E_2 such that (V, E)
 belongs to C
diff --git a/intersection_graph b/intersection_graph
@@ -4,5 +4,8 @@ https://en.wikipedia.org/wiki/Intersection_graph
 
 - [interval_graph]
 - [circle_graph]
+- [uv_graph]
+- [dv_graph]
+- [rdv_graph]
 
 Up: [graph_family]
diff --git a/leaf_power b/leaf_power
@@ -1,10 +1,14 @@
 # Leaf power
 
+https://www.graphclasses.org/classes/gc_649.html
+
 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
+[Hamiltonian_path] on them is in [PTIME] for each fixed k
 https://cstheory.stackexchange.com/questions/52305/complexity-of-finding-a-path-visiting-all-leaves-on-a-tree-while-respecting-a-di/52315
 
+[NP_hardness] of [Hamiltonian_path_problem] is claimed by [IGCSI] from [RDV_graphs] but is in fact open, cf [bergougnoux2026hamiltonicity]
+
 Variant: [pairwise_compatibility_graph], i.e., the distance is between two thresholds
 
 Recognizing these graphs is [NP_hard] [duprelatour2025recognizing]
diff --git a/mim_width b/mim_width
@@ -8,4 +8,6 @@ via [induced_matching]
 
 variant [sim_width]
 
+[bergougnoux2025hamiltonicity] shows that the [hamiltonian_path_problem] is [NP_hard] on [graphs] of [linear_mim_width] 26
+
 Up: [width_measure]
diff --git a/np_hard b/np_hard
@@ -7,3 +7,5 @@ at least as hard as the hardest [computational_problems] in [nptime]
 See also: [nptime], [computational_hardness]
 
 Up: [computational_complexity]
+
+Aliases: NP hardness, NP-hardness
diff --git a/path_graph b/path_graph
@@ -19,6 +19,6 @@ special case:
 
 Up: [graph]
 
-See also: [path]
+See also: [path], [UV_graph]
 
 Aliases: path graphs
diff --git a/rdv_graph b/rdv_graph
@@ -0,0 +1,13 @@
+# RDV graph
+
+discussed in [panda2008np] which gives a [flawed_proof] of [NP_hardness] of [hamiltonian_path] in RDV graphs, cf [bergougnoux2026hamiltonicity]
+
+[rdv_graph_isgci]
+
+taxonomy in [monma1986intersection]
+
+Up: [intersection_graph]
+
+Aliases: rooted directed path graph, rooted directed path graphs, RDV graphs
+
+See also: [uv_graph], [dv_graph]
diff --git a/uv_graph b/uv_graph
@@ -0,0 +1,13 @@
+# UV graph
+
+A graph which is an [intersection_graph] of [undirected_paths] in some [tree]
+
+discussed in [panda2008np]
+
+taxonomy in [monma1986intersection]
+
+Up: [path_graph]
+
+See also: [DV_graph], [RDV_graph]
+
+Aliases: UV graphs