5 papers · 1 filter
Finding Spanning Trees with Perfect Matchings
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi +2
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:…
Multiway Cuts with a Choice of Representatives
Kristóf Bérczi, Tamás Király, Daniel P. Szabo
In this paper, we study several generalizations of multiway cut where the terminals can be chosen as \emph{representatives} from sets of \emph{candidates} . In this…
Matroid Intersection under Minimum Rank Oracle
Mihály Bárász, Kristóf Bérczi, Tamás Király +3
In this paper, 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 o…
Hypergraph Connectivity Augmentation in Strongly Polynomial Time
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where…
Splitting-off in Hypergraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of…