Standard Problem or Not?

Revision en1, by Final_Track, 2024-09-11 22:35:44

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Final_Track 2024-09-11 22:35:44 641 Initial revision (published)