As part of a research task, I came across a sub-problem as follows:
Given an undirected, unweighted tree of $$$n$$$ nodes and a threshold $$$k$$$, partition the $$$n-1$$$ edges of the tree into simple paths such that every edge belongs to exactly one simple path and the maximum length of a simple path is atmost $$$k$$$. What is the minimum number of simple path partitions which meet this criteria? Note that every edge belongs to exactly one simple path, but the same vertices can be visited by multiple simple paths.
I was wondering if this is by any chance a "standard" problem with a known polynomial time solution?
