3 citations · 6 across the 18 of their papers we have counts for
21 papers
Near-Feasible Solutions to Complex Stable Matching Problems
Gergely Csáji
In this paper, we demonstrate that in many NP-complete variants of the stable matching problem, such as the Stable Hypergraph Matching problem, the Stable Multicommodity Flow probl…
Stable Hypergraph Matching in Unimodular Hypergraphs
Péter Biró, Gergely Csáji, Ildikó Schlotter
We study the NP-hard Stable Hypergraph Matching (SHM) problem and its generalization allowing capacities, the Stable Hypergraph -Matching (SHM) problem, and investigate their…
Ex-post Stability under Two-Sided Matching: Complexity and Characterization
Haris Aziz, Gergely Csáji, Péter Biró
A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, e…
Extending Stable and Popular Matching Algorithms from Bipartite to Arbitrary Instances
Gergely Csáji
We consider stable and popular matching problems in arbitrary graphs, which are referred to as stable roommates instances. We extend the 3/2-approximation algorithm for the maximum…
The NTU Partitioned Matching Game for International Kidney Exchange Programs
Gergely Csáji, Tamás Király, Zsuzsa Mészáros-Karkus
Motivated by the real-world problem of international kidney exchange (IKEP), recent literature introduced a generalized transferable utility matching game featuring a partition of…
Popular Maximum-Utility Matchings with Matroid Constraints
Gergely Csáji, Tamás Király, Kenjiro Takazawa +1
We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where ve…
Popularity and Perfectness in One-sided Matching Markets with Capacities
Gergely Csáji
We consider many-to-one matching problems, where one side corresponds to applicants who have preferences and the other side to houses who do not have preferences. We consider two d…
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…
Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
Márton Benedek, Péter Biró, Gergely Csáji +3
In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries try to merge their national patient-don…
Permutation Tutte polynomial
Csongor Beke, Gergely Kál Csáji, Péter Csikvári +1
The classical Tutte polynomial is a two-variate polynomial associated to graphs or more generally, matroids. In this paper, we introduce a polynomial $\widetilde{T}_H(x,…
The Merino--Welsh conjecture is false for matroids
Csongor Beke, Gergely Kál Csáji, Péter Csikvári +1
The matroidal version of the Merino--Welsh conjecture states that the Tutte polynomial of any matroid without loops and coloops satisfies that $$\max(T_M(2,0),T_M(0,…
Popular Matchings under Preference Variation and an Algorithm for Popular Common Bases with Integral Comparison Margins
Gergely Csáji
Preference information in matching markets may be incomplete, criterion-dependent, or noisy. We study popular and dominant matchings under four forms of preference variation: indep…
Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to Stable Matchings
Gergely Csáji, Frederik Glitzner
The efficient computation of large matchings with desirable guarantees is a crucial objective in market design. However, even in simple two-sided matching markets with weak ordinal…
Optimal Capacity Modification for Many-To-One Matching Problems
Jiehua Chen, Gergely Csáji
We consider many-to-one matching problems, where one side consists of students and the other side of schools with capacity constraints. We study how to optimally increase the capac…
Maximum Stable Matching with Matroids and Partial Orders
Gergely Csáji, Tamás Király, Yu Yokoi
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, th…
On the complexity of packing rainbow spanning trees
Kristóf Bérczi, Gergely Csáji, Tamás Király
One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list o…
Manipulating the outcome of stable matching and roommates problems
Kristóf Bérczi, Gergely Csáji, Tamás Király
The stable marriage and stable roommates problems have been extensively studied due to their high applicability in various real-world scenarios. However, it might happen that no st…
Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity
Jiehua Chen, Gergely Csáji, Sanjukta Roy +1
We investigate verification and existence problems for prominent stability concepts in hedonic games with friends, enemies, and optionally with neutrals [8, 16]. We resolve several…
Strong core and Pareto-optimal solutions for the multiple partners matching problem under lexicographic preferences
Péter Biró, Gergely Csáji
In a multiple partners matching problem the agents can have multiple partners up to their capacities. In this paper we consider both the two-sided many-to-many stable matching prob…
Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial
Csongor Beke, Gergely Kál Csáji, Péter Csikvári +1
In this short note we show that a system with a ground set of size and (rank) function satisfying for ev…
A new quantum algorithm for the hidden shift problem in
Gergely Csáji
In this paper we make a step towards a time and space efficient algorithm for the hidden shift problem for groups of the form . We give a solution to the case when…