Guillaume Bagan

Valentin Gledel

Marc Heinrich

Fionn Mc

Weighted Total Acquisition *

Keywords: Total acquisition, Complexity, Treewidth, Dynamic programming

come   L'archive ouverte pluridisciplinaire

Introduction

Data gathering is an essential capability of any type of wireless network. In general, all of the nodes of the network want to send their data to a particular node, typically known as a sink. In this process, nodes may act as intermediary sinks, in that, they collect data from many of the other nodes, and then, the intermediary sinks transfer their data to the destination or final sink. This process is known as multi-hopping. This all-to-one type of communication or data gathering protocol is called convergecast. Convergecast has been vastly studied and has found its applications in, e.g., wireless sensor networks (WSN) [START_REF] Gandham | Distributed time-optimal scheduling for convergecast in wireless sensor networks[END_REF][START_REF] Malhotra | Aggregation convergecast scheduling in wireless sensor networks[END_REF][START_REF] Shi | Convergecast scheduling for industrial wireless sensor networks with local available channel sets[END_REF], wireless body area networks (WBAN) [START_REF] Badreddine | Convergecast in wireless body area networks[END_REF][START_REF] Bu | Fifo order reliable convergecast in wban[END_REF], wireless ad hoc radio networks [START_REF] Kesselman | Fast distributed algorithm for convergecast in ad hoc geometric radio networks[END_REF], and vehicular networks [START_REF] Jiang | Improving throughput and fairness of convergecast in vehicular networks[END_REF].

In 1995, Lampert and Slater introduced the following convergecast model. In a graph G, each vertex v ∈ V (G) initially has a weight of 1, and a vertex x can transfer its total weight w(x) to a neighbouring vertex y if and only if w(x) ≤ w(y). Such a transfer is called an acquisition move, and when the context is clear, we will simply refer to it as a move or acquisition. When there are no more possible moves, the remaining set of vertices with non-zero weights is referred to as a residual set. The minimum cardinality of a residual set is called the total acquisition number of G and denoted by a t (G) [START_REF] Lampert | The acquisition number of a graph[END_REF]. The rule that a vertex may only transfer its weight to a neighbouring vertex with at least the same weight can be motivated by disjoint set data structures. For example, in the UNION-FIND data structure with linked lists, a smaller list should always be appended to a larger list to improve performance [START_REF] Bal | The total acquisition number of random graphs[END_REF].

Related Work

In 1995, in the seminary paper on the topic, Lampert and Slater proved that a t (G) ≤ n+1 3 for any connected graph G on n vertices and that this bound is sharp [START_REF] Lampert | The acquisition number of a graph[END_REF]. The graphs achieving this equality were then characterized in [START_REF] Lesaulnier | Acquisition-extremal graphs[END_REF]. In 2008, Slater and Wang proved that deciding whether a t (G) = 1 is NPcomplete [START_REF] Slater | Some results on acquisition numbers[END_REF]. Further studies on total acquisition have also been done for trees [START_REF] Lesaulnier | Total acquisition in graphs[END_REF], grids [START_REF] Macdonald | Total acquisition on grids[END_REF], and random graphs [START_REF] Bal | The total acquisition number of random graphs[END_REF][START_REF] Infeld | The total acquisition number of random geometric graphs[END_REF]. Work has also been done on a game variation of total acquisition [START_REF] Slater | The competitive-acquisition numbers of paths[END_REF] and variants where the total weight need not be transferred from vertex to vertex, but rather just a portion of it, see, e.g., [START_REF] Johnson | The unit acquisition number of a graph[END_REF][START_REF] Wenger | Fractional acquisition in graphs[END_REF].

In this paper, we consider the weighted total acquisition number of a weighted graph G with weight function w which contains only positive non-zero integer weights, denoted by a t (G, w), which is the minimum cardinality of a residual set when the vertices begin with their weight according to w. This is in contrast to the total acquisition number, in which all the vertices begin with weight 1, and makes for a much more realistic model since all the nodes would not necessarily begin with the same amount of data (see, e.g., [START_REF] Gandham | Distributed time-optimal scheduling for convergecast in wireless sensor networks[END_REF]). To the best of our knowledge, the only paper to have considered this variant is [START_REF] Godbole | The total acquisition number of the randomly weighted path[END_REF], a paper of Godbole et al. from 2017. In [START_REF] Godbole | The total acquisition number of the randomly weighted path[END_REF], they studied the possible sizes of residual sets obtainable for cliques, paths, cycles, wheels, and complete bipartite graphs. Their main focus, however, was studying a t (P n , w) (P n is a path on n vertices) when w is a random weight function. In particular, they gave bounds on the expected weighted total acquisition number of paths, and, given a weighting w, they described a simple polynomial-time greedy algorithm for finding a t (P n , w). The latter algorithm also shows that a t (C n , w) (C n is a cycle on n vertices) can be determined in polynomial time by testing all of the possible O(n) first acquisition moves and then applying the greedy algorithm to the path that remains.

Our Results

In this paper, we are interested in the complexity of computing the weighted total acquisition number for various classes of graphs. The complexity of the problem depends on whether the weights given in the input are encoded in unary or in binary. Our results include both positive and negative results for both versions of the problem. The paper is organized as follows. We start with some notations and formal definitions in Section 2. We first focus on our more positive results, and thus, we begin with the unary version of the problem in Section 3 as the problem is more tractable in this setting. In Subsection 3.1, we show that when the input weights are encoded in unary, there is a polynomial-time algorithm which computes the weighted total acquisition number on graphs with both bounded degree and bounded treewidth. When only the treewidth of the graph is bounded, the algorithm has a quasi-polynomial run time, i.e., it runs in time at most W O(log W ) , where W is the sum of the weights of the vertices. In particular, this implies that the problem can be solved in quasi-polynomial time on trees, showing that it is unlikely to be NP-hard on trees, unlike the binary version of the problem, as will be seen, e.g., in Subsection 4.1. Moreover, we show in Subsection 3.2, that the unary version of the problem is FPT when parameterized by the maximum degree of the tree. In other words, the problem can be solved on trees in time O(f (∆)W c ), for some computable function f and a constant c, where ∆ is the maximum degree of the graph. Finally, in Subsection 3.3, we show that even in its unary version, the problem remains NP-complete on trivially perfect graphs. Since trivially perfect graphs have clique-width at most 2, this proves in particular that the problem is not FPT when parameterized by the clique-width of the graph. On the contrary, when both the clique-width and the maximum degree are bounded, then the treewidth of the graph is also bounded, and the problem can be solved in polynomial time. Finally, deciding whether the weighted total acquisition number is one on split graphs is NP-complete, even in the unary version of the problem.

We then focus on the binary version of the problem in Section 4. For this version of the problem, most of our results are negative, showing that the problem is hard even for very restricted classes of graphs. In Subsection 4.1, we show that binary weighted total acquisition is NP-complete, even on trees of bounded degree and on trees of bounded depth. On the positive side, we prove that the problem is in XP on trees when parameterized by the weighted total acquisition number of the graph (i.e., a t (G, w) can be computed in polynomial time if it is upper bounded by a fixed constant). Since the problem is already difficult on trees, our focus for the rest of this section is on graphs which are even more simple, or on the case where the weighted total acquisition number of the graph is bounded. Unfortunately, our results are again mostly negative. We show in Subsection 4.2 that it is NP-complete to decide whether the weighted total acquisition number of K 3,n is equal to 1, where K 3,n is the complete bipartite graph with one side of the bipartition of size 3. In Subsection 4.3, we prove that deciding whether the weighted total acquisition number of a trivially perfect graph is 1 can be done in polynomial time, while deciding whether this number is at most 2 is NP-complete for this class, as well as for the class of planar graphs with pathwidth at most 2 (studied in Subsection 4.4) and unit-interval graphs. We also show, in Subsection 4.4, that computing the weighted total acquisition number of a wheel (i.e., a cycle plus a universal vertex) is NP-complete, but is also in XP when parameterized by the weighted total acquisition number of the graph.

Notations and Definitions

Graph theory

We start with some basic definitions and notations from graph theory (see [START_REF] Diestel | Graph Theory[END_REF] for a book on graph theory). A graph G = (V, E) is defined by a set of vertices V , and a set of edges E. Sometimes we will refer to V as V (G) and E as E(G), to make it clear that these are the sets of vertices and edges, respectively, of the graph G. Throughout this paper, every graph that we consider is undirected and simple. Moreover, all our graphs will be given a weight function w : V → N * which assigns weights to the vertices of the graph. Given two vertices u and v of a graph G, uv denotes the edge between u and v, and N G (v) = {u ∈ V, uv ∈ E} denotes the neighbours of v. If the graph G is clear from the context, then we will drop the subscript and simply write N (v) for the neighbourhood of v. A vertex is universal if it is adjacent to all of the vertices of the graph.

Given a graph G with a weight function w, the total weight of the graph G, denoted by W , is the sum of the weights of the vertices, i.e., W = v∈V (G)

w(v).

A tree decomposition of a graph G is a tree T whose nodes are each labelled with a subset of vertices of the graph G, and such that: for every vertex v, the nodes which contain v induce a subtree of T ; for every edge uv, there is a node of T that contains u and v in its label.

A tree decomposition has width k if the largest subset in the labels of T contains k+1 vertices. Trees are exactly the graphs of treewidth 1. The treewidth, tw(G), of a graph G, is the smallest value k such that G admits a tree decomposition of width k (see [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF] for a survey on the topic). If we restrict T to be a path, then we obtain another parameter called the pathwidth of the graph G.

Throughout the paper, we will consider several classes of graphs (see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF] for a survey on graph classes). Below, we give some formal definitions of these classes. A graph is an interval graph if each vertex can be represented by an interval on the real line such that two vertices of the graph are adjacent if and only if their corresponding intervals intersect. Unit interval graphs are a subclass of interval graphs, where each vertex is represented by an interval of the same length. Another subclass of interval graphs are the trivially perfect graphs. There are several ways to characterize this class, one way is to say that it has an interval representation such that any two intervals are either disjoint or one is included in the other. Another way to characterize this class is by the following property: Lemma 1. A graph is trivially perfect if and only if it is either: (i) a single vertex, (ii) the disjoint union of two trivially perfect graphs, or (iii) obtained by adding a universal vertex to a trivially perfect graph.

Another class of graphs that we will consider are split graphs, for which there is a partition of the vertices into an independent set and a clique. Interval graphs and split graphs are a subclass of chordal graphs, which are the graphs that do not contain any induced cycle of length four or more. Finally, planar graphs are graphs that can be drawn on the plane such that no two edges intersect.

Problem definition

Let us now give a formal definition of our problem. Given a graph G = (V, E), a weight function w is interpreted as the number of tokens on each of the vertices of G. An acquisition move consists in moving w(v) tokens from a certain vertex v to a neighbour u, provided that w(u) ≥ w(v). An acquisition sequence is a sequence of weight functions w 1 , . . . , w t such that w i+1 is obtained from w i by an acquisition move. Given an acquisition sequence, its residual set is the set of vertices which have at least one token at the end of the sequence, i.e., it is the set {v ∈ V, w t (v) > 0}. The cost of an acquisition sequence is the size of the residual set. Our problem consists in finding an acquisition sequence of minimum cost, i.e., which minimizes the size of the residual set. Formally, it has the following definition:

Weighted Total Acquisition problem (WTA) :

Input: A graph G with a weight function w, and an integer k ≥ 1. Question: Is there an acquisition sequence of cost at most k?

