A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles, which is optimal. This is an improvement over the previous best bound k^O(k) g² of Gao, Richter and Seymour [Journal of Combinatorial Theory, Series B, 1996].

The geometry of a graph \(G\) embedded on a closed oriented surface \(S\) can be probed by counting the intersections of \(G\) with closed curves on \(S\). Of special interest is the map \(c \mapsto \mu_G(c)\) counting the minimum number of intersections between \(G\) and any curve freely homotopic to a given curve \(c\). Schrijver [On the uniqueness of kernels, 1992] calls \(G\) a kernel if for any proper graph minor \(H\) of \(G\) we have \(\mu_H \lt \mu_G\). Hence, \(G\) admits a minor \(H\) which is a kernel and such that \(\mu_G = \mu_H\). We show how to compute such a minor kernel of \(G\) in \(O(n^3 \log n)\) time where \(n\) is the number of edges of \(G\), and \(g \ge 2\) is the genus of \(S\). Our algorithm leverages a tight bound on the size of minimal bigons in a system of closed curves. It also relies on several subroutines of independent interest including the computation of the area enclosed by a curve and a test of simplicity for the lift of a curve in the universal covering of \(S\).

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 .