Hypergraph connectivity augmentation

In our paper titled Hypergraph connectivity augmentation in strongly polynomial time, we consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. The central theme of our work is to show that certain hypergraph network design problems admit solutions in which the number of hyperedges is polynomial…

Regular matroids at STOC

Our paper on regular matroids has been accepted to the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)! The paper provides an upper bound on the exchange distance of basis pairs in regular matroids. As a byproduct, we also verify a conjecture of Gabow from 1976 on the serial symmetric exchange property of…

Solution for a long-standing conjecture of Thomassen

A classical theorem of Nash-Williams implies that every $2k$-edge-connected graph has a $k$-arc-connected orientation. In 1985, Thomassen asked whether a similar statement is true for vertex-connectivity, and formulated a conjecture stating that for every positive integer $k$ there exists a smallest integer $f(k)$ such that every $f(k)$-connected graph has a $k$-connected orientation. In a recent…

Approximating maximum-size properly colored forests

In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in which any two adjacent edges have distinct colors. The problem is interesting not only from a graph coloring point of view, but is also closely…

Workshop on Matroid-Constrained Optimization Problems

We are organizing a Workshop on “Matroid-Constrained Optimization Problems” at the Institut Henri Poincaré (IHP) in Paris, France April 2-3, 2024. We intend to bring together a small group (25-35) of people working on matroid-related optimization problems for two half days, with keynote talks given by Britta Peis (RWTH Aachen) and Rico Zenklusen (ETH Zurich). Further, we plan to have…