The equitability theorem for matroids says that if the ground set of a matroid can be partitioned into $k$ bases, then the elements of any prescribed subset can be distributed almost equally among the bases. In our paper Weighted Equitability and Matroid-Constrained Discrepancy, we prove a weighted analogue: for arbitrary nonnegative weights, there is a…
Frank’s min–max theorem gives an exact relation between maximum joins and optimal ear decompositions in graphic matroids. In our paper Joins and ear decompositions beyond graphic matroids, we investigate how far this relation extends beyond the graphic setting. The exact equality already fails for cographic matroids, and computing a maximum join is NP-hard even in…
Our paper Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations was accepted to FOCS 2026! The paper studies the Steiner Rooted Orientation problem introduced by Király and Lau at FOCS 2006. Given an undirected graph, a root vertex, a set of $t$ terminals, and a connectivity requirement $k$, the goal is to…
Motivated by the exact weight perfect matching problem and recent parameterized algorithms for finding an $\ell$-th smallest perfect matching, in the paper A hierarchy of edge-weight symmetries in perfect matchings we study structural properties of edge-weight symmetries in graphs. Recent work by El Maalouly et al. (ESA 2025) showed that excluding all perfect matchings whose…
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct colors. Since finding such a tree is NP-hard in general, previous work often relied on minimum color degree conditions to guarantee the existence of…