In the paper Multiway Cuts with a Choice of Representatives, appearing at MFCS 2024, we study several generalizations of multiway cut where the terminals can be chosen as representatives from sets of candidates $T_1,\dots,T_q$. In this setting, one is allowed to choose these representatives so that the minimum-weight cut separating these sets via their representatives…
In the paper paper Matroid Intersection under Minimum Rank Oracle, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set of elements, and returns as its output the minimum of the ranks of the given set…
In our recent paper titled Finding Spanning Trees with Perfect Matchings, we investigate the tractability of a simple fusion of two fundamental structures on graphs, a spanning tree and a perfect matching. Specifically, we consider the following problem: given an edge-weighted graph, find a minimum-weight spanning tree among those containing a perfect matching. On the…
The research group will present two papers at ESA! The first one, Approximating maximum-size properly colored forests deals with the problem of finding a maximum sized properly colored forest in edge colored graphs. The second, Hypergraph Connectivity Augmentation in Strongly Polynomial Time considers hypergraph network design problems where the goal is to construct a hypergraph…
As a continuation of our work on the quotient-convergence of submodular setfunctions, in the paper Cycle Matroids of Graphings: From Convergence to Duality, we study the connection between local-global convergence of graphs and quotient-convergence of their cycle matroids. We characterize the exposed points of the associated convex set, forming an analytic counterpart of matroid base-polytopes.…