1 citations · 1 across the 8 of their papers we have counts for
11 papers
Testing the max-flow min-cut property and the replication conjecture
Ahmad Abdi, Tamás Schwarcz
The replication conjecture [Conforti and Cornuéjols, 1993] states that every clutter with the packing property has the MFMC property. If true, this conjecture would have far-reachi…
Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
Kristóf Bérczi, Florian Hörsch, András Imolay +1
Finding a Steiner strongly -arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set…
Generalizing the Multiple Exchange Property for Matroid Bases
Taihei Oki, Tamás Schwarcz
The multiple exchange property for matroid bases states that for any bases and of a matroid and any subset , there exists a subset $Y\subseteq B\se…
Interaction between skew-representability, tensor products, extension properties, and rank inequalities
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
Skew-representable matroids form a fundamental class in matroid theory, bridging combinatorics and linear algebra. They play an important role in areas such as coding theory, optim…
Towards the Proximity Conjecture on Group-Labeled Matroids
Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki +2
Consider a matroid whose ground set is equipped with a labeling to an abelian group. A basis of is called -avoiding if the sum of the labels of its elements is not in a…
Matroid products via submodular coupling
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the…
Monotonic Decompositions of Submodular Set Functions
Kristóf Bérczi, Boglárka Gehér, András Imolay +2
Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions ha…
Problems on Group-labeled Matroid Bases
Florian Hörsch, András Imolay, Ryuhei Mizutani +2
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We st…
Approximating maximum-size properly colored forests
Yuhang Bai, Kristóf Bérczi, Gergely Csáji +1
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 whic…
Partitioning into common independent sets via relaxing strongly base orderability
Kristóf Bérczi, Tamás Schwarcz
The problem of covering the ground set of two matroids by a minimum number of common independent sets is notoriously hard even in very restricted settings, i.e.\ when the goal is t…
Hypergraph characterization of split matroids
Kristóf Bérczi, Tamás Király, Tamás Schwarcz +2
We provide a combinatorial study of split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. A nice feature of split mat…