Finding the two-core of a tree (Q1086244)

The core of a graph was defined by \textit{C. A. Morgan} and \textit{P. J. Slater} [A linear algorithm for the core of a tree, J. Algorithms 1, 247- 258 (1980; Zbl 0454.68067)] to be a path minimizing the sum of the distances from all the vertices of the graph to the (nearest vertex of the) path. Finding the core of a general graph is NP-hard by a trivial reduction from the hamiltonian path problem which is also NP-hard [\textit{M. R. Garey} and \textit{D. S. Johnson}, Computers and intractibility, A guide to the theory of NP completeness (1979; Zbl 0411.68039)]; however, for trees a linear algorithm was presented in the paper of Morgan and Slater (loc. cit.). In the paper under review, a 2-core of a graph is defined to be a set of two disjoint paths minimizing the sum of the distances from all the vertices of the graph to the (nearest vertex in the union of the) two paths. Finding the 2-core of a general graph is also NP-hard [Garey and Johnson (loc. cit.), problem GT 13]; for trees this paper presents a simple quadratic algorithm and a more sophisticated algorithm which runs in O(nd) time on an n-vertex tree of diameter d. The O(nd) algorithm is an improvement over the \(O(n^ 2)\) one in the average case since the average diameter of a tree in O(\(\sqrt{n})\) [\textit{A. Renyi} and \textit{S. Szekeres}, On the height of trees, J. Aust. Math. Soc. 7, 497-507 (1967; Zbl 0153.258)]. Another O(nd) algorithm is presented for finding a set of two intersecting paths in a tree with the same minimizing property.