| dc.description.abstract | Given a vertex-weighted tree T , the split of an edge e in T is the minimum over the weights
of the two trees obtained by removing e from T , where the weight of a tree is the sum of
weights of its vertices. Given a set of weighted vertices V and a multiset of integers S, we
consider the problem of constructing a tree on V whose splits correspond to S. The problem
is known to be NP-complete, even when all vertices have unit weight and the maximum
vertex degree of T is required to be at most 4. We show that
• the problem is strongly NP-complete when T is required to be a path,
• the problem is NP-complete when all vertices have unit weight and the maximum
degree of T is required to be at most 3, and
• it remains NP-complete when all vertices have unit weight and T is required to be a
caterpillar with unbounded hair length and maximum degree at most 3.
We also design polynomial time algorithms for
• the variant where T 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 T has a constant number of leaves.
The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but
also is a fixed-parameter algorithm for parameter k.
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. | |
