The Maximum Zero-Sum Partition problem
Guillaume Fertin, Oscar Fontaine, Géraldine Jean, Stéphane Vialette · Theoretical Computer Science · 2024
We study the Maximum Zero-Sum Partition problem (or MZSP ), defined as follows: given a multiset S = { a 1 , a 2 , … , a n } of integers a i ∈ Z ⁎ (where Z ⁎ denotes the set of non-zero integers) such that ∑ i = 1 n a i = 0 , find a maximum cardinality partition { S 1 , S 2 , … , S k } of S such that, for every 1 ≤ i ≤ k , ∑ a j ∈ S i a j = 0 . Solving MZSP is useful in genomics for computing evolutionary distances between pairs of species. Our contributions are a series of algorithmic results concerning MZSP , in terms of complexity, (in)approximability, with a particular focus on the fixed-parameter tractability of MZSP with respect to either (i) the size k of the solution, (ii) the number of negative (resp. positive) values in S and (iii) the largest integer in S .