Problems on group-labeled matroid bases

Consider a matroid equipped with a labeling of its ground set to an abelian group, and define the label of a subset of the ground set as the sum of the labels of its elements. In our paper Problems on group-labeled matroid bases, we study a collection of problems on finding bases and common bases…

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…