Complexity of splits reconstruction for low-degree trees

Given a vertex-weighted tree TT, the split of an edge ee in TT is the minimum over the weights of the two trees obtained by removing ee from TT, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices VV and a multiset of integers SS, we consider the problem of constructing a tree on VV whose splits correspond to SS. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of TT is required to be at most 44. We show that
• the problem is strongly NP-complete when TT is required to be a path,
• the problem is NP-complete when all vertices have unit weight and the maximum degree of TT is required to be at most 33, and
• it remains NP-complete when all vertices have unit weight and TT is required to be a caterpillar with unbounded hair length and maximum degree at most 33. We also design polynomial time algorithms for
• the variant where TT is required to be a path and the number of distinct vertex weights is constant, and
• the variant where all vertices have unit weight and TT has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, kk, is a constant, but also is a fixed-parameter algorithm for parameter kk.Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm.The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physico-chemical properties of the substance.