A binary tree is a rooted tree in which each node has at most two children. A full binary tree is one in which each node has exactly two children or no child. A node is called a leaf if it has no child. For a given rooted tree and a node $v$, the number of edges from the root to $v$ is called the depth of $v$. For a non-negative integer vector $w=(w_1,w_2,\cdots, w_d)$, if there is a full binary tree $T$ such that each $w_i$ corresponds to the number of leaves at depth $i$ in $T$, where $w$ is said to be a leaf vector of full binary trees.
In this talk, we present an algorithm to enumerate all full binary trees for a given leaf vector. Our algorithm runs in constant delay and generates each full binary tree in O($max w_i$) time as the difference from the previous output. The algorithm is extended to enumerate all binary trees in polynomial delay for a given leaf vector.

Investigating the set of Path-Length Matrices (PLMs) induced by unrooted binary trees with n leaves remains an elusive challenge in combinatorial optimization and graph theory, persisting since its introduction in the 1970s. This characterization plays a pivotal role in exploring the optimization facets of diverse applications, spanning from epidemiology to data compression and information theory. Here, we address this longstanding problem by presenting the first known characterization for the PLM set, accompanied by a collection of valid inequalities and polyhedral results that contribute to understanding its convex hull.

Leveraging these findings, we delve into the Balanced Minimum Evolution Problem (BMEP), a NP-hard nonlinear optimization problem arising from the literature on computational phylogenetics. The study of the polyhedral combinatorics of the BMEP reveals strong connections with the symmetric Traveling Salesman polytope, and sheds light on the aspects related to the dyadic nature of its solutions.

By working in an extended space, our characterization leads to the smallest integer linear programming formulation known to date for the BMEP. By further embodying the facets and the strengthening valid inequalities derived earlier we obtain a branch-and-cut algorithm that significantly outperforms the best exact solution algorithm currently available in the literature.

Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. For combinatorial LP beyond directed graphs this gap between exact and high-accuracy solvers is currently quadratic. We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor.

We give a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all linear programs with at most two variables per inequality. Previously, strongly polynomial algorithms were only known for the primal and dual feasibility problems. Our approach is to show that the path-following interior point method of Allamigeon et al. '22 terminates in a strongly polynomial number of iterations for minimum cost generalized flow. We achieve this by bounding the 'straight line complexity' of the central path, which is the minimum number of pieces required by a piecewise affine curve to multiplicatively approximate the central path.

Based on joint work with Daniel Dadush, Bento Natura, Neil Olver and László Végh.