The Maximum Zero-Sum Partition problem

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.

Authors

• Guillaume Fertin
• Oscar Fontaine
• Géraldine Jean
• Stéphane Vialette

Keywords

• Zero-sum
• Partition
• Algorithmic complexity
• Inapproximability
• FPT