leaf_power (559B)
1 # Leaf power 2 3 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 4 5 [Hamiltonian_path] on them is in [PTIME] for each fixed k but [NP_hard] in general 6 https://cstheory.stackexchange.com/questions/52305/complexity-of-finding-a-path-visiting-all-leaves-on-a-tree-while-respecting-a-di/52315 7 8 Variant: [pairwise_compatibility_graph], i.e., the distance is between two thresholds 9 10 Recognizing these graphs is [NP_hard] [duprelatour2025recognizing] 11 12 Up: [graph_family]