We will denote by a t (G, w) the (weighted) total acquisition number of G, which is the minimum cost of an acquisition sequence for the graph G with weight function w. Hence, the problem above consists in deciding whether a t (G, w) ≤ k or not. Note that the WTA problem is clearly in NP, and so this fact will be omitted from all of the (strongly) NP-completeness proofs.

Throughout this paper, we study the complexity of this problem, and, specifically, when the graph G is restricted to various classes of graphs. From a complexity point of view, it is important to specify whether the weights in the weight function given as input are encoded in unary or in binary. Since we have results for both versions of the problem, we will explicitly write Unary WTA (resp.

Binary WTA) when the input weights are encoded in unary (resp. binary). Some of our hardness results also apply to the case where the parameter k, the target cost for the acquisition sequence, is not given as input, but is instead a fixed constant. This variant of the problem is denoted by k-WTA.

A first observation concerning this problem is that there are several ways to encode a solution to the problem. The trivial way to represent a solution consists in simply giving the sequence of acquisition moves. However, there are other more simple ways to represent a solution, and the sequence of moves can also be recovered from these other representations.

The first alternative way to define a solution to the problem consists in giving, for every edge of the graph, how much weight is transferred along this edge (note that an edge can be used at most once in any acquisition sequence). Hence, a solution can be represented by a weight function f on the edges of the graph G. In the rest of the paper, when we use such a weight function f , we assume that the edges of G are oriented. More precisely, given two vertices u and v, f (uv) represents the number of tokens which are moved from u to v. This quantity can be negative if the tokens are moved from v to u, and, in particular, f (uv) = -f (vu). To avoid confusion, when considering a weight function on an edge, we will always specify the two endpoints unless it is clear from the context. We will also abuse notations, and sometimes write f (uv) for two vertices which are not adjacent, in which case the value is always zero.

Moreover, to simplify some notations, given a weight function f on the edges of G, we will denote by f + the function such that f + (uv) = max(0, f (uv)). Consequently, f + allows to count the number of tokens which are moved in a particular direction. Using this notation, for a given vertex v, the quantity

u∈N (v)
f + (uv) denotes the total number of tokens received by the vertex v from its neighbours. Note that not all weight functions correspond to valid acquisition sequences. A weight function f is a valid solution if there is an acquisition sequence where the number of tokens which are moved on a given edge is exactly the value of f on this edge. It is easy to check that a weight function f is a valid solution if and only if it satisfies the following local constraints for every vertex v of the graph: (P1) v gives tokens to at most one of its neighbours, i.e., there is at most one u ∈ N (v) with f (vu) > 0;

(P2) either v does not give tokens, or it gives as many as it received plus its own. In the latter case, we must have:

w(v) + x∈N (v) f (xv) = 0;
(P3) v must be able to acquire all the incoming weights. In other words, there is an ordering u 1 , . . . , u k of the neighbours of v, such that :

w(v) + j<i f + (u j v) ≥ f + (u i v).
Since the constraints that a solution f must satisfy are local, this representation is convenient for dynamic programming algorithms in the unary version of the problem. Note that specifying the number of tokens which are moved on the edges of the graph in the acquisition sequence is not strictly necessary, and it is sufficient to store which edges are used in the sequence (i.e., have a non-zero weight). This leads to the last way to encode a solution to the problem. An acquisition forest is a rooted spanning sub-forest F (i.e., all the trees in the forest are rooted) of the graph G such that every connected component of the forest has a weighted total acquisition number of 1. The root of each tree in the forest corresponds to the vertex in the component with remaining tokens at the end of the acquisition sequence, and the edges of the tree, oriented towards the root, tell us in which directions the tokens are moved along the edges. Consequently, with this representation, the cost of the acquisition forest is simply the number of connected components. It is easy to see that the three ways to represent a solution are equivalent: if we have only an acquisition forest, getting an acquisition sequence with the same cost can be done in polynomial time. Hence, when we devise algorithms to solve the WTA problem, the algorithm will compute the solution in one of the three forms, whichever is more convenient at the time.

Hardness reductions

All of our hardness results in the binary version are achieved by using reductions from the Partition problem, which asks whether a set of integers can be partitioned into two subsets of equal value:

Partition problem :

Input: A set S = {x 1 , . . . , x ℓ } with M = 1≤i≤ℓ

x i .

Question: Is there a partition (S 1 , S 2 ) of S such that

