{'fraction_non_alphanumeric': 0.05432590800180295, 'fraction_numerical': 0.012834199226626812, 'mean_word_length': 3.402046783625731, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 51, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complexity of Splits Reconstruction for Low-Degree Trees

Given a vertex-weighted tree T, the split of an edge xy in T is min{s_x(xy), s_y(xy)} where s_u(uv) is the sum of all weights of vertices that are closer to u than to v in T. Given a set of weighted vertices V and a multiset of splits 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 no more than 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 no more than 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 fixed-parameter tractable when parameterized by 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 correlation between structural properties, such as the Wiener index, which is closely connected to the considered problem, and biological activity.


Introduction
In this paper, we consider trees T = (V, E) where integer weights are associated to vertices by a function ω : V → N, where N denotes the set of natural numbers excluding 0.
Definition 1. Let T be a tree and ω : V → N be a function. The split of an edge e in T is the minimum of Ω(T 1 ) and Ω(T 2 ), where T 1 and T 2 are the two trees obtained by deleting e from T , and Ω(T i ) = v∈Ti ω(v). We use S(T ) to denote the multiset of splits of T .
We consider the problem of reconstructing a tree with a given multiset of splits and a given set of weighted vertices.
Weighted Splits Reconstruction (WSR): Given a set V of n vertices, a weight function ω : V → N, and a multiset S of integers, is there a tree T whose multiset of splits is S (i.e.

S(T ) = S)?
The Weighted Splits Reconstruction for Trees of Maximum Degree k problem (WSR k ) is defined in the same way, except that we restrict the tree T to have maximum degree at most k. When we require T to belong to a class of trees T , the problem is called Weighted Splits Reconstruction for T .
When ω assigns unit weights to the vertices, the problem is simply called Splits Reconstruction (SR). The Splits Reconstruction for Trees of Maximum Degree k problem (SR k ) and the Splits Reconstruction for T are the obvious unweighted counterparts of the weighted variants defined above. Related Work. In the field of Chemical Graph Theory [2, 3,19], molecules are modeled by graphs in order to study the physical properties of chemical compounds. A chemical graph is a graph, where vertices represent atoms of a chemical compound and edges the chemical bonds between them. Within the area of quantitative structure-activity relationship (QSAR), several structural measures of chemical graphs were identified that quantitatively correlate with a well defined process, such as biological activity or chemical reactivity. Probably the most widely known example is the Wiener index (see [13]): the sum of the distances in a graph between each pair of vertices, where the distance between two vertices is the length (the number of edges) of a shortest path from one to the other. Wiener [20] found a strong correlation between the boiling points of paraffins and the Wiener index. From then on, many other topological (using the information of the chemical graph) and topographical (using the information of the chemical graph and the location of its vertices in space) indices were introduced and their correlation with various other biological activities was investigated.
In Combinatorial Chemistry, drug design is facilitated by building libraries of molecules that are structurally related (via the Wiener index or any of the other numerous indices). We face inverse problems where the goal is to design new compounds that have a prescribed structural information (see also [6]).
Goldman et al. [12] study problems related to the design of combinatorial libraries for drug design from an algorithmic and complexity-theoretic point of view, following the heuristic approaches of [18] and [11]. Goldman et al. show that for every positive integer W , except 2 and 5, there exists a graph with Wiener index W . They also show that every integer, except a finite set, is the Wiener index of some tree. For constructing a tree (of unbounded or bounded maximum degree) with a given Wiener index, they devise pseudo-polynomial dynamic programming algorithms. Goldman et al. also introduce the Splits Reconstruction problem and recall a result due to Wiener [20]: the Wiener index of a tree T on n vertices with unit weights is s∈S(T ) s · (n − s). They show that SR is NP-complete and give an exponential-time algorithm without running time analysis.
As it is not reasonable to construct chemical trees with arbitrarily high vertex degrees, Li and Zhang [16] studied SR 4 and showed that it is also NP-complete. Their algorithm to construct a tree with maximum degree at most 4 to solve SR 4 runs in exponential time (no running time analysis is provided) and creates weighted vertices in intermediate steps.
In order to reconstruct glycans or carbohydrate sugar chains, Aoki-Kinoshita et al.
[1] study the reconstruction of a node-labeled supertree from a set of node-labeled subtrees. They give a 6-approximation algorithm for this problem, which generalizes the smallest superstring problem.
We refer to [4] surveying results on the Wiener index for trees. Our Results. By the result of Li and Zhang [16], SR 4 is NP-complete, while SR 2 is trivially in P. We close this gap by showing that SR 3 is NP-complete by a reduction from Numerical Matching with Target Sums (defined below). It is even NP-complete for caterpillars with unbounded hair length. Identifying small classes of trees for which the problem is NP-complete may be important for future investigations in the spirit of the deconstruction of hardness proofs [15] which aim at identifying parameters for which the problem becomes tractable when these parameters are small.
Our main result proves that WSR 2 is strongly NP-complete by a reduction from a variant of Numerical Matching with Target Sums in which all integers of the input are distinct. For the case where the weights of the vertices are chosen from a small set of values, our dynamic-programming algorithm solves WSR 2 in time O(n k+3 · k), where k is the number of distinct vertex weights. Although this running time is polynomial for every constant k, the degree of the polynomial depends on k. Thus, the running time becomes impractical, even for small values of k. Parameterized complexity [5,8,17] is a theoretical framework that allows to distinguish between running times of the form f (k)n g(k) where the degree of the polynomial depends on the parameter k and running times of the form f (k)n O(1) where the exponential explosion of the running time is restricted to the parameter only. The fundamental hierarchy of parameterized complexity classes is where a parameterized problem is in FPT (fixed-parameter tractable) if there is a function f such that the problem can be solved in time f (k)n O(1) , a problem is in XP if there are functions f, g such that the problem can be solved in time f (k)n g(k) , and W[t], t ≥ 1, are parameterized intractibility classes giving strong evidence that a parameterized problem that is hard for any of these classes is not in FPT. Our algorithm for WSR 2 parameterized by the number of distinct vertex weights places this problem in XP. A generalization of this problem is W[1]-hard [7], but it remains open whether this problem is fixed parameter tractable. As a relevant parameter for SR we identified k, the number of leaves in the reconstructed tree. This parameterization of SR can be solved in time O(8 k log k · n), and is thus fixed-parameter tractable. Definitions. A caterpillar is a tree consisting of a path, called its backbone, and paths attached with one end to the backbone. Its hair length is the maximum distance (in terms of the number of edges) from a leaf to the closest vertex of the backbone. A star K 1,k is a tree with k leaves and one internal vertex, called the center. In our hardness proofs, we reduce from the following problem (problem [SP17] in [9]).
Numerical Matching with Target Sums (NMTS): Given three disjoint multisets A,B, and S = {s 1 , . . . , s m }, each containing m elements from N, can A ∪ B be partitioned into m disjoint sets C 1 , C 2 , . . . , C m , each containing exactly one element from each of A and B, such that, for 1 ≤ i ≤ m, c∈Ci c = s i ?
Organization. The remainder of this paper is organized as follows. Section 2 shows that WSR 2 is NPcomplete. On the positive side, we show in Section 3 that WSR 2 can be solved in polynomial time when the number of distinct vertex weights is bounded by a constant. That this result cannot be extended to WSR 3 is shown in Section 4: SR 3 remains NP-complete. Section 5 gives an FPT-algorithm for SR parameterized by the number of leaves of the reconstructed tree. The variant where the vertex weights are freely choosable is discussed in Section 6 and we conclude with some directions for future research in Section 7.

WSR is strongly NP-complete
In this section, we show that WSR 2 is strongly NP-complete. First we introduce a new problem that is polynomial-time-reducible to WSR 2 , and then show that this new problem is strongly NP-hard.
Scheduling with Common Deadlines (SCD): Given n jobs with positive integer lengths j 1 , . . . , j n and n deadlines d 1 ≤ . . . ≤ d n , can the jobs be scheduled on two processors P 1 and P 2 such that at each deadline there is a processor that finishes a job exactly at this time, and processors are never idle between the execution of two jobs?
To reinforce the intuition on this problem one may imagine that we want to satisfy delivery deadlines and avoid using any warehouse space to store a product between its fabrication and the delivery date. There is no restriction as to which product should be delivered at a given time. (Another possibility is imagining computer scientists scheduling paper production to fit conference deadlines.) Given an instance (j 1 , . . . , j n , d 1 , . . . , d n ) for SCD, we construct an instance for WSR 2 as follows. For each job j i , 1 ≤ i ≤ n, create a vertex v i with weight ω(v i ) = j i . For each deadline d i , 1 ≤ i ≤ n − 1, create a split d i . We may assume that n i=1 j i = d n−1 + d n , otherwise we trivially face a No-instance. Suppose the path P = (v π(1) , v π(2) , . . . , v π(n) ) is a solution to WSR 2 . Say {v π( ) , v π( +1) } is the edge associated to the split d n−1 . We construct a solution for SCD by assigning the jobs j π(1) , j π(2) , . . . , j π( ) to processor P 1 , and the jobs j π(n) , j π(n−1) , . . . , j π( +2) , j π( +1) to processor P 2 , in this order. Note that then, one of the jobs j π( ) , j π( +1) ends at d n−1 , and the other at −d n−1 + n i=1 j i = d n , which is as desired.
On the other hand, if SCD has a solution, then WSR 2 has a solution as well, because the previous construction is easily inverted. Visually, the list of jobs of P 2 is reversed and appended to the list of jobs of P 1 . Job lengths correspond to vertex weights and deadlines correspond to splits (the last deadline where a job from P 1 finishes is merged with the last deadline where a job from P 2 finishes). Thus, SCD is polynomial-time-reducible to WSR 2 .
In the remainder of this section, we show that dNMTS is polynomial-time-reducible to SCD. The dNMTS problem is equal to the NMTS problem, except that all integers in A ∪ B ∪ S are pairwise distinct. This variant has been shown to be strongly NP-hard by Hulett et al. [14]. As the proof becomes somewhat simpler, we use dNMTS instead of NMTS for our reduction.
Let us first give a high level description of the main ideas of the reduction. For a dNMTS instance (A, B, S), the elements of A∪B will be encoded as jobs, and the elements of S will be encoded as deadlines. A convenient way to represent an element s ∈ S is by introducing segments which are delimited to the left and the right by double deadlines, and whose distance is equivalent to s. The elements of A ∪ B ∪ S are blown up by well-chosen additive factors that preserve solutions and make sure that the length of each segment can only be met by the sum of exactly two job-lengths, one corresponding to an element of A and the other to an element of B.
Our reduction will create an instance whose solution assigns, in each segment, one x-job (a job corresponding to an A-element) and one y-job (a job corresponding to a B-element) to the same processor, such that these two jobs are the only jobs executed on this processor in this segment, thus providing a solution to dNMTS. Without loss of generality, the x-job is scheduled first. As we must not introduce any restriction which x-jobs can be assigned to which segments, we introduce a deadline for each length of an x-job; these are the real deadlines. We refer to the x-and y-jobs as green jobs. The job lengths were blown up such that in each segment, exactly one processor starts with a green x-job, and in each segment, exactly one processor ends by executing a green y-job. In each segment, the green jobs must not overlap; this is achieved by multiplying all deadlines created so far and the corresponding job lengths by a factor 2, and introducing fake deadlines at odd positions one unit before the real deadlines. If an x-job and a y-job overlapped, there would be no job ending at the fake deadline preceding the real deadline at which the x-job ends, as all green jobs have even length and all real deadlines and double deadlines are even. Blue, red, and black jobs are created to meet all deadlines on the processor that is not currently executing green jobs. The blow-up of the elements of A ∪ B ∪ S ensures that these jobs cannot equate the green jobs (except the black jobs whose lengths might equal the lengths of green y-jobs, but, without loss of generality, one can assign them to the last part of each segment of the processor not executing a green job). That none of these jobs is executed between two green jobs within a segment is ensured as the sum of all green job lengths equals the sum of the lengths of the segments. This summarizes the reduction and gives the reasons for the different elements of the construction. Let us now turn to the formal reduction.
Property 1. Each element of X ∪ Y ∪ Z is an even positive integer.
Property 2. For every i ∈ {1, . . . , n − 1}, we have that x i < x i+1 , that y i < y i+1 , and that z i < z i+1 .  Figure 1: How jobs are assigned to processors in the SCD instance in segment j < n.
In particular, Property 3 implies that y 1 > x n , that z 1 > y n , and that 2 · y 1 > z n . Properties 1-3 easily follow by construction of X, Y , and Z.
Property 4. If k and are integers such that x k + y = z n , then k = = n.
Property 4 holds because x n and y n are the only elements of X and Y , respectively, that are large enough to sum to z n .
By Property 3, the sum of any two X-elements is smaller and the sum of any two Y -elements is larger than any element of Z.
To illustrate these definitions, we start by showing that if we have a Yes-instance (X, Y, Z) for dN-MTS, then we have an SCD Yes-instance as well. Let C 1 , C 2 , . . . , C n be n couples such that C j = {x π1(j) , y π2(j) } and x π1(j) + y π2(j) = z j , j ∈ {1, . . . , n}, for two permutations π 1 and π 2 of the set {1, . . . , n}. We construct a solution for SCD. Let us construct the schedules for P 1 and P 2 . For each j ∈ {1, . . . , n − 1}, • assign the green x-job x π1(j) to the interval [ds 1,j−1 , r π1(j),j−1 ] of P 1 , • assign the green y-job y π2(j) to the interval [r π1(j),j−1 , ds 1,j ] of P 1 , • assign a red fill job of length • assign a red overlap job of length • assign a black fill job of length z j − x n to the interval [r n,j−1 , ds 1,j ] of P 2 .
It only remains to assign jobs to the last segment. The last segment of P 1 contains the green x-job x n and the green y-job y n , in this order. The last segment of P 2 contains a red fill job of length x 1 − 1, a blue job, a red fill job of length x 2 − 1 − x 1 , a blue job, . . ., a red fill job of length x n − 1 − x n−1 , and the black overlap job, in this order. See Fig. 1 for an illustration.
Now suppose the SCD instance is a Yes-instance. We will show some structural properties of any valid assignment of jobs to the processors, which will help to extract a solution for our original dNMTS instance. We will show that in each segment I j , any valid solution for the SCD instance has exactly one green x-job x k and exactly one green y-job y , and that x k and y sum to z j .
Consider a valid assignment of the jobs to the processors P 1 and P 2 . As two jobs with the same length are interchangeable, when we encounter a job whose length belongs to more than one category (for example "black fill" and "green y") we may choose in this case, without loss of generality, to which category the job belongs.
Proof. Let j ∈ {0, . . . , n − 2}. Two jobs must finish at the double deadline ds 1,j+1 , ds 2,j+1 . One of these must start at r n,j and thus has length ds 1,j+1 − r n,j = j+1 k=1 z k − x n − j k=1 z k = z j+1 − x n . So this job is, without loss of generality, a black fill job.
This uses up all black fill jobs.
Claim 2. The green y-job y n is assigned to the interval [r n,n−1 , ds 1,n ].
Proof. As in the previous proof, one job must be assigned to this interval, whose length is n k=1 z k − x n − n−1 k=1 z k = z n − x n , which is y n by Property 4. Thus, the green y-job y n is assigned to the interval [r n,n−1 , ds 1,n ].
Claim 3. The black overlap job is assigned to the interval [f n,n−1 , ds 1,n ].
Proof. As r n,n−1 is the only deadline between f n,n−1 and ds 1,n , the processor that does not use this deadline needs to process a job finishing at ds 1,n and starting before r n,n−1 . This is the black overlap job, since no other job is long enough. It is assigned to the interval [f n,n−1 , ds 1,n ] of length ds 1,n −f n,n−1 = z n − x n + 1.
This uses up all black jobs. Now, the only jobs left whose length is between 6b m + 12 and 8b m + 14 are the green y-jobs y 1 , . . . , y n−1 . Proof. Each job is assigned to an interval inside some segment, as the double deadlines prevent jobs to span more than one segment. Suppose the green y-job y is assigned to segment p. As ds 1,p + y > ds 1,p + x n , by Properties 2 and 3, and the deadline following r n,p = ds 1,p + x n is ds 1,p+1 , it must be that the green y-job y finishes at ds 1,p+1 . Moreover, ds 1,p+1 − y is equal to a real deadline as ds 1,p+1 − y is even.
Each of the 2n jobs that have been assigned so far finish at a double deadline ds 1,j , ds 2,j . Thus, no other jobs may end at a double deadline.
Claim 5. A red fill job of length x 1 − 1 is assigned to each interval [ds 1,j , f 1,j ] with 0 ≤ j ≤ n − 1.
Proof. Since both processors finish a job at deadline ds 1,j (respectively, are initialized at time ds 1,0 = 0) and one of them finishes a job at the following deadline, which is f 1,j , we need to assign a job of length f 1,j − ds 1,j = x 1 − 1 to the interval [ds 1,j , f 1,j ]. Without loss of generality, this is one of the red fill jobs of length x 1 − 1.
This uses up all red fill jobs of length x 1 − 1. Proof. Suppose the green x-job x is assigned to segment p. Notice that x > r n,p − f 1,p . Indeed r n,p − f 1,p = x n − x 1 + 1 and, by construction, x n − x 1 + 1 ≤ 2b m , whereas x ≥ 2b m + 4. Moreover, r n,p is the latest deadline in p. So the green x-job x starts at ds 1,p . Notice that ds 1,p + x < ds 1,p+1 and that ds 1,p + x corresponds to a real deadline as ds 1,p + x is even, but all fake deadlines are odd.
By Claims 2, 4, and 6, and since we have the same amount of segments as green x-jobs, respectively green y-jobs, we obtain that each segment I j , 1 ≤ j ≤ n,, contains exactly one green x-job and exactly one green y-job.
Claim 7. For j ∈ {1, . . . , n}, the green x-job and the green y-job in the segment I j do not overlap.
Proof. Suppose otherwise, that is, suppose there is a j ∈ {1, . . . , n} such that I j contains a green x-job, say x , and a green y-job, say y k , that overlap (i.e. the intervals they are assigned to overlap). Since x ends at a real deadline by Claim 6 and y k starts at a real deadline by Claim 4, no job ends at the fake deadline situated at ds 1,j−1 + x − 1, which contradicts the validity of the SCD solution.
The last claim implies that in each segment I j , 1 ≤ j ≤ n, there is a green x-job x j and a green y-job y kj which together have the same size as the interval. Hence the couples C j = {a j , b kj }, 1 ≤ j ≤ n, form the desired solution of dNMTS. Thus, we have the following lemma.
We have assembled enough information to prove our main theorem. Theorem 4. WSR 2 is strongly NP-complete.
Proof. The theorem follows from the strong NP-hardness of dNMTS, Lemmas 2 and 3, and the membership of WSR 2 in NP, which is easily verified as the certificate is a path and an assignment of the splits to its edges, all of which can be encoded in polynomial space.

Corollary 5. Splits Reconstruction for Caterpillars of Unbounded Hair-Length and Maximum Degree 3 is NP-complete.
Proof. It is clear that this problem, abbreviated SRC, is in NP. To show that it is hard for NP, we reduce from WSR 2 . Let I P = (ω 1 , . . . , ω n−2 , s 1 , . . . , s n−3 ) be an instance of WSR 2 , where ω i , 1 ≤ i ≤ n − 2, are the vertex weights and s j , 1 ≤ j ≤ n − 3, are the splits. We assume that all vertex weights and splits are upper bounded by a polynomial in n; as WSR 2 is strongly NP-hard, it is still NP-hard with this restriction. Define Ω := 1 + 2 · max{ω i : 1 ≤ i ≤ n − 2}. To simplify the argument, consider an auxiliary instance I P = (ω 1 , . . . , ω n , s 1 , . . . , s n−1 ) of WSR 2 obtained from I P by: • augmenting the values of s j , 1 ≤ j ≤ n − 3, by Ω, • adding ω n−1 = ω n = Ω to the multiset of weights, • adding s n−2 = s n−1 = Ω to the multiset of splits, • and finally, multiplying each value in I P by nΩ (so, for 1 ≤ i ≤ n−3, ω i = ω i nΩ, and s i = (s i +Ω)Ω).
It is not difficult to see that I P and I P are equivalent. Now let us create an instance I C of SRC in the following way.
Notice that there are n i=1 ω i vertices and ( n i=1 ω i ) − 1 splits (i.e. edges) in total. As one easily checks, if I P has a solution then I C has a solution. Now suppose I C has a solution C. Then, as C is an instance for SRC, it follows that C is a caterpillar of maximum degree 3 (with unbounded hair-length). Call B the backbone of C. Let B ⊆ B be maximal such that its endvertices have degree 3.
By construction s i > 1, 1 ≤ i ≤ n − 1, and only the splits s 1,i , 1 ≤ i ≤ n, have value 1. There are exactly n such splits, and so, C must have exactly n leaves.
Since there is no split of value nΩ 2 + 1, each hair of C has length at most nΩ 2 . So, as s i > nΩ 2 for i = 1, . . . n − 3, we obtain that the splits s 1 , ..., s n−3 are assigned to edges b 1 , . . . , b n−3 in E(B ). Observe that the edges b 1 , . . . , b n−3 induce a connected graph (i.e. a path), as all other splits are smaller than the minimum of the s i , i = 1, . . . n − 3.
Let P be the path formed by the edges b 1 , . . . , b n−3 and let u and v be the two endpoints of P . There is at most one vertex y such that if we look at the values of the splits of the edges from u to y (resp. from v to y), then they are strictly increasing. In addition, if two edges of P share a vertex x, x = y, then there must be a hair attached to x, because the splits associated to these two edges differ by more than 1. Furthermore, there are hairs H 1 and H 2 of length nΩ 2 attached to the first and to the last vertex on the backbone, as no two auxiliary splits are large enough to add up to one of the original splits s i , i = 1, . . . n − 3. From the fact that C has exactly n leaves, it follows that the remaining hair has to be attached to y. As a consequence, E(B ) = {b 1 , . . . , b n−3 }.
Let B be equal to B augmented with the two edges to which the splits of value nΩ 2 are assigned. All edges outside B (that is, edges from hairs) belong to auxiliary splits. This means that the edges adjacent to B correspond to auxiliary splits s ωi−1,i .
In order to find a solution for I P , it thus suffices to take B and replace all hairs with the corresponding weight on their starting vertex on B .

Algorithm for WSR 2 with few distinct vertex weights
Let k = |{ω(v) : v ∈ V }| denote the number of distinct vertex weights in an instance (V, ω, S) for WSR 2 . In this section, we exhibit a dynamic programming algorithm for WSR 2 that works in polynomial time when k is a constant. Moreover, standard backtracking can be used to actually construct a solution, if one exists.
Our dynamic programming algorithm computes the entries of a boolean table A. The table A has an entry A[p, W L , W R , v 1 , v 2 , . . . , v k ] for each integer p with 1 ≤ p ≤ n − 1, each two integers W L , W R ∈ S, and each v i ∈ {0, 1, . . . , m i }, where i ∈ {1, 2, . . . , k}. The entry A[p, W L , W R , v 1 , v 2 , . . . , v k ] is set to true iff there is an assignment of the splits s 1 , s 2 , . . . , s p to the leftmost edges and the r rightmost edges of the path P n on n vertices, such that • p = + r; • v 1 weights w 1 , v 2 weights w 2 , . . . , and v k weights w k are assigned to the leftmost and the r rightmost vertices of P n such that each split assigned to the left (respectively to the right) part of the path corresponds to the sum of the vertex weights assigned to vertices to the left (respectively to the right) of this split; and • W L is equal to the value of the th split from the left and W R is equal to the r th split from the right.
Intuitively, our algorithm assigns splits and weights by starting from both endpoints of the path and trying to join these two sub-solutions. For the base case, set . . = v k = 0 and to false otherwise. We compute the remaining entries of A by increasing values of p using the following recurrence.
In the previous recurrence, the formulas that refer to table entries that are undefined have the value false.
The final result of the algorithm is computed by evaluating the expression Theorem 6. WSR 2 can be solved in time O(n k+3 · k), where k is the number of distinct vertex weights of any input instance (V, ω, S) and n is the number of vertices.
Proof. The correctness of the base case is clear. For the correctness of the recurrence, let v pivot be the vertex on P n where the two sub-solutions corresponding to the left and to the right part of P n meet. First note that the values of the splits increase from left to right until we encounter vertex v pivot , from which point they decrease. Filling up the path from both ends, this means that reading the splits from s 1 to s n−1 , we can assign them to the path, each time only deciding whether we assign it to the left part or to the right part of the path (in the SCD model, this would be equivalent to deciding whether to meet the next deadline on the processor P 1 or on the processor P 2 ). The first (respectively second) case of the recurrence corresponds to assigning the next split to the left (respectively right) part of the path by inserting a vertex of weight w i , i ∈ {1, 2, . . . , k}. The correctness of the final evaluation follows because it inserts the one missing vertex weight that has not been used between the left and the right part of the path.
The table has |S| 3 · Π k i=1 (m i + 1) ≤ n k+3 entries, each entry can be computed in time O(k), and the final evaluation takes time O(n · k).

SR 3 is NP-complete
In this section we show that Splits Reconstruction with unit weights is NP-complete for trees with maximum degree 3. Our polynomial-time reduction is done from the strongly NP-complete NMTS problem recalled in Section 1. This problem remains NP-complete even if each integer of the NMTS instance is at most p(m), where p is a polynomial and m is the length of the description of the instance. Let us just mention that the next theorem does not immediately follow from Corollary 5. instance: Let b i be the number of vertices in the set V ; we recall that these vertices have unit weight. The multiset S of splits is defined as follows.
• For each value s i , 1 ≤ i ≤ m, the value 1 + s i is added to S and we refer to these splits as red splits.
• For each value s i , 2 ≤ i ≤ m − 2, the value (i − 1) + i j=1 (1 + s j ) is added to S and we refer to these splits as black splits.
• For each value a i , 1 ≤ i ≤ m, the values {1, 2, . . . , a i } are added to S and we refer to these splits as green splits.
• For each value b i , 1 ≤ i ≤ m, the values {1, 2, . . . , b i } are added to S and we refer to these splits as blue splits.
Finally each value x of S is replaced by min(x, n − x). As required, S contains n − 1 splits. Proof. Throughout the proof, when we refer to a split of value x, we mean a split of value min(x, n − x).
"⇒" Assume that (A, B, S) is a Yes-instance for NMTS. We will show that there is a solution to SR 3 . A tree T = (V, E) and a bijective function b : E → S can be constructed as follows (see also Figure 2). Construct a path P with m − 3 edges with the black splits such that the (i − 1) th edge is associated to the black split (i − 1) + i j=1 (1 + s j ), i ∈ {2, 3, . . . , m − 2}. Add two edges incident to the first vertex of P , that are associated to the red splits 1 + s 1 and 1 + s 2 . Add two edges incident to the last vertex of P that are associated to the red splits 1 + s m−1 and 1 + s m . To the i th vertex of P , 2 ≤ i ≤ m − 3, add one incident edge associated to the red split 1 + s i+1 . Finally, for each a i ∈ A and each b i ∈ B, construct the paths with a i and b i vertices respectively. To each edge of these 2m paths, we can associate a green or a blue split. It remains to attach one green path and one blue path to each endpoint of an edge associated to a red split (one endpoint is already involved in the path P and of degree 3). The way to attach these path is given by the solution to the (A, B, S) instance.
"⇐" Assume that there exists a solution (T, b) to SR 3 , where T = (V, E) is a tree of maximum degree 3 and b is a bijection from E to S. We show how a solution of the NMTS instance (A, B, S) can be derived from (T, b). Let us note that for any i, j, k ∈ {1, 2, . . . , m}, we have that a i + s j > s k , that a i + a j < s k , that b i + b j > s k , and that a i + a j > b k . Claim 8. For every i ∈ {1, 2, . . . , m}, there is a path on a i edges, called the a i -path, using the splits 1, 2, . . . , a i (without loss of generality, they are green) and there is a path on b i edges, called the b i -path, using the splits 1, 2, . . . , b i (without loss of generality, they are blue). All these a-paths and b-paths are edge-disjoint.
Proof. As the instance has 2m splits of value 1, T has 2m leaves. Each of these leaves is incident to a green or blue split of value 1. As the instance also has 2m splits of each of the values 2, 3, . . . , 2 + 3C, the leaves of T are the starting points of 2m edge-disjoint paths P 1 , P 2 , . . . , P 2m , each having 2 + 3C edges in T . Consider an x ∈ A ∪ B and the splits 2 + 3C + 1, 2 + 3C + 2, . . . , x. As x < 4 + 6C, and as there is no split smaller than 2 + 3C other than those we have already used to form the paths P i , 1 ≤ i ≤ 2m, the splits 2 + 3C + 1, 2 + 3C + 2, . . . , x are assigned to an extension of a path P i , which, together with P i , forms a path P i with x edges using the splits 1, 2, . . . , x. All these paths P i , 1 ≤ i ≤ 2m, are edge disjoint and without loss of generality, green splits are assigned to their edges if they have at most 2 + 4C edges and blue splits otherwise.
Claim 9. For every i ∈ {1, 2, . . . , m}, the red split of value 1 + s i is assigned to an edge e i of T whose vertex u i is the common extremity of an a-path and a b-path, where u i is in the subtree of T − e i that has s i + 1 vertices.
Proof. As no split has value s i , vertex u i is incident to another two edges besides e i . We note that all splits, besides those of the a-and b-paths, have value at least 6 + 8C. One such split plus the smallest a j , 1 ≤ j ≤ m, would exceed s i . So, u i is the end point of two a/b-paths. These cannot be two a-paths as a j + a k < s i , for any j, k ∈ {1, 2, . . . , m} and they cannot be two b-paths as b j + b k > s i , for any j, k ∈ {1, 2, . . . , m}. Thus, u i is the common extremity of an a-path and a b-path.
Finally, a solution to the instance (A, B, S) of NMTS is formed by the couples C 1 , C 2 , . . . , C m , where each C i contains a ia and b i b , where i a and i b are such that the edge e i of T , with b(e i ) = 1 + s i , is incident to the a ia -path and the b i b -path. This proves the NP-hardness of SR 3 .
As the certificate is a tree on n vertices, the membership in NP is obvious and Theorem 7 is proved.

Algorithm for SR with few leaves
In this section we design an algorithm for SR parameterized by the number k of splits that are equal to one, i.e. k = |{s = 1 : s ∈ S}|. As each such split is incident to a leaf in a reconstructed tree, the algorithm reconstructs trees with k leaves.
The algorithm starts with a star T with center r and k leaves. The vertex r is also the root of T and r is the only vertex which is allowed to have non-unit weight during the execution of the algorithm. We start by setting ω(r) = n − k. The splits that are equal to 1 are assigned to the edges of the star.
At any stage of the algorithm, T is a tree with splits from S assigned to its edges, and the goal is to replace the root r of T by a tree T r with unit-weight vertices (except for the new root, that can have a non-unit weight), using splits from S that have not been assigned yet; the leaves of T r are made adjacent to the former neighbors of r in T . If there exists such a replacement where the splits form a subset of S, we say that T has a valid extension. Each tree T uniquely defines a partition (A, C, U ) of the splits S such that • A represents the multiset of available splits that have not yet been assigned to T , • C represents the multiset of current splits assigned to edges incident to r, and • U represents the multiset of used splits assigned to edges of T that are not incident to r.
Let b denote the value of the smallest split in C. Our tree T will grow out of r as follows.
• If ω(r) = 1, then return True. Indeed, T uses all splits from S as A is empty.
• If A contains a split whose value is at most b, then T has no valid extension and the algorithm backtracks. Indeed, on a path between two leaves in a valid tree, there is no split with value at most b between two splits with value at least b.
• If |{s ∈ A : s = b + 1}| > |{s ∈ C : s = b}|, that is, A contains more splits with value b + 1 than C contains splits with value b, then T has no valid extension and the algorithm backtracks. The correctness of this case holds by the pigeonhole principle and the argument used in the previous case.
• If |{s ∈ A : s = b + 1}| = |{s ∈ C : s = b}|, then all valid extensions of T are also valid extensions of the tree obtained from T by subdividing each edge with split b that is incident to r. That is, for each edge rv with a split of value b, add a new vertex z v , remove the edge rv, and add edges rz v and z v v. Decrement ω(r) by |{s ∈ C : s = b}|. The algorithm recursively solves the problem on this tree.
• Otherwise (if |{s ∈ A : s = b + 1}| < |{s ∈ C : s = b}|), some split from C with value b receives a parent split with value more than b + 1. Go over all choices for selecting a subset U of N (r) of size at least 2 containing a vertex v such that rv is associated with a split with value b. If A contains no split that equals 1 + u∈U s(ru), where s(e) denotes the split associated to the edge e of T , then discard this choice. Otherwise, create a new vertex z U , remove the edges {ru : u ∈ U } from T , add the edges {z U u : u ∈ U ∪ {r}}, and decrement ω(r) by 1. The algorithm resursively solves the resulting subproblems. If one such tree has a valid extension, T has a valid extension.
Theorem 9. SR can be solved in time O(8 k log k · n), where k = |{s = 1 : s ∈ S}| and n is the number of vertices.
Proof. The arguments for correctness have been given in the description of the algorithm. For the running time analysis, we observe that ω(r) decreases in each recursive call, no recursive call increases |C|, and the time spent in each recursion step is linear. Let T (c) denote an upper bound on the number of atomic instances solved for an instance with |C| = c ≤ k, where an instance is atomic if the algorithm makes no recursive call for solving the instance. In the only case making more than one recursive call, we have as the set U in the neighborhood of N (r) is replaced by one vertex z U . As c ≤ k and c i ≤ k i , we have that This maximum is attained for i = 2, which proves the theorem.

Freely choosable weights
We remark that the following modification of WSR makes any set of splits realizable in some tree. Suppose the weight function ω is not given, but freely choosable, that is, we ask whether, given a multiset S of integers, there exists a tree T = (V, E) and a weight function ω : V → N, such that S is the multiset of splits of T . We call this problem ChWSR. Proof. We show that the answer to ChWSR is always yes: Decompose S into κ chains s j 1 < s j 2 < . . . s j m(j) , j = 1, . . . , κ, where κ is the maximal multiplicity in S. Let T be obtained from the star K 1,κ by subdividing e j , the j th edge of T , m(j) − 1 times (for j = 1, . . . , κ), and root T at the center r of K 1,κ . Map s j i to the edges of the subdivided e j , 1 ≤ i ≤ m(j), keeping their order, so that the edge corresponding to s j 1 is incident to a leaf of T . Finally, choose the weight ω(r) for the root to be equal to the maximum value in S. For each leaf v of T , set the weight ω(v) equal to the split assigned to the edge {v, u}, where u is the parent of v. Any other vertex v is given a weight equal to the difference of splits assigned to the edges incident to v. This choice of T and ω clearly satisfies the requirements.
Remark. Due to the construction provided by the proof of Theorem 10, we note that we are not only always able to construct a tree T as required, but the structure of this tree is also rather simple. In particular, the realization of the split sequence is a path if each split in S repeats at most twice. Observe that if we consider ChWSR with unit weights, we are back at the problem SR. It is not difficult to see that in SR, a given set of splits can be realized in the same way as explained in the proof of Theorem 10 for ChWSR, the only difference being that each time a non-unit weight w is assigned to some vertex v in ChWSR, in SR we have to add w − 1 leaves of unit weight to v. Thus, if S contains a sufficient number of splits 1, then S can always be realized by a tree. More precisely, setting the boundary values s j 0 := 0 for all j, and letting κ denote the maximum multiplicity over all elements in S except 1, we have that if κ ≥ 2 and S contains at least times the split 1, then S can be realized by a tree T : κ of them are needed to be assigned to edges incident to leaves of the star, m(j) i=1 (s j i − s j i−1 − 1) of them are added, with pending vertices, to vertices introduced by subdividing the edge e j , and 2 · max κ i=1 {s i m(i) } − 1 − κ j=1 s j m(j) of them are added, with pending vertices, to the root. (Note that it does not matter if there are more splits 1 than needed in our construction, since we may always add leaves to the center of T .) The previous condition is, of course, sufficient, but not necessary. Moreover, the tree T that realizes S is a subdivided star to which some leaves have been added. In particular, if each split in S repeats at most twice, then we can realize S in a caterpillar with hair-length one. We note that the conditions κ = 2 and the lower bound on the number of splits with value 1 are also necessary for caterpillars with hair length one.

Conclusion
In Section 3, we have shown that WSR 2 is in XP when parameterized by the number of distinct vertex weights. It remains open whether this problem is fixed parameter tractable (a generalization of the problem is W[1]-hard [7]). For practical purposes, it would further be important to identify other quantities that are small in practice (e.g. the diameter of the tree or topological indices), and investigate the multivariate complexity of the considered problems parameterized by combinations of these quantities.
There is a large contrast between the complexities of WSR, where we are given n vertex weights, and ChWSR, where we can freely choose the vertex weights, or, alternatively, we can choose the vertex weights from an infinite multiset containing n times each element of N. It would be interesting to know some restrictions on the multiset of vertex weights such that the problem becomes polynomial time solvable, or fixed-parameter tractable with respect to interesting parameterizations, when we can chose the weights from this multiset. Ideally, these restrictions should be consistent with the applications in drug design and discovery.