Skip to Main content Skip to Navigation
Journal articles

Weighted Total Acquisition

Guillaume Bagan 1 Valentin Gledel 2 Marc Heinrich 3 Fionn Mc Inerney 4 
1 GOAL - Graphes, AlgOrithmes et AppLications
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
2 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
4 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
LIS - Laboratoire d'Informatique et Systèmes
Abstract : In the Weighted Total Acquisition problem (WTA) on a weighted graph $G$ (only positive non-zero weights), a vertex $v$ can acquire the total weight of a neighbour $u$ if and only if the current weight of $v$ is at least that of $u$. The new weight of $u$ is then zero, and the new weight of $v$ is then the sum of the weights at $u$ and $v$ just before the acquisition. Over all possible acquisition sequences in $G$ with weight function $w$, the minimum number of vertices with a non-zero weight at the end is denoted by $a_t(G,w)$. Given a graph $G$, a weighting $w$, and an integer $k\geq 1$, the WTA problem asks whether $a_t(G,w)\leq k$. The Binary (Unary resp.) WTA problem corresponds to the WTA problem when the weights are encoded in binary (unary resp.).We prove that Unary WTA is polynomial-time solvable in graphs of bounded treewidth and degree. When only the treewidth is bounded, this algorithm is quasi-polynomial, i.e., it runs in time $W^{O(\log W)}$, where $W$ is the sum of the weights of the vertices. Moreover, we show that Unary WTA is FPT in trees when parameterized by the maximum degree. On the negative side, we show that WTA is NP-complete in trivially perfect graphs and split graphs, even when $k=1$ in the latter.We prove that the Binary WTA problem is NP-complete in trees of bounded degree, trees of bounded depth, and wheels, but that it is in XP for trees and wheels when parameterized by the solution size. Moreover, we show that Binary WTA is NP-complete in $K_{3,n}$, planar graphs of pathwidth 2, and unit interval graphs even when $k=1$, and in trivially perfect graphs when $k\geq 2$ (but polynomial-time solvable when $k=1$).
Document type :
Journal articles
Complete list of metadata
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Tuesday, August 17, 2021 - 5:00:15 PM
Last modification on : Friday, June 10, 2022 - 1:26:02 PM


Files produced by the author(s)



Guillaume Bagan, Valentin Gledel, Marc Heinrich, Fionn Mc Inerney. Weighted Total Acquisition. Discrete Applied Mathematics, Elsevier, 2021, 304, pp.260-282. ⟨10.1016/j.dam.2021.07.040⟩. ⟨hal-02880093v2⟩



Record views


Files downloads