y∈S1 y = z∈S2 z = M 2 ?
This problem is a special case of another well-known problem called subset sum and is a known NP-hard problem when the values x i in the input are encoded in binary [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. However, if the values are written in unary, it can be solved using a simple dynamic programming algorithm [START_REF] Bellman | Dynamic Programming[END_REF]. Hence, this problem is not suitable in reductions which aim at proving that Unary WTA is NPhard. In this case, we will use the following problem instead:

3-Partition problem :

Input: A set S = {x 1 , . . . , x 3n } and an integer B such that

1≤i≤3n x i = n • B,
x = B for all 1 ≤ i ≤ n?
This problem was shown to be strongly NP-hard in [START_REF] Garey | Complexity results for multiprocessor scheduling under resource constraints[END_REF], i.e., the hardness holds even if the input is encoded in unary.

Unary WTA

We start with our more positive results, and thus, we begin by considering the unary version of the problem in this section since it is much more tractable than the binary version of the problem, as will be seen in Section 4. In particular, there are cases where a dynamic programming approach can be used to compute the weighted total acquisition number of the graph. In this section, we give two dynamic programming algorithms. The first one works for graphs of bounded treewidth, for which we show that if the maximum degree is also bounded, then there is a polynomial-time algorithm. On the other hand, if the maximum degree is not bounded, the algorithm still runs in time at most W O(log W ) , where W is the total sum of the weights, which shows in particular that the problem is unlikely to be NP-hard in this case. As will be seen in Section 4, this contrasts with our results for the binary version of the problem which we show is NPhard on trees, wheels, and planar graphs of bounded pathwidth, all of which are classes of graphs with bounded treewidth. Our second algorithm applies to trees and computes the weighted total acquisition number in time O(f (∆) • poly(W )), where f is a computable function, and ∆ is the maximum degree of the graph. This shows that the problem is FPT in trees when parameterized by the maximum degree of the tree.

On the negative side, we show that even in its unary version, the problem remains NP-complete in trivially perfect graphs. Moreover, even deciding if the weighted total acquisition number is equal to 1 is hard for split graphs.

Bounded treewidth

In this subsection, we devise an algorithm for graphs of bounded treewidth. Our result is the following: Theorem 1. The Unary WTA problem can be solved in graphs G of treewidth k in time at most W O(k min(∆(G),k+log W )) .

Note that this result gives a polynomial-time algorithm on bounded degree trees, and a quasi-polynomial-time algorithm for general trees, which shows that Unary WTA is unlikely to be NP-hard on trees, and on graphs of bounded treewidth in general. The question of whether the problem can be solved in polynomial time in general trees is still open.

Our algorithm will use a tree decomposition of the graph which has some additional properties. Recall that, given a graph G, a tree decomposition of G is given by a tree T , where each node of T is labelled by a subset of vertices of G, and each vertex induces a connected component of the tree. A tree decomposition is nice if T is rooted at a node labelled by the empty set, and every node a of the tree satisfies one of the following four cases: a is a leaf node and is labelled by the empty set; a is a delete node: it has exactly one child b, and the label of b is the label of a plus one vertex; a is an introduce node: it has exactly one child b, and the label of b is the label of a minus one vertex; a is a branch node: it has exactly two children with the same label as a.

It is known that if a graph has treewidth k, then a nice tree decomposition of width k can be computed in time 2 O(k 3 log k) • n [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF].

The main idea of our algorithm is to use dynamic programming on the tree decomposition of the graph to compute an optimal solution. More precisely, let T be a nice tree decomposition of the graph G. Given a node a of T , we will denote by T a , the subgraph of G induced by the vertices which appear in the labels of the descendants of a, and by S a , the label of a.

The algorithm will proceed by computing, for every node a, and every possible "configuration" of the solution on S a , the optimal cost of a solution of T a which agrees with this configuration on S a . These configurations describe how the solution we are searching for behaves on the vertices in S a . If the graph also had bounded degree, it would be enough to take as a configuration all the possible values taken by a solution function on the edges incident to S a . However, when the maximum degree is not bounded, this direct approach is too expensive, and we have to rely on other tools to consider all the possible solutions around S a . The ingredient consists in managing to regroup a certain number of partial solutions that can be completed in the same fashion.

More precisely, if we assume that some (but not all) of the edges around a vertex v have a fixed weight, we can ask how this partial solution can be extended to the remaining edges so that the weights around v satisfy the three conditions (P1), (P2), and (P3). The next subsection develops a tool to answer this question, and subsection 3.1.2 uses this tool to design a dynamic programming algorithm to compute the weighted total acquisition number for graphs of bounded treewidth.

Compact representation of a partial solution

In the rest of this subsection, we will identify a multiset of weights X = {x 1 , . . . , x k } with a weight function on the edges around some vertex v (the order of the elements in the multiset is not important), with the convention that positive weights correspond to transfers towards v, and negative weights are transferred from v to its neighbours. Hence, by abuse of notation, we will say that the multiset satisfies one of the properties (P1), (P2), or (P3) for weight w if the weight function f corresponding to this multiset satisfies these properties for a vertex v with w tokens on v. We will denote by X k W the set of all multisets of at most k elements of value at most W .

Given two multisets X = {x 1 , . . . , x l } and Y = {y 1 , . . . , y r }, let X ⊎Y be the union (with multiplicities) of X and Y : X ⊎ Y = {x 1 , . . . , x l , y 1 , . . . y r }. Our goal is to group together multisets which can be completed in a similar way.

In other words, we want to say that X and Y are similar if for all Z, X ⊎ Z satisfies the three properties (P1), (P2), and (P3) if and only if Y ⊎ Z also does. This could be made into a formal definition, but we will not need all the formalism for the algorithm, and instead focus only on the tools needed for the algorithm. Note that among the three properties, (P1) and (P2) are relatively simple, and consequently we will focus on (P3) in the rest of this subsection. Note that since the property (P3) does not depend on the number of tokens that the vertex v gives to its neighbours, we will assume without loss of generality that the multisets that we consider contain only non-negative elements.

The main property that we will need consists in observing that some of the weights in the multiset X can be grouped together, without losing any information on how X can be completed into a multiset which satisfies the property (P3). More precisely, we will consider multisets of pairs of integers (x, r) representing a group of weight, where x is the cost to acquire this group (i.e., the minimum value of an element in the group), and r is the total value that will be added to the vertex v when this group is acquired. Hence, a multiset of integers X = {x 1 , . . . x k } can be naturally converted with this extension into X = {(x 1 , x 1 ), . . . , (x k , x k )}. In the following, to make the distinction clear in the notation between multisets of integers and multisets of pairs of integers we will typeset the latter with a bold font.

The main advantage of this new notation is that we can apply the following simplification. Assume that X contains two pairs (x 1 , r 1 ) and (x 2 , r 2 ) such that x 1 ≤ x 2 ≤ x 1 + r 1 , then X can be replaced by Y, the multiset obtained from X by replacing these two pairs by (x 1 , r 1 + r 2 ). Indeed, the condition implies that as soon as the weight of the vertex v is sufficient to acquire the pair (x 1 , r 1 ), then the pair (x 2 , r 2 ) can be acquired immediately afterwards since v has a weight of at least x 1 before acquiring (x 1 , r 1 ) and a weight of at least x 1 +r 1 after acquiring it. This simplification will be denoted by X → Y, and we write X → * Y if Y is obtained from X by a (possibly empty) sequence of such simplifications. Moreover, Y will be called terminal if no such simplification can occur. Note that, since each time a simplification is made, the number of pairs in the multiset decreases by 1, these simplifications cannot occur indefinitely. Moreover, the following lemma shows that the order by which these simplifications are made is not important, since the terminal multiset that we obtain at the end is unique.

Lemma 2. Given a multiset of pairs X, there is a unique terminal value X * such that X → * X * .

Proof. The proof follows immediately by applying induction and using the following claim:

Claim 1. If we have X → Y 1 and X → Y 2 with Y 1 ̸ = Y 2 , then there exists Z such that Y 1 → Z and Y 2 → Z.
Proof of claim. Assume that the transformation X → Y 1 is made by simplifying the pairs (x 1 , r 1 ) and (x 2 , r 2 ), and the transformation X → Y 2 simplifies (x 3 , r 3 ) and (x 4 , r 4 ). If these pairs are all different, then we can simply take Z to be the sequence obtained from Y 1 by simplifying the pairs (x 3 , r 3 ) and (x 4 , r 4 ). Hence, we can assume without loss of generality that (x 1 , r 1 ) = (x 4 , r 4 ). Let Z be the multiset obtained from X by replacing these three pairs by (min(x 1 , x 2 , x 3 ), r 1 + r 2 + r 3 ). We want to show that Y 1 → Z and Y 2 → Z. There are four cases:

x 1 ≤ x 2 and x 1 ≤ x 3 , then from Y 1 , the two pairs (x 1 , r 1 + r 2 ) and (x 3 , r 3 ) can be replaced by (x 1 , r 1 +r 2 +r 3 ) since x 1 ≤ x 3 ≤ x 1 +r 1 ≤ x 1 +r 1 +r 2 by the assumption that X → Y 2 , and consequently, Y 1 → Z. By symmetry, we also have Y 2 → Z.

x 2 ≤ x 1 and x 3 ≤ x 1 , then we know that x 1 ≤ x 2 + r 2 and x 1 ≤ x 3 + r 3 , and hence,

x 3 ≤ x 1 ≤ x 2 + r 2 ≤ x 2 + r 1 + r 2 . Additionally, we have x 2 ≤ x 1 ≤ x 3 + r 3 ,
and since either x 2 ≤ x 3 or x 3 ≤ x 2 , it follows that, from Y 1 , the pairs (x 2 , r 1 + r 2 ) and (x 3 , r 3 ) can be simplified together to obtain Z, and hence, we have Y 1 → Z. By symmetry, we also have Y 2 → Z.

x 2 ≤ x 1 and x 1 ≤ x 3 , then x 2 ≤ x 3 , and

x 3 ≤ x 1 + r 1 ≤ x 2 + r 1 + r 2 .
Hence, the two pairs (x 2 , r 1 + r 2 ) and (x 3 , r 3 ) in Y 1 can be simplified, and Y 1 → Z. In a similar way, we have x 2 ≤ x 1 and x 1 ≤ x 2 + r 2 , and hence, the two pairs (x 2 , r 2 ) and (x 1 , r 1 + r 3 ) in Y 2 can be simplified, and hence, Y 2 → Z.

x 1 ≤ x 2 and x 3 ≤ x 1 , then this is symmetric to the case above. ⋄

We can thus define the function σ, which associates, to a given multiset of pairs of integers Y, the unique terminal Y * such that Y → * Y * . By extension, if X is a multiset of integers, then we write σ(X) = σ( X). Note that σ satisfies the following property that we will use several times during the proofs: Observation 1. For all multisets X and Y , the following equality holds:

σ(X ⊎ Y ) = σ(σ(X) ⊎ σ(Y )).
Another observation concerns the size of a terminal value, which explains why this representation can be used as a compressed way to represent a partial solution around a vertex: Proof. The fact that |σ(X)| ≤ |X| follows immediately from the fact that the simplification decreases the size of the multiset. Hence, we only need to show that |σ(X)| ≤ log W + 1. Let (x 1 , r 1 ), . . . , (x k , r k ) be the pairs in σ(X) ordered by increasing x i , and with k = |σ(X)|. We can assume that r i ≥ x i for all 1 ≤ i ≤ k since this property is true for X and is preserved by the simplification observation. Moreover, since σ(X) is terminal, then, for all 1 ≤ i < k, we also have that

x i+1 > x i + r i ≥ 2x i , from which it follows immediately that x k ≥ 2 k-1 . Since we also have x k ≤ W , this implies k ≤ log W + 1.
We can now describe how this simplification procedure is related to the property (P3). Proof. The result is proved by induction on the size of X. If X is empty, then the result is always true, and there is nothing to prove. Hence, we can assume that X contains at least one element.

First assume that X satisfies property (P3) for the weight w, and let us show that σ( X ⊎ {(0, w)}) = {(0, A)}. Let x 1 , . . . , x k be the elements of X in increasing order. Since X satisfies property (P3), then in particular it follows that x 1 ≤ w. Consequently, if Y = X \ {x 1 }, then there is a simplification from X ⊎ {(0, w)} to Ỹ ⊎ {(0, w + x 1 )}, and consequently σ( X ⊎ {(0, w)}) = σ( Ỹ ⊎ {(0, w + x 1 )}). Moreover, we know that for any 1 < i ≤ k we have:

(w + x 1 ) + 1<j<i x j = w + j<i x j ≥ x i .
Consequently, Y satisfies the property (P3) for the weight w + x 1 , hence using the induction hypothesis, it follows that σ( Ỹ ⊎ {(0, w

+ x 1 )}) = {(0, A)} where A = w + x 1 + y∈Y y = w + x∈X x.
Let us now prove the other direction and assume that σ( X ⊎ {(0, w)}) = {(0, A)}, and let us show that X satisfies the property (P3). Let x 1 = min(X), then we must have x 1 ≤ w. Indeed, if this was not the case, then the pair (0, w) could never be simplified with any of the other pairs, which would contradict the assumption that σ( X + {(0, w)}) contains a single pair. Hence, it follows that if Y = X \{x 1 }, then there is a simplification from X⊎{(0, w)} to Ỹ⊎{(0, w+x 1 )}. By consequence, it follows that σ( Ỹ ⊎ {(0, w + x 1 )}) = {(0, A)}, and using the induction hypothesis, this implies that Y satisfies the property (P3) for the weight x 1 + w. This means that for all 1 ≤ i ≤ k, we have:

w + j<i x j = w + x 1 + 1<j<i x j ≥ x i .
And since we also have x 1 ≤ w, then X satisfies (P3) for the weight w.

We now have all the tools that we need to describe the algorithm.

Algorithm

The algorithm proceeds using dynamic programming on the tree-decomposition of the graph G. Let a be a node in the tree decomposition of G, and S a , its associated bag. A configuration for the node a is a triple (g, α, µ) where:

g is a weight function on the edges of G[S a ], which represents the restriction of the solution to these edges; α is a function which associates, to each vertex v ∈ S a , an integer with 0 ≤ α(v) ≤ W representing the number of tokens v gives to one of its neighbours in T a \ S a (if any); µ is a function which associates, to each vertex v in S a , a terminal multiset with a size of at most min(∆(G), log(W ) + 1). The value µ(v) represents how a solution behaves on the edges of the form v i u with u ∈ T a \ S a .

Note that the upper bound on the length of the values µ(v) in the configuration follows from the fact that larger multisets cannot occur due to the upper bound on the length of values of the form σ(X) given by Observation 2. We will denote by C a , the set of configurations for the node a. Note that, by definition, we immediately have the following:

Observation 3. The number of configurations of a node a is at most |C a | ≤ W O(tw(G) min(∆(G),tw(G)+log W ))
for any node a.

Proof. Note that since there are at most tw(G) min(tw(G), ∆(G)) edges in G[S a ], then there are at most (2W + 1) tw(G) min(tw(G),∆(G)) possible values for g. Similarly, there are at most (W +1) tw(G)+1 possible values for α. Lastly, for each vertex v in S a , µ(v) is a multiset of size at most min(∆(G), log W + 1), and each element in the multiset is a pair of integers between 0 and W . Therefore, there are at most (W + 1) 2(tw(G)+1) min(∆(G),log W +1) possible values for µ. All in all, this gives an upper bound of

W O(tw(G) min(tw(G),∆(G))+tw(G) min(∆(G),log W )) = W O(tw(G) min(∆(G),tw(G)+log W ))
for the number of possible configurations.

A weight function f on the edges of T a is a partial solution for T a if it satisfies the property (P1) for all the vertices in T a , and properties (P2) and (P3) for all vertices in T a \ S a . We denote by F a the set of partial solutions for T a . A partial solution for T a is compatible with a given configuration (g, α, µ) of a if:

(C1) f | Sa = g; (C2) for all v ∈ S a , we have α(v) = u∈Ta\Sa f + (vu) (note that at most one term in this sum can be positive). (C3) for all v ∈ S a we have µ(v) = σ({f (uv i ), u ∈ N G (v) ∩ T a \ S a }).
Note that these configurations define a partition of the set of partial solutions F a . Indeed, it is clear that a partial solution f cannot be compatible with more than one configuration, and also, f is always compatible with the configuration c a f = (g f , α f , µ f ), where g f , α f , and µ f are taken such that the three conditions above are satisfied.

The cost of such a weight function f will be the number of sinks for f in T a \ S a . The algorithm will proceed using dynamic programming by computing, for every node a of the tree decomposition and every configuration c of the node, the minimal cost of a weight function f compatible with this configuration, with the convention that this cost is +∞ if no such weight function exists. The result computed by the algorithm will be denoted by cost(a, c). The algorithm is the following:

Input:

a: a node of the tree decomposition c = (g, α, µ) a configuration of a. Output: cost(a, c), the minimum cost of a solution compatible with c.

1. a is a leaf node: return 0. result

← +∞ Iterate over all (c 1 , c 2 ) ∈ C b1 × C b2 . 2.1. (g i , α i , µ i ) ← c i for i ∈ {1, 2} 2.2. Discard (c 1 , c 2 )
and continue if one of the following does not hold: i.

g 1 = g 2 ii. ∀v ∈ S a , α(v) = α 1 (v) + α 2 (v) iii. ∀v ∈ S a , µ(v) = σ(µ 1 (v) ⊎ µ 2 (v)) iv. ∀v ∈ S a , α 1 (v)α 2 (v) = 0 2.3. result ← min(result, cost(b 1 , c 1 ) + cost(b 2 , c 2 )) return result.
3. a is a delete node with child b, and v is the deleted vertex.

result

← +∞ Iterate over all c ′ = (g ′ , α ′ , µ ′ ) ∈ C b 3.1. X v ← {g ′ (uv), u ∈ S a \ v} 3.2. β v ← α ′ (v) + u∈Sa g ′+ (vu)
3.3. Discard c ′ and continue if one of the following does not hold: i.

g ′ | G[Sa] = g ii. ∀u ∈ S a , α(u) = α ′ (u) + g ′+ (uv) iii. ∀u ∈ S a , µ(u) = σ(µ ′ (u) + {(y, y)}) with y = g ′+ (vu) iv. σ(µ(v) ⊎ Xv ) = {(0, r)} for some r v. β v ∈ {0, r} 3.4. result ← min(result, cost(b, c ′ ) + 1 βv=0 ) return result 4.
a is an introduce node with child b, and v is the introduced vertex.

4.

1. If α(v) > 0 or µ(v) ̸ = ∅, then return +∞ 4.2. return cost(b, (g| S b , α| S b , µ| S b ))
The algorithm then returns cost(r, ∅) where r is the root of the tree decomposition.

Proof of Theorem 1. To prove the theorem, it only remains to show that the algorithm described above is correct and has the desired runtime.

Correctness. To prove that the algorithm is correct, we will first show that for all nodes a, and all configurations c of a, the algorithm computes the minimal cost of a solution compatible with c. The proof for this result proceeds by induction on the size of the subtree of T rooted in a. If a has no children, then a is a leaf and S a is empty. In this case, there is only one configuration for a, that is the empty configuration and the algorithm gives a cost of 0 for this configuration. Let us assume that the property is true for all subtrees of size at most K, and let a be a node such that the subtree rooted at a has size K + 1. We distinguish three cases depending on the type of the node a.

a is a branch node. Let c = (g, α, µ) be a configuration of a. First, assume that there is a solution f for T a compatible with c and with a cost of A. We will show that the result returned by the algorithm is at most A. Let b 1 and b 2 be the two children of a, and let f 1 and f 2 be the restriction of f to G[T b1 ] and G[T b2 ] respectively. By definition, for i ∈ {1, 2} we know that f i is compatible with the configuration c fi = (g i , α i , µ i ), and additionally, the cost of f is exactly A 1 + A 2 where A i is the cost of f i since the two sets T bi \ S bi for i ∈ {1, 2} form a partition of T a \ S a . Hence, we only need to prove that the pair (c f1 , c f2 ) is not discarded by the algorithm at step 2.2.. In other words, we need to show that the pair satisfies all four properties i. through iv. which are checked at this step:

i. We clearly have g 1 = g 2 since f 1 and f 2 are both restrictions of the same function f .

ii. Since f is compatible with c, we have the following for any v ∈ S a :

α(v) = u∈Ta\Sa f + (vu) = u∈T b 1 \Sa f + (vu) + u∈T b 2 \Sa f + (vu) = α 1 (v) + α 2 (v) .
iii. In a similar way, we have:

µ(v) = σ({f (uv), u ∈ T a \ S a }) = σ({f (uv), u ∈ T b1 \ S a } + {f (uv), u ∈ T b2 \ S a }) = σ(σ({f (uv), u ∈ T b1 \ S a }) + σ({f (uv), u ∈ T b2 \ S a })) = σ(µ 1 (v) + µ 2 (v)) .
iv. Finally, since f is compatible with c, the property (P1) is satisfied for all the vertices in v ∈ S a , in particular, there is at most one vertex u ∈ T a \ S a with f (vu) > 0. Hence, one of α 1 (v) or α 2 (v) is equal to zero.

Since the four properties are satisfied for the pair (c 1 , c 2 ), this pair is not discarded. Using the induction hypothesis, the result returned by the algorithm on the input (b i , c i ) is at most A i , and the result returned by the algorithm on the input (a, c) is at most

A 1 + A 2 = A.
Let us now prove the converse that if the algorithm returns A, then there is a function f compatible with c with a cost of A. Let (c 1 , c 2 ) be the pair which achieves the minimum in the iteration of step 2.. Note that since the pair (c 1 , c 2 )

was not discarded at step 2.2., the properties i. through iv. are satisfied. Let A 1 and A 2 be the result of the algorithm on these two configurations. Using the induction hypothesis, there exist functions f 1 and f 2 compatible with c 1 and c 2 respectively, which achieve a cost of A 1 and A 2 respectively. Let f be the function such that f (e

) = f 1 (e) if e ∈ G[T b1 ] and f (e) = f 2 (e) if e ∈ G[T b2 ].
Note that this function is well-defined since f 1 and f 2 agree on the edges of G[S a ] since the condition i. is satisfied. The cost of f is equal to the cost of f 1 plus the cost of f 2 , hence, to prove the result, we only need to show that f is a valid solution and is compatible with c. Let us first show that f is a valid solution. Clearly, the three properties (P1), (P2), and (P3) are satisfied for all the vertices of T a \ S a since f 1 and f 2 are valid solutions. Moreover, property (P1) is also satisfied for all the vertices in S a by the condition iv. Furthermore, we can check that f satisfies the three properties to make it compatible with c: f agrees with g on S a by construction, moreover, by the condition ii. we have for all v ∈ S a :

α(v) = α 1 (v) + α 2 (v) = u∈T b 1 \Sa f + 1 (vu) + u∈T b 2 \Sa f + 2 (vu) = u∈Ta\Sa f + (vu)
and finally, using condition iii., we have for all v ∈ S a :

µ(v) = σ(µ 1 (v) + µ 2 (v)) = σ(σ({f 1 (uv), u ∈ T b1 \ S b1 }) ⊎ σ({f 2 (uv), u ∈ T b2 \ S b2 })) = σ({f (uv), u ∈ T a \ S a })
This concludes the induction step in the case where a is a branch node.

a is a delete node. Let b the child of a, and v the deleted vertex, i.e., {v} = S b \ S a . Let c = (g, α, µ) be a configuration of a, and let us first assume that there is a solution f compatible with c for T a compatible with c with a cost of A. The cost of f for the node a is equal to the cost of f for the node b plus one if v is a sink in f . Let (g ′ , α ′ , µ ′ ) = c b f be the configuration of f for the node b. To show that the algorithm returns a result of at most A, we only need to prove that the configuration c b f is not discarded at step 3.3.. We check the five properties one by one: i. is clearly true by construction.

ii. By definition, for any u ∈ S a , we have:

α(u) = x∈Ta\Sa f + (ux) = f + (uv) + x∈T b \S b f + (ux) = f + (uv) + α ′ (u) since T a \ S a = T b \ S b ∪ {v}.
iii. Similarly, we have for all u ∈ S a :

µ(u) = σ({f (xu), x ∈ T a \ S a }) = σ({f (xu), x ∈ T b \ S b } ⊎ {f (vu)}) = σ(σ({f (xu), x ∈ T b \ S b }) ⊎ σ({f (vu)})) = σ(µ ′ (u) ⊎ {(y, y)})
where y = f + (vu). iv. Since f is compatible with c, in particular, it satisfies the property (P1) for any vertex in S a \ T a , and in particular for the vertex v. By Lemma 3, this implies that σ(σ({f (uv), u ∈ T a }) ⊎ {(0, w)}) contains a single pair of the form (0, r), where r = w + u∈Ta f + (uv).

v. Since f ′ is compatible with c ′ , it follows that:

β v = α ′ (v) + u∈Sa g ′+ (vu) = u∈Ta f + (vu)
Since f is compatible with c, in particular it satisfies the condition (P2) at the vertex v, which implies that either

β v = 0, or β v = r.
Hence, the configuration c ′ is not discarded by the algorithm, and it returns a result of at most A. Let us assume now for the other direction that the algorithm returns A, and let us show that there exists a solution f with the given cost. Let c ′ be the configuration of b which achieves the minimum in the iteration of step 3. of the algorithm. By definition, the algorithm returns

A ′ = A -1 βv̸ =0
on the input (b, c ′ ). Using the induction hypothesis, we know that there is a function f compatible with c ′ which achieves this cost. The cost of f for the node a is exactly A, hence, to prove the result, we only need to show that f is compatible with c. Since f is a valid solution for the node b, we know that it satisfies the three properties (P1), (P2), and (P3) for all the vertices in T b \ S b , and it satisfies (P1) for all the vertices in S b . Since T a \S a = T b \S b ∪{v}, we only need to show that f satisfies the two properties (P2) and (P3) for the vertex v.

The property (P2) follows from the fact that β v counts how many tokens v gives to one of its neighbours, and the fact that condition v. holds. The property (P3) is a consequence of conditions iv. and v. together with Lemma 3. This shows that f is a valid solution for the node a.

To show that f is compatible with c, we need to check that the three conditions (C1), (C2), and (C3) are satisfied.

(C1) follows immediately from condition i. and the fact that f is compatible with c ′ .

(C2) follows from condition ii., indeed this implies that for all u ∈ S a :

α(u) = g ′+ (uv) + α ′ (u) = f + (uv) + w∈T b \S b f + (uw) = w∈Ta\Sa f + (uw)
finally, (C3) is a consequence of iii., since it implies that for all u ∈ S a :

µ(u) = σ(µ ′ (u) ⊎ {(g ′+ (vu), g ′+ (vu))}) = σ(σ({f + (wu), w ∈ T b \ S b }) ⊎ σ({(f + (vu)})) = σ({f + (wu), w ∈ T a \ S a })
where the last step is obtained using Observation 1.

a is an introduce node. Let b be the child of a, and v be the introduced vertex. Let c = (g, α, µ) be a configuration of a. Assume first that there exists a solution f compatible with c which achieves a cost of A, and let us show that the algorithm returns a result of at most A. Let f ′ be the restriction of f to T b = T a \ v. By definition, the cost of f for the node a is equal to the cost of f ′ for the node b. Additionally, the function f ′ is compatible with the configuration c ′ = (g ′ , α ′ , µ ′ ), where g ′ , α ′ , µ ′ are the restrictions of g, α, µ to S b . Finally, we must have α(v) = 0 and µ(v) = ∅ since, otherwise, there would be no function compatible with c as the vertex v has no neighbour in T a outside of S a . By induction, the algorithm returns a result of at most A on the function f ′ for the node b, and consequently, it also returns A on f for the node a.

Conversely, assume that the algorithm returns a result of A on the node a, and let us show that there exists a solution compatible with c with this cost. Let c ′ be the configuration obtained from c by a restriction to S b . Since the algorithm returns A < +∞, then we must have α(v) = 0, µ(v) = ∅, and the algorithm returns A on the input (b, c ′ ). Using the induction hypothesis, this implies that there is a function f ′ , compatible with c ′ with a cost of A. Let f be the function such that f (uv) = g(uv) for all the vertices u ∈ S a , and f (e) = f ′ (e) for all the other edges. The function f is a valid solution for the node a since f ′ is a valid solution for b. Moreover, f is compatible with c since: f agrees with g on the vertices of S a since f ′ agrees with g on S a \ v, and by construction for the other edges. For all vertices u ∈ S a \ {v}, the condition (C2) is clearly satisfied for f since it is satisfied for f ′ , and α(v

) = 0 = u∈Ta\Sa f + (vu) since v has no neighbours in T a \ S a .
For all vertices u ̸ = v, the condition (C3) is clearly satisfied for f since it is satisfied for f ′ , and µ(v) = ∅ = σ({f (uv), u ∈ S a }) since, again, v has no neighbours in T a \ S a . This concludes the induction step in the case where a is an introduce node, and terminates the proof of the correctness of the algorithm.

Complexity. The complexity follows from the upper bound on the number of configurations in Observation 3. Indeed, for each configuration of a node, one step of the algorithm is performed. The most costly part of the algorithm is the iteration in step 2. which iterates over all pairs of configurations. In the end, the complexity of the algorithm is O(K 3 n), where K is an upper bound on the number of configurations for any given node in the tree decomposition. Observation 3 implies that K = W O(tw(G) min(∆(G),tw(G)+log W )) , giving the required upper bound on the runtime of the algorithm.

Trees

If we restrict our attention to trees, then the algorithm from the previous section can be slightly improved. More precisely, the algorithm above has a complexity of W O(∆) on trees of maximum degree ∆. We show that there is in fact an algorithm with a complexity of O((∆ + 2)!W 4 ), which is a slight improvement on the previous result. In particular, it implies that Unary WTA is FPT on trees when parameterized by the maximum degree of the tree.

The algorithm again uses a dynamic programming approach to solve the problem. The main idea is to observe that if we know the order with which a given vertex acquires its children, then solving the problem just consists in finding weights for each children that sum to the desired value. This can be done in polynomial time using a dynamic programming algorithm somewhat similar to what is used for subset sum. Precisely, we consider the following problem:

Ordered Acquirable Sequence Extraction (OASE)

Inputs: Sets S i for i ≤ k of pairs (x, c) of positive values and their associated costs, represented by a matrix M , where M i,j = c if (j, c) ∈ S i , and M i,j = +∞ otherwise; An initial non-negative value w 0 and a target value W .

Output: a function f : {1, . . . , k} → {0, . . . , W } which minimizes i≤k M i,f (i) under the constraints:

w 0 + i<k f (i) = W ,
f can be acquired with this ordering: for all i ≤ k we have

f (i) ≤ w 0 + j<i f (j).
With this formulation, the set S i represents the possible values that can be acquired from the i th child, and the cost associated to each of these actions. Proof. The algorithm proceeds by dynamic programming by recording for each i, and for each possible value w the minimum cost of a function f on the first i sets. In other words, at step i of the dynamic programming algorithm, for each possible cost w, we have a function f such that:

w 0 + j<i f (j) = w; for each j < i, f (j) ≤ w 0 + ℓ<j f (ℓ).
Among all the functions which satisfy these conditions, we record the ones for which j<i M j,f (j) is minimal. Clearly, by definition, at step k of the algorithm, the cost corresponding to the value w = W is the solution of the problem. Hence, we only need to describe how to go from step i to step i + 1. This is done in a natural way, by simply trying all possibilities for the value f (i + 1). More precisely, the cost for each w of step i + 1 is initialized with +∞. Then, for each possible w and each possible x, the minimum cost of w + x is updated to the minimum between its current value and the sum of the optimal cost for w at step i plus M i,x .

Complexity. At each step, the algorithm iterates over all possible total values w for the previous step, and all possible values x for f (i), which gives at most O(W 2 ) possible choices to consider. Since there are k steps in total, the desired bound on the complexity of the algorithm follows.

Note that the crucial property which makes the algorithm described above work is that we are already given the order according to which the values are acquired. Without this condition, the complexity of the problem is not known. Moreover, a polynomial-time algorithm for the variant of OASE where the order of the acquisition is not fixed could be transformed into a polynomial-time algorithm computing the total acquisition number on trees. This idea is clarified in the proof of the theorem below. Since we do not know a polynomial-time algorithm for the unordered version of OASE, the algorithm first tries all possible orderings, and then applies the algorithm for OASE from Lemma 4.

Theorem 2. The Unary WTA problem can be solved in time O((∆ + 2)!W 4 ) on trees of maximum degree ∆.

Proof. The algorithm proceeds by computing, for every vertex v of the tree, the cost of an optimal solution on the subtree rooted at this vertex, assuming that a certain amount of weight w is moved between v and its parent. The result returned by the algorithm will be simply the associated cost of the root assuming it receives nothing from its (non-existent) parent. If v is a leaf of the tree, then this cost is 1 if v receives at most w(v) from its parent, 0 if v gives exactly w(v) to its parent, and +∞ in all other cases.

Assuming that these costs have been computed for all the children of v, the cost for v, assuming it gives or receives w from its parent is computed by first making a few guesses, and then invoking the algorithm for the OASE problem:

1. first we guess which neighbour v will transfer its weight to, assuming v does not already give the tokens to its parent. We also guess how many tokens w are given to this vertex. If v gives the tokens to its parent, then skip this step and proceed with the second step of the algorithm below. The rest of the algorithm does not change.

2. Then, for the remaining neighbours, we guess the order by which they will be acquired. Again, this is done by trying all the possibilities for the order according to which the neighbours are acquired.

3. Finally, once these choices are made, finding a solution for the tree rooted at the vertex v, knowing potential solutions for the subtrees rooted at each neighbour of v corresponds to solving an instance of OASE. The weight w possibly received from the parent can be treated as a set where the cost of a value is 0 if it is w, and +∞ otherwise. The solution to the instance of OASE gives the optimal cost of a solution which satisfies the choices that were made in the previous steps.

4. Finally, among all the functions that were tried for all the possible choices, we only keep the one which has an optimal cost. Since we tried all possibilities, this is the optimal cost of a partial solution on the subgraph rooted at v where a weight of w is transferred between v and its parent.

The correctness of the algorithm follows immediately from the fact that we tried all possibilities, and the fact that the problem OASE looks for solutions which are acquirable. The only remaining point is to consider the complexity of the algorithm we just described.

Complexity. For each vertex of the tree, the algorithm first tries all possible choices of neighbours of v to which v can transfer its tokens, and, for each of these choices, the algorithm guesses how many tokens are transferred. There are at most ∆W possible choices for this step. Then, the algorithm chooses an ordering of the remaining children, for which there are ∆! possibilities. Finally, the resulting OASE instance is solved in time O(∆W 2 ) using the algorithm from Lemma 4. This gives an overall complexity of O(∆!∆ 2 W 3 ) = O((∆ + 2)!W 3 ) for each vertex of the tree, and since there are n ≤ W vertices in the tree, this gives the complexity claimed in the statement of the theorem.

Split and trivially perfect graphs

In this subsection, we show that the WTA problem is strongly NP-complete, that is, even in its unary version, the problem remains NP-complete in split graphs and trivially perfect graphs.

Theorem 3. The Unary 1-WTA problem is NP-complete in split graphs.

Proof. The hardness is shown by a reduction from the 3-Partition problem. Given an instance S = {x 1 , . . . , x 3ℓ } for 3-Partition, we construct, in polynomial time, a split graph G with a weight function w (with weights polynomial in ℓ) such that a t (G, w) ≤ 1 if and only if the instance of 3-Partition has a solution.

Let B = 1 ℓ 1≤i≤3ℓ

x i , and take two integers Q and R such that Q > ℓB, and R > 3ℓQ. Moreover, we know that we can assume without loss of generality that B 4 < x i < B 2 for all 1 ≤ i ≤ 3ℓ. The split graph G is constructed in the following way: add ℓ vertices u 1 , . . . u ℓ to the clique of G, with w(u i ) = Q; add 3ℓ vertices v 1 , . . . , v 3ℓ to the clique of G, with w(v i ) = x i ; add a single vertex c with weight R to the clique; finally, add ℓ vertices y 1 , . . . , y ℓ to the independent set of G with w(y i ) = Q + B, and such that y i is only adjacent to u i .

An illustration of the construction can be found in Figure 1.

Let us first assume that a t (G, w) = 1, and let us prove that the instance S of 3-Partition admits a solution. Because R is sufficiently large, we know that c will be the only vertex remaining at the end of the acquisition sequence. This implies that, for all 1 ≤ j ≤ ℓ, the vertex y j must be acquired by its only neighbour u j . This is only possible if u j first acquires a weight of at least B first. Moreover, this weight of B can only be acquired from the vertices v i . Indeed, assume by contradiction that this is not the case, and that there is a vertex u j which did not acquire B from the vertices v i , then this vertex must acquire its weight from one other u j ′ , and assume that u j ′ is the first such vertex acquired by u j . However, by the argument above, u j ′ acquires y j ′ before being itself acquired by a neighbour, which means that u j must reach a weight of 2Q + 2B, which is not possible. Hence, every vertex u j must acquire at least B from the vertices v i , and consequently they all acquire exactly B. Hence, if we denote by S j the set of weights acquired by u j , then (S j ) 1≤j≤ℓ is a solution to the Let us prove the other direction, and assume that the set S can be partitioned into ℓ subsets S 1 , . . . , S ℓ , such that for all 1 ≤ j ≤ ℓ, a∈Sj a = B. Using this partition, the acquisition sequence is the following:

u 1 u 2 u ... Q Q Q v 1 v 2 v 3 ...
1. for all 1 ≤ j ≤ ℓ, u j acquires the vertices v i whose weight is in the set S i , which brings the weight of u j to exactly Q + B;

2. then, for all 1 ≤ j ≤ ℓ, u j can acquire y j ;

3. Finally, all the u j s can be acquired by c.

At the end of this sequence, {c} is the residual set, and so, a t (G, w) = 1.

Furthermore, the Unary WTA problem is NP-complete on trivially perfect graphs when the weighted total acquisition number is not a fixed constant.

Theorem 4. The Unary WTA problem is NP-complete in trivially perfect graphs.

Proof. The hardness of the problem is proven by a reduction from 3-partition. Given an instance S = {x 1 , . . . , x 3ℓ } for 3-partition, we construct, in polynomial time, a graph G with a weight function w (with weights polynomial in ℓ) such that a t (G, w) ≤ ℓ if and only if S can be partitioned into ℓ subsets S 1 , . . . , S ℓ of equal value B = 1 ℓ 1≤i≤3ℓ

x i . Moreover, we know that we can assume without loss of generality that B 4 < x i < B 2 for all 1 ≤ i ≤ 3ℓ. Given an integer Q > ℓB, the graph G consists of: 3ℓ universal vertices v 1 , . . . , v 3ℓ , with w(v i ) = x i ; ℓ vertex disjoint paths P j on three vertices u j,1 , u j,2 , u j,3 , with w(u j,2 ) = Q and w(u j,1 ) = w(u j,3

) = Q + B.
It is not difficult to see that this graph is trivially perfect as is shown in Figure 2 First, let us assume that a t (G, w) ≤ ℓ, and let us prove that there is a solution to the 3-partition problem. We can start by observing that since Q > ℓB, the vertices u j,r will never be acquired by any of the vertices v i . Hence, for each 1 ≤ j ≤ ℓ, the tokens which are on the vertices of the path P j never leave this path. Moreover, since the weighted total acquisition number of the graph G is at most ℓ, this implies that the residual set has size at most one on each path P j .

. ... ... v 1 v 2 v 3 u 1,1 u 1,2 u 1,3 u 2,1 u 2,2 u 2,3 u ,1 u ,2 u ,3 x 1 x 2 x 3 Q Q Q Q+B Q+B Q+B Q+B Q+B Q+B
Note that if u j,2 does not acquire any of its two neighbours in the path P j , then by the observations above, there must be at least two residual vertices at the end of the acquisition sequence. Hence, u j,2 must acquire at least one of its two neighbours for all 1 ≤ j ≤ ℓ, which is only possible if it first acquires a weight of at least B. Hence, if we consider an acquisition sequence of cost at most ℓ, then u j,2 acquires at least B from the vertices v i . Moreover, since 1≤i≤3ℓ w(v i ) = ℓ • B, then the vertices u j,2 must acquire a value of exactly B. If we denote by S j the set of weights acquired by u j,2 from the vertices v i , then we have xi∈Sj x i = B, and |S j | = 3 for all 1 ≤ j ≤ ℓ due to the inequalities on the weights x i . Hence, (S j ) 1≤j≤ℓ is a solution to the 3-partition problem.

Let us now prove the other direction, and assume that (S j ) 1≤j≤ℓ is a solution to the 3-partition instance S. We want to show that there is an acquisition sequence which leaves at most ℓ vertices at the end. The acquisition sequence is defined in the following way:

for each 1 ≤ j ≤ ℓ, u j,2 acquires the vertices v i with a weight in S j in any order; then, since the weight of u j,2 is now Q+B, it can acquire its two neighbours u j,1 and u j,3 .

At the end of this acquisition sequence, there is at most one vertex per path P j with remaining tokens, which proves that a t (G, w) ≤ ℓ.

Binary WTA

In this section, we consider the complexity of the binary version of the problem, and we study its complexity for several classes of graphs. Not so surprisingly, the problem turns out to be difficult, and is NP-complete even for very simple classes of graphs such as trees or wheels. However, we prove the problem is tractable on trees when the size of the residual set is bounded, but we show that for other classes of graphs such as complete bipartite graphs, it remains NP-complete to even decide if the weighted total acquisition number of the graph is equal to one. For trivially perfect graphs, Binary 1-WTA is polynomial-time solvable, but Binary 2-WTA is NP-complete. These results prove that polynomial-time algorithms are unlikely to exist for all but the simplest classes of graphs such as paths and cycles, for which such algorithms exist (see Subsection 1.1 and [START_REF] Godbole | The total acquisition number of the randomly weighted path[END_REF]).

Trees

We start by considering the complexity of the problem on trees. In this section, we show that the problem is NP-complete, even for caterpillars of maximum degree 3 (Theorem 5) and subdivided stars (Theorem 6). This shows that neither bounded degree nor bounded depth are sufficient conditions to make the problem polynomial-time solvable.

Theorem 5. The Binary WTA problem is NP-complete on caterpillars of maximum degree 3.

Proof. The NP-hardness proof is done by a reduction from the Partition problem. Let S = {x 1 , . . . , x ℓ } be an instance for the Partition problem. We construct, in polynomial time, an instance G with a weight function w for the WTA problem. This graph G will be such that a t (G, w) ≤ ℓ if and only if the set S = {x 1 , . . . , x ℓ } can be partitioned into two subsets S 1 and S 2 of equal value.

The construction of G = (V, E) is as follows. The vertices of G will be V = {v 1 , . . . , v 2ℓ } ∪ {u 1 , . . . , u 2ℓ }, where the vertices v i induce a path, and the u i form an independent set with u i adjacent only to v i for every 1 ≤ i ≤ 2ℓ. See Figure 3 for an illustration of the construction.

... where

v 1 v 2 v 2 u 1 u 2 u 2 ... v v +1 v +2 u u +1 u +2
Y = 4 ℓ-1 (Q + M 2 ) and Z = 4 ℓ-1 (2Q + M ). Let M = i≤ℓ
x i , and let P 1 , . . . , P ℓ , Q be integers such that P 1 > M , P j > P j-1 + M for all 2 ≤ j ≤ ℓ, and Q = P 1 + P 2 + . . . + P ℓ . The weight function on G is taken such that for every 1 ≤ i ≤ ℓ:

w(v i ) = P i w(v ℓ+i ) = 4 i-1 Q + M 2 w(u i ) = x i w(u ℓ+i ) = 4 i-1 (2Q + M )
To complete the proof, we only need to show that a t (G, w) ≤ ℓ if and only if S has a partition into two subsets of equal value. We start with the forward direction and let us assume that a t (G, w) ≤ ℓ. We want to prove that there is a subset S 1 of S such that

x∈S1 x = M 2 .
Let us consider an optimal acquisition sequence for G. Since the residual set of this sequence has size at most ℓ, there is at least one index i such that the tokens from u ℓ+i are moved towards its (only) neighbour v ℓ+i . Indeed, if this is not the case, then the ℓ vertices u ℓ+1 , . . . , u 2ℓ must all be in the residual set, and thus, all the tokens from the other vertices must move to these ℓ vertices. In particular, this means that all the tokens from the vertices v 1 , . . . , v ℓ and u 1 , . . . , u ℓ must move to these ℓ vertices, and thus, v ℓ+1 must acquire all these tokens since it separates v 1 , . . . , v ℓ and u 1 , . . . , u ℓ from u ℓ+1 , . . . , u 2ℓ . However, this is not possible since their total sum is greater than w(v ℓ+1 ) = Q + M 2 and v ℓ+1 cannot acquire tokens from any of its other neighbours since their weights are larger. Thus, there is at least one index i such that the tokens from u ℓ+i are moved towards its neighbour v ℓ+i . However, since w

(v ℓ+i ) = 4 i-1 (Q + M
2 ) is smaller than w(u ℓ+i ) = 4 i-1 (2Q + M ), this means that v ℓ+i must first receive tokens from one of its two other neighbours. Since the weight of v ℓ+i+1 is larger than the total sum of the weights of the vertices v 1 , . . . , v ℓ+i , u 1 , . . . , u ℓ+i-1 , then v ℓ+i cannot receive tokens from this neighbour, and consequently it must receive tokens from v ℓ+i-1 . The number of tokens it has to receive is at least w(u ℓ+i )-w(v ℓ+i ) = 4 i-1 (Q+ M 2 ). Moreover, this quantity is four times the initial weight of v ℓ+i-1 , hence, the vertex v ℓ+i-1 itself must receive tokens from both of its other neighbours. By iterating the argument, it follows that the tokens from u ℓ+1 are moved to its neighbour v ℓ+1 , which then transfers these tokens to its neighbour on the right. This operation is possible if and only if it receives exactly Q + M 2 tokens from its neighbour v ℓ (it cannot receive more than that since a vertex cannot receive more than its current weight in one move). If we denote by I the set of indices 1 ≤ i ≤ ℓ such that u i transfers tokens to v i in the acquisition sequence, then the previous condition implies that

i∈I x i = M 2 .
Let us now prove the other direction, and assume that the set S can be partitioned into two subsets S 1 and S 2 such that

y∈S1 y = z∈S2 z = M 2 .
We want to prove that a t (G, w) ≤ ℓ. Using the partition, for every 1 ≤ i ≤ ℓ, if x i ∈ S 1 , then v i acquires its neighbour u i . Then, for each 2 ≤ i ≤ ℓ, v i acquires v i-1 . At this point, the vertex v ℓ has a total weight of

1≤i≤ℓ P i + x∈S1 x = Q + M 2 .
From this point, for 1 ≤ j ≤ ℓ, v ℓ+j first acquires v ℓ+j-1 , and then, acquires u ℓ+j . Checking that all these moves are valid is straightforward. The residual set has size at most ℓ (v 2ℓ plus at most ℓ -1 of the vertices u 1 , . . . , u ℓ ).

The previous result shows that the problem is hard if we allow long paths in a tree, even if the maximum degree is 3. The following theorem compliments this result by showing that even if the depth of the tree is bounded (and the maximum degree is unbounded), the problem remains NP-complete. Note that trees with both bounded depth and bounded maximum degree have bounded size and consequently are not interesting to study. Theorem 6. The Binary WTA problem is NP-complete on stars where each edge is subdivided once.

Proof. The NP-hardness of the problem is shown by a reduction from the Partition problem. Let S = {x 1 , . . . , x ℓ } be an instance for Partition. We construct, in polynomial time, a graph G with a weight function w such that a t (G, w) ≤ ℓ + 1 if and only if the set S = {x 1 , . . . , x ℓ } can be partitioned into two subsets S 1 and S 2 of equal value.

The graph G is a star where each edge is subdivided once. We denote by c the center of the star, u 1 , . . . u ℓ , t 1 , t 2 the leaves of the star, and v 1 , . . . , v ℓ , s 1 , s 2 the vertices obtained by the subdivision of the edges. See Figure 4 for an illustration of the construction. Let M = 1≤i≤ℓ

x i , and let Q, R be integers such that Q > M and R > 15Q.

The weight function w is defined such that for every 1 ≤ i ≤ ℓ:

w(v i ) = x i w(u i ) = R w(s 1 ) = Q + M 2 w(t 1 ) = Q + M 2 w(s 2 ) = 4Q + 2M w(t 2 ) = R w(c) = 2Q + M 2
First, assume that a t (G, w) ≤ ℓ+1, and let us prove that S admits a partition into two subsets of equal value. Note that, since the vertices u 1 , . . . , u ℓ , t 2 form ... ...

v 1 v 2 v u 1 u 2 u x 1 x 2 x R R R Q+ M 2 Q+ M 2 4Q+2M R 2Q+ M 2 s 1 s 2 t 1 t 2 c
Figure 4: Construction of the subdivided star graph G from the proof of Theorem 6.

an independent set and all these vertices have sufficiently large weight, they will never be acquired by any other vertex. Hence, these vertices must form the residual set of any optimal acquisition sequence. This implies that in such a sequence, t 1 must be acquired by s 1 , and c must be acquired by s 2 since none of the other vertices v i has an initial weight sufficiently large to acquire c. The vertex c can acquire s 1 if and only if it reaches a weight of at least w(s 1 ) + w(t 1 ) since s 1 acquired t 1 . This implies that c must acquire a weight of at least M 2 from the vertices v 1 , . . . , v ℓ . Moreover, since c is acquired by s 2 , its weight at the moment it is acquired cannot exceed w(s 2 ) = 4Q + 2M . This implies that c did not acquire more than M 2 from the vertices v 1 , . . . , v ℓ . Hence, if S 1 is the set of weights acquired by c, then (S 1 , S \ S 1 ) is a partition of S where the two parts sum to the same total value.

For the other direction, assume that S can be partitioned into two subsets S 1 and S 2 such that

y∈S1 y = z∈S2 z = M 2 .
Consider the following acquisition sequence:

1. for all 1 ≤ i ≤ ℓ, if x i ∈ S 1 , then the vertex v i is acquired by c, otherwise, it is acquired by u i ; 2. s 1 acquires t 1 ; 3. at this step, c has a total weight of w(c) + M Theorem 7. For all integers k ≥ 1, the Binary k-WTA problem can be solved in trees in time n O(k) .

Proof. The result follows from the two following observations:

The first observation is that there are at most O(n k ) ways to partition a tree into k connected components. Indeed, every edge which is removed from the tree splits a component into 2, thus a partition of size k is uniquely defined by the k edges which were removed from G.

We can decide in polynomial time if a tree has a weighted total acquisition number of 1. For this, simply observe that the first move of an acquisition sequence on the tree must move tokens from a leaf to its neighbour (since otherwise the move disconnects the graph, and the residual set will have size at least 2). Moreover, the order according to which the leaves are acquired is not important.

With these two observations, devising an algorithm for the problem is straightforward: we can simply try all O(n k ) partitions, and each of these partitions we can check in polynomial time if the weighted total acquisition number of each connected component is one.

Complete bipartite graphs

In the previous section, we studied the complexity of computing the weighted total acquisition number on trees, and saw that the problem was NP-complete if the weighted total acquisition number of the tree is not bounded. In this section, we show that it remains NP-complete to decide if the weighted total acquisition number is equal to 1 for another very simple class of graphs: complete bipartite graphs. In Theorem 8, we show that this problem is NP-complete in K 3,n , the complete bipartite graph where one side of the bipartition has size 3.

w(v 1 ) = R, w(v 2 ) = 2Q + M , w(v 3 ) = Q, w(u ℓ+1 ) = Q + M
2 , and for every 1 ≤ i ≤ ℓ, take w(u i ) = x i . See Figure 5 for an illustration of the construction.

First, assume that a t (G, w) = 1, and let us prove that there is a partition (S 1 , S 2 ) of S into subsets of equal value. Consider an optimal acquisition sequence for the graph G. Since R is taken sufficiently large and a t (G, w) = 1, the residual set must be equal to {v 1 }. This implies that v 2 must be acquired Binary 1-WTA can be solved in polynomial time on trivially perfect graphs, while Binary 2-WTA is NP-complete for this class.

Theorem 9. The Binary 1-WTA problem is polynomial-time solvable on trivially perfect graphs.

If the trivially perfect graph is not connected, then clearly any residual set is of size at least 2. Thus, assume the trivially perfect graph is connected. The algorithm in this theorem will find an acquisition sequence with a residual set of size 1 (if it exists) by greedily moving tokens from one vertex to one of the universal vertices of the graph. The correctness of the algorithm relies on the following lemma: Lemma 5. Let G = (V, E) be a graph and w be a weight function of G. Assume that there is a subset S such that:

G[V \ S] contains k connected components A 1 , . . . A k ; v∈S w(v) < w(u) for every u ∈ V \ S.
Then, a t (G, w) ≥ k.

Proof. Assume by contradiction that a t (G, w) < k, and let us consider an optimal acquisition sequence. Since a t (G, w) < k, this implies that at some point during the acquisition sequence, one of the vertices in one of the sets A i is acquired by a vertex which is not in A i , and thus, is in S. Let us consider the first time such an event happens, and let v be the vertex in A i , and u the vertex in S. When v is acquired by u, there are at least w(v) tokens on v, while the number of tokens on u can be at most x∈S w(x), since this is the first time that a vertex in S acquires a vertex outside S. However, this contradicts the assumption that x∈S w(x) < w(v), and consequently is not possible. Hence, a t (G, w) ≥ k.

The algorithm for finding an acquisition sequence proceeds greedily. At each step, it finds a universal vertex with maximum weight, and makes it acquire another vertex of the graph until only it remains. If the algorithm cannot find such an acquisition move, then it concludes that the weighted total acquisition number of the graph is larger than 1. The algorithm is described more formally below: Input: A connected trivially perfect graph G and a weight function w. Output: Tests whether a t (G, w) = 1.

while

|V (G)| > 1 do u ← universal vertex of G with maximum weight. if there is v ̸ = u such that w(v) ≤ w(u) then u acquires v remove v from G else return False end if end while return True
Proof of Theorem 9. Clearly, the algorithm described above runs in polynomial time since the number of vertices in the graph decreases by one at each iteration. Hence, to prove the theorem, we only need to prove that it is correct. The case when the algorithm returns true is straightforward since the algorithm has found an acquisition sequence with only one vertex at the end. Hence, we only need to prove that when the algorithm returns false, then a t (G, w) > 1. This is done by showing that when the algorithm returns false, then we can construct a set S which satisfies the conditions of Lemma 5.

Let us assume that the algorithm returned false on the graph G with the weight function w, and let us show that a t (G, w) > 1. Let G ′ and w ′ be the graph and the weight function at the time where the algorithm returned false. Let us start with a few observations. First, remark that G ′ contains exactly one universal vertex u. Indeed, if there were two universal vertices, then the one with the larger weight could acquire the one with the smaller weight. Also, since the graph remains connected throughout the algorithm, it must contain at least one universal vertex by the definition of trivially perfect graphs.

Furthermore, at each step, the universal vertex u acquires another vertex of the graph, hence, if S is the set of vertices which were removed up to this point, then we must have w

′ (u) = w(u) + v∈S w(v) since u is the only universal vertex in G ′ . Consequently, we also have w ′ (v) = w(v) for all v ∈ G ′ \ {u}.
Since u is the unique universal vertex of G ′ , then G ′ \ {u} is not connected. Since the algorithm returned false at this step, then for all v ∈ G ′ with v ̸ = u, we have w ′ (v) > w ′ (u) = x∈S∪{u} w(x). Hence, S ∪ {u} is a separator of G, and by the previous inequality and Lemma 5, we can conclude that a t (G, w) ≥ 2.

The Binary WTA problem becomes NP-complete as soon as the desired residual set is of size at most k for k ≥ 2.

Theorem 10. The Binary 2-WTA problem is NP-complete on trivially perfect graphs.

Proof. To show that the problem is NP-hard, we reduce from the Partition problem. Given an instance S = {x 1 , . . . , x ℓ } for Partition, we construct, in polynomial time, a graph G and a weight function w such that a t (G, w) ≤ 2 if and only if S can be partitioned into two subsets S 1 and S 2 of equal value.

The graph G is composed of two independent sets I v = {v 1 , v 2 } and I u = {u 1 , . . . , uℓ, s 1 , s 2 , t 1 , t 2 }, and a universal vertex c. The vertex v 1 is only adjacent to t 1 , t 2 , and c, while v 2 is adjacent to u 1 , . . . , u ℓ , s 1 , s 2 , and c. Let M = 1≤i≤ℓ

x i , and let P, Q be integers such that P > M 2 and Q > P +M . The weight function w is as follows for all 1 ≤ i ≤ ℓ and 1 ≤ j ≤ 2:

w(c) = P w(v j ) = Q w(u i ) = x i w(s j ) = Q + M 2 w(t j ) = Q + P + M 2 ... ... P Q Q Q+ M 2 Q+ M 2 Z Z x 1 x c v 1 v 2 t 1 t 2 u 1 u s 1 s 2
= Q + P + M 2 .
The graph G is trivially perfect, as we can see in Figure 6. We start with the following claim: Claim 2. In any acquisition sequence of G, c never acquires any vertex in

S * = {v 1 , v 2 , t 1 , t 2 , s 1 , s 2 }.
Proof of claim. Assume by contradiction that there is an acquisition sequence of G in which c acquires a vertex of S * , and let us be at the step in the acquisition sequence just before the first time such an acquisition occurs. At this time, the current weight of c is at most P + M since c has not acquired any of the vertices in S * yet. Moreover, all the vertices in S * have an initial weight of at least Q, hence, their current weight, if it is not zero, is also at least Q. But, Q > P + M , which means that the acquisition of the vertex in S * by c is not valid. ⋄

First, assume that a t (G, w) ≤ 2 and let us prove that there is a partition of S into two subsets of equal value. Let us consider an optimal acquisition sequence for G. By Claim 2, we know that c will never acquire the vertices v 1 , t 1 , and t 2 , and hence, at least one of these three vertices is in the residual set. Additionally, if c is not acquired by v 1 , or if c does not have a total weight of at least P + M 2 at the time it is acquired by v 1 , then the residual set will have size at least 3. Indeed, in both cases the two vertices t 1 and t 2 cannot be acquired by any neighbour, and at least one of v 2 , s 1 , and s 2 will remain in the residual set since none of them can be acquired by c by Claim 2. This implies that c must acquire a weight of at least M 2 from the vertices u 1 , . . . , u ℓ . Moreover, for similar reasons, at least one of s 1 and s 2 must be acquired by one of their neighbours, and this neighbour cannot be c, and consequently must be v 2 . However, for this move to be possible, v 2 must acquire at least M 2 from its neighbours, and since v 2 cannot acquire c, then this weight of M 2 must come from the vertices u 1 , . . . , u ℓ . Hence, if we denote by S 1 the weights x i which are acquired by c, and S 2 the weights acquired by v 2 , then the two sets have a total sum of at least M 2 , and consequently, exactly M 2 since 1≤i≤ℓ

x i = M . Hence, (S 1 , S 2 ) is a partition of S into two subsets of equal value. Now, let us prove the other direction, and assume that the set S can be partitioned into two subsets S 1 and S 2 of equal value. Using this partition, consider the following acquisition sequence:

1. for all 1 ≤ i ≤ ℓ, if x i ∈ S 1 , then c acquires u i , otherwise, v 2 acquires u i .
After this, c has a weight of P + M 2 , and v 2 has a weight of Q + M 2 . 2. v 1 acquires c, and then both t 1 and t 2 ; 3. v 2 acquires both s 1 and s 2 .

The residual set for this acquisition sequence has size two, which proves that a t (G, w) ≤ 2 and proves the theorem.

Planar graphs

In this section, we study the weighted total acquisition number in planar graphs. We show that the Binary WTA problem is NP-complete in wheels, a simple class of planar graphs. However, similarly to trees, we show that the problem can be solved in polynomial time for instances with a bounded weighted total acquisition number. Finally, we show that for a slightly larger class of graphs, namely planar graphs of pathwidth 2, the Binary 2-WTA problem is NPcomplete.

Theorem 11. For all integers k ≥ 1, the binary k-WTA problem can be solved in n O(k) time on wheels.

Proof. Let G = (V, E) be a wheel with center c, w be a weight function on G, and k a fixed positive integer. The main idea of the algorithm consists in proving that there are only at most n O(k) possible candidates we need to consider for the acquisition forest that we are searching for.

First, notice that there are at most n O(k) partitions of G into at most k vertex-disjoint connected components. Indeed, a connected component of G that does not contain c is a path and can be identified by its extremities. So, there are O(n 2 ) such components. Consider now a connected component C which contains c. Since G[V \ C] contains at most k -1 connected components and those components can be identified by their extremities, C can be identified by at most 2(k -1) vertices. Thus, there are n O(k) connected components that can contain c and n O(k) ways to partition into k connected components.

Hence, to complete the algorithm it is sufficient to be able to check in polynomial time if each component of a given partition has a weighted total acquisition number of 1. If the component is a path, then this can be done using the algorithm from [START_REF] Godbole | The total acquisition number of the randomly weighted path[END_REF]. Hence, we only need to consider the component which contains the center of the wheel. We will show that, for this component, there is only a polynomial number of acquisition forests to consider. We know that if we remove the vertex c, this component is a collection of paths. Moreover, without loss of generality, we can assume that, for all but one of these paths, a solution acquisition forest does not contain edges of the path (the exception being the path that will contain the residual vertex, if it is not c). Indeed, if there is an acquisition move from u to v, and then from v to c, then the first move can be replaced by an acquisition move from u to c directly. By repeating this simplification, we can assume that c acquires all the vertices in each of the paths of the component, except possibly one. Hence, once we have chosen which vertex will be residual, and which neighbour c will transfer its tokens to, the acquisition forest satisfying this property is fixed. Hence, since there are at most O(n 2 ) possibilities for these two choices, we can check in polynomial time if the component containing the center has a weighted total acquisition number of 1. This completes the proof of the existence of such an algorithm, and proves the theorem.

If the size of the desired residual set is not fixed, the problem becomes NPcomplete.

Theorem 12. The Binary WTA problem is NP-complete in wheels.

Proof. The hardness of the problem is shown by a reduction from Partition. Given an instance S = {x 1 , . . . , x ℓ } of the Partition problem, we construct, in polynomial time, a graph G with a weight function w such that a t (G, w) ≤ ℓ + 2 if and only if S can be partitioned into two subsets S 1 and S 2 of equal value.

The graph G will be composed of a central vertex c, and 2ℓ + 7 vertices v 1 , . . . , v 2ℓ+1 , u 1 , s 1 , s 2 , s 3 , s 4 , u 2 on the outer cycle in this order. Let M = 1≤i≤ℓ x i , and let Q, R be integers such that Q > 50M , and R > 50Q. The weight function w is built such that for all 1 ≤ i ≤ ℓ:

w(v 1 ) = R w(v 2i+1 ) = R w(v 2i ) = x i w(c) = Q w(u 1 ) = w(u 2 ) = M w(s 1 ) = 2Q + 4M w(s 2 ) = Q + 7M 2 w(s 3 ) = 4Q + 8M w(s 4 ) = 8Q + 15M
The vertices with weight R act as some sort of separator. Since their weight is too large, they will never be acquired and they remain in the residual set at the end of the acquisition sequence. The main idea is that the center c will need to acquire exactly M 2 tokens if we want only one residual vertex for the vertices s 1 , s 2 , s 3 , s 4 . See Figure 7 for an illustration of the construction.

Let us first assume that a t (G) ≤ ℓ + 2, and let us prove that there is a partition of S into two subsets of equal value. Since R is taken sufficiently large, we know that the vertices v 1 and v 2i+1 will never be acquired and remain in any residual set at the end of an acquisition sequence. Moreover, the center c can ... acquire a weight of at most 3M from the vertices v 2i and u 1 , u 2 , and consequently will never be able to acquire any of the s i . Similarly, by the choice of Q, we also know that the vertices u i will not be able to acquire any of their neighbouring s i . Since there are at most ℓ + 2 vertices in the residual set at the end, and ℓ + 1 of these vertices are v 1 and the v 2i+1 , this implies that the vertices s 1 , . . . , s 4 must be ultimately acquired by a single vertex. This vertex will have a weight of at least 1≤i≤4 w(s i ) ≥ 15Q at the end. Since the s i cannot be acquired by other vertices that are not s i , and the initial weights of s 3 and s 4 combined are much larger than those of s 2 and s 1 (even combined and after receiving all the other possible weights they could acquire), the vertex which acquires the vertices s i can only be either s 3 or s 4 . This implies that s 1 must be acquired by s 2 , which is only possible if s 2 first acquires at least Q + M 2 tokens from another vertex. This other vertex can only be the central vertex c. Hence, after acquiring both c and s 1 , the vertex s 2 has a weight of at least 4Q + 8M = w(s 3 ). Moreover, since the residual vertex is either s 3 or s 4 , then s 2 must be acquired by s 3 , which is only possible if its weight at this point is at most w(s 3 ) = 4Q + 8M . This implies that s 2 acquired at most Q + M 2 from c, and consequently acquired exactly this quantity from c. Hence, if we denote by S 1 the set of weights acquired by c, and S 2 = S \ S 1 , then these two sets form a partition of S, and by the construction of S 1 and the argument above, we have 1. u j acquires all the vertices v i with x i ∈ S j , for all 1 ≤ i ≤ ℓ and 1 ≤ j ≤ 2; 2. at this point, u 1 and u 2 both have a weight of Q + M 2 , and they can acquire s 1 and s 2 respectively; 3. finally, t acquires both u 1 and u 2 .

Clearly, the residual set at the end of this acquisition sequence has size 1, which proves that a t (G, w) ≤ 1.

Corollary 1. The Binary 1-WTA problem is NP-complete in unit interval graphs.

Proof. Observe that in the construction of the graph G in the proof of Theorem 13, we can replace the independent set formed by the vertices v 1 , . . . , v ℓ , t by a clique, and all the arguments still work the same. By doing this, the graph G becomes a unit interval graph, which proves the theorem.

Further Work

In this article we investigated the complexity of the weighted total acquisition problem for different classes of graphs. We have seen that, in its binary version, the problem is hard even for very simple classes of graphs. One further direction of research could be to look in more detail at the parameterized complexity of the problem. For example, on trees and on wheels, we know that Binary k-WTA is in XP for the parameter k, but it is unknown if the problem is FPT. It can also be interesting to investigate the problem on other classes of graphs such as outerplanar graphs for which we conjecture that Binary k-WTA can be solved in polynomial time for constant k.

We also proved that Unary WTA is more tractable than the binary version. One question which remains open is whether the problem can be solved in polynomial time on trees or at least to look for ways to improve the W O(log(W )) upper bound on the time complexity of the problem for trees. Finally, it could be interesting to investigate if Unary WTA can be solved in polynomial time on other classes of graphs such as complete bipartite graphs.

Observation 2 .

 2 Let X be a multiset of elements with values upper bounded by W , then |σ(X)| ≤ min(|X|, log W + 1).

Lemma 3 .

 3 The multiset X satisfies property (P3) for weight w if and only if σ( X ⊎ {(0, w)}) = {(0, A)} where A = w + x∈X x.

2 .

 2 a is a branch node with children b 1 and b 2 .

Lemma 4 .

 4 The OASE problem can be solved in time O(kW 2 ).

Figure 1 :

 1 Figure 1: Construction of the split graph G from the proof of Theorem 3.

3 -

 3 Partition instance, since |S j | = 3 for all 1 ≤ j ≤ ℓ due to the inequalities on the weights x i .

Figure 2 :

 2 Figure 2: Construction of the trivially perfect graph G from the proof of Theorem 4.

Figure 3 :

 3 Figure 3: Construction of the caterpillar graph G from the proof of Theorem 5, where Y = 4 ℓ-1 (Q + M 2 ) and Z = 4 ℓ-1 (2Q + M ).

Theorem 8 .

 8 The Binary 1-WTA problem is NP-complete in K 3,n . Proof. To show that the problem is NP-hard, we reduce from the Partition problem. Given an instance S = {x 1 , . . . , x ℓ } for the Partition problem, we construct, in polynomial time, a graph G with a weight function w such that a t (G, w) = 1 if and only if the set S can be partitioned into two subsets S 1 and S 2 of equal value. The graph G is K 3,ℓ+1 , with v 1 , v 2 , v 3 the vertices of the side of size 3, and u 1 , . . . , u ℓ+1 the vertices of the other side. Let M = x∈S x, and Q, R be integers such that Q > M , and R > 10Q. The weight function w is constructed such that

Figure 6 :

 6 Figure 6: Construction of the trivially perfect graph G from the proof of Theorem 10, where Z = Q + P + M 2 .

6 vFigure 7 :

 67 Figure 7: Construction of the wheel graph G from the proof of Theorem 12, where Z = 8Q + 15M .

x∈S1 x = M 2 ,

 2 which proves that the two subsets have equal value.

2 xFigure 8 : 2 .

 282 Figure 8: Construction of the graph G of pathwidth 2 from the proof of Theorem 13.

  Is there a partition of S into n triples S 1 , . . . , S n such that

	and B 4 < x i < B 2 for all 1 ≤ i ≤ 3n.
	Question: x∈Si

which is equal to the current weight of s 1 , hence, c can acquire s 1 and its new weight becomes 4Q + 2M ; 4. finally, c can be acquired by s 2 which can then be acquired by t 2 .The residual set of this acquisition sequence has size exactly ℓ + 1.The two previous results showed that Binary WTA is hard, even in trees. On the positive side, the theorem below shows that if the weighted total acquisition number is bounded by a fixed constant, then the problem becomes polynomial-time solvable. From a parameterized complexity point of view, this result implies that Binary k-WTA is in XP in trees when parameterized by k. The question of whether this problem is FPT or not is still open.

-1

* This work has been partially supported by ANR projects GAG and DISTANCIA (ANR-14-CE25-0006 and ANR-17-CE40-0015, respectively).

... by one of its neighbours, and this neighbour must be u ℓ+1 since it is the only vertex in its neighbourhood that can reach a sufficient weight to acquire v 2 . In order to acquire v 2 , u ℓ+1 must first reach a sufficient weight to acquire it, hence, it must first acquire at least Q + M 2 tokens from v 3 . Moreover, since the initial weight of u ℓ+1 is also Q + M 2 , it must acquire exactly Q + M 2 tokens from v 3 (since otherwise the move from v 3 to u ℓ+1 would not be possible). This implies that v 3 must acquire a weight of exactly M 2 from the vertices u 1 , . . . , u ℓ . Consequently, if S 1 corresponds to the weights of the vertices acquired by v 3 in this acquisition sequence, and S 2 = S \ S 1 , then (S 1 , S 2 ) forms a partition of S into subsets of equal value. Now, let us prove the other direction, that is, if the set S can be partitioned into two subsets S 1 and S 2 such that

2 , then a t (G, w) ≤ 1. Let S 1 and S 2 be such a partition of S. We start by using this partition to send a total weight of M 2 from the vertices u 1 , . . . , u ℓ to v 3 by making v 3 acquire all the weights x i , for x i ∈ S 1 for example. By this operation, v 3 reaches a weight of Q + M 2 , and can be acquired by u ℓ+1 who now reaches a weight of 2Q + M , and can thus acquire v 2 . Finally, v 1 can acquire all the remaining vertices, which shows that a t (G, w) = 1.

Note that the proof can be easily adapted to k-WTA, for k > 1 by adding vertices with very large weights on the side of size 3. In this case, the graph we obtain with this construction will be K k+2,ℓ+1 .

Trivially perfect graphs

In this section, we focus on the weighted total acquisition number of trivially perfect graphs. We give a full dichotomy of the complexity of the problem in terms of the maximum size of the residual set. More precisely, we prove that Now for the other direction, assume that S can be partitioned into two subsets S 1 and S 2 such that

2 , and let us construct an acquisition sequence for G. Using this partition, the central vertex c can acquire a total weight of exactly M 2 by acquiring all the x i for x i ∈ S 1 . All the remaining vertices v 2i which were not acquired by c at this point, as well as u 1 and u 2 are acquired by one of their neighbours with weight R. Then, apply the following acquisition moves in this order: At the end of this acquisition sequence the only remaining vertices are s 3 , v 1 , and the v 2i+1 , which proves that a t (G, w) ≤ ℓ + 2.

Theorem 13. The Binary 1-WTA problem is NP-complete in planar graphs of pathwidth 2.

Proof. To show that the problem is NP-hard, we reduce from the Partition problem. Given an instance S = {x 1 , . . . , x ℓ } for Partition, we construct, in polynomial time, an instance G with a weight function w such that a t (G, w) ≤ 1 if and only if S can be partitioned into two subsets S 1 and S 2 of equal value. Let M = 1≤i≤ℓ

x i , and let Q and R be two integers such that Q > M and R > 10Q. The graph G and the weight function w consist of:

ℓ + 1 vertices v 1 , . . . , v ℓ , t forming an independent set, with w(v i ) = x i for all 1 ≤ i ≤ ℓ, and w(t) = R;

two vertices u 1 and u 2 adjacent to t and all the vertices in v 1 , . . . , v ℓ , and such that w(u 1 ) = w(u 2 ) = Q ; two vertices s 1 and s 2 adjacent to u 1 and u 2 respectively, with w(s 1 ) = w(s 2 ) = Q + M 2 . We can see in Figure 8 that G is planar, and it can be easily checked that it also has pathwidth 2.

Let us first assume that a t (G, w) = 1, and let us prove that S can be partitioned into two sets of equal value. Consider an optimal acquisition sequence for G. Note that since R, the weight of t, is sufficiently large, and the size of the residual set is 1, this residual set must be equal to {t}. This implies that both s 1 and s 2 must be acquired by their only neighbour u 1 and u 2 respectively. However, for this to happen, both u 1 and u 2 must first acquire a weight of at least M 2 , and since 1≤i≤ℓ

x i = M , they can only acquire exactly M 2 each. Hence, if S i are the weights acquired by u i from the vertices v 1 , . . . , v ℓ , then by the argument above, (S 1 , S 2 ) is a partition of S where the two parts sum to the same value.