Clearly, one can construct \(T^{\prime }\)  from \(T\)  in linear time. By an algorithm from [1]} one can construct a minimum path cover of \(T\)  in linear time. Indeed, the mentioned algorithm is based on finding a pendant generalized star, and providing a path cover for it, and then continuing the process in the tree from which this pendant generalized star is removed. In addition, checking if the resulting path cover is interior can be done efficiently by going through all connector edges and checking if the end-vertices are interior vertices of their paths. This resolves (1). To consider \(\cal P\)  in \(T\)  we only need to add additional one-vertex paths to \(\cal P\) , which consist of vertices deleted in the previous step. This resolves step (2). For step (3), we apply an algorithm for verifying whether two trees are isomorphic. We can use the classical AHU algorithm for checking tree isomorphism [2]}, applied on the corresponding components of the forest. We slightly modify the algorithm by fixing the two vertices and checking whether an algorithm maps one to the other. This algorithm is linear, and since the number of paths in a path cover is \(O(n)\) , we derive that entire algorithm performs in \(O(n^2)\)  time. We summarize these observations in the following result.
