Stable Hypergraph Matching in Unimodular Hypergraphs
Abstract
We study the -hard Stable Hypergraph Matching (SHM) problem and its generalization allowing capacities, the Stable Hypergraph -Matching (SHM) problem, and investigate their computational properties under various structural constraints. Our study is motivated by the fact that Scarf’s Lemma [19] together with a result of Lovász [15] guarantees the existence of a stable matching whenever the underlying hypergraph is normal. Furthermore, if the hypergraph is unimodular (i.e., its incidence matrix is totally unimodular), then even a stable -matching is guaranteed to exist. However, no polynomial-time algorithm is known for finding a stable matching or -matching in unimodular hypergraphs.
We identify subclasses of unimodular hypergraphs where SHM and SHM are tractable such as laminar hypergraphs or so-called subpath hypergraphs with bounded-size hyperedges; for the latter case, even a maximum-weight stable -matching can be found efficiently. We complement our algorithms by showing that optimizing over stable matchings is -hard even in laminar hypergraphs. As a practically important special case of SHM for unimodular hypergraphs, we investigate a tripartite stable matching problem with students, schools, and companies as agents, called the University Dual Admission problem, which models real-world scenarios in higher education admissions.
Finally, we examine a superclass of subpath hypergraphs that are normal but not necessarily unimodular, namely subtree hypergraphs where hyperedges correspond to subtrees of a tree. We establish that for such hypergraphs, stable matchings can be found in polynomial time but, in the setting with capacities, finding a stable -matching is -hard.
Keywords and phrases:
stable hypergraph matching, Scarf’s Lemma, unimodular hypergraphs, university dual admissionCategory:
Track A: Algorithms, Complexity and GamesFunding:
Péter Biró: Supported by the Hungarian Scientific Research Fund (OTKA grant no. K143858).Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithms ; Theory of computation Algorithmic mechanism design ; Mathematics of computing HypergraphsAcknowledgements:
We are grateful for the reviewers of ICALP 2025 for their valuable comments.Funding:
Supported by the Hungarian Academy of Sciences under Momentum grant no. LP2021-2.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Stable matchings are fundamental in economics, combinatorial optimization, and mechanism design, playing a crucial role in applications such as college admissions, job markets, and organ exchange programs. Since the seminal work of Gale and Shapley [12], stable matchings have been extensively studied in two-sided markets where agents form pairwise relationships. However, many real-world scenarios require interactions beyond pairwise relationships, leading naturally to hypergraph-based formulations.
The focus of our study is the Stable Hypergraph -Matching (SHM) problem, where we are given a hypergraph whose vertices represent agents, with each agent having preferences over the incident hyperedges and, additionally, a capacity value . The task is to find a stable -matching, i.e., a set of hyperedges where each agent is adjacent to at most hyperedges in , and no hyperedge outside is “desirable” for all agents in ; see Section 2 for the precise definition of stability.
In the context of hypergraph matchings, stability is often difficult to achieve, as stable solutions may not always exist. On the positive side, Scarf’s Lemma [19] guarantees the existence of a fractional stable solution in the SHM problem. Furthermore, a famous result of Lovász [15] in combination with Scarf’s Lemma ensures that in an instance of Stable Hypergraph Matching (SHM) – the restriction of SHM without capacities – with a normal hypergraph, a stable matching always exists. An even stronger result follows for unimodular hypergraphs, where the incidence matrix is totally unimodular: Scarf’s Lemma guarantees the existence of a stable -matching. However, these results only provide existential guarantees, leaving computational aspects largely unexplored.
Motivated by these structural insights, we investigate the computational complexity of finding stable (-)matchings in different hypergraph classes. Furthermore, we consider not only the problem of finding any stable (-)matching but also of computing maximum-weight stable solutions.
1.1 Our Contribution
We begin with a class inspired by a real-world problem: the University Dual Admission (UDA) problem which arises in higher education admissions where students apply to universities and internship programs simultaneously [10]. Although we show that a stable solution always exists by reducing UDA to SHM in a unimodular hypergraph, our proof does not directly lead to an efficient algorithm. though we are unable to settle the complexity of finding a stable solution in a general instance of UDA, we provide an algorithm that finds a maximum-weight stable solution and runs in time parameterized by the number of universities. To complement this, we prove that computing a maximum-size stable matching is -hard even without capacities, although we show that a stable matching can be found efficiently in this case. Additionally, we introduce a relaxation of stability, termed half-stability, and design a polynomial-time algorithm that always finds a half-stable matching.
Next, we investigate laminar hypergraphs, a class where hyperedges follow a hierarchical inclusion property. Leveraging their structure, we design a polynomial-time algorithm that finds a stable -matching whenever the input hypergraph is laminar. By contrast, we also establish that, even in the setting without capacities, finding a maximum-weight stable matching (or even a stable matching containing a fixed edge) is -hard.
We extend our study to a superclass of laminar hypergraphs, subpath hypergraphs, where hyperedges can be represented as subpaths of a path. Subpath hypergraphs naturally model scenarios where relationships or interactions are constrained along a linear structure, such as transportation networks or supply chains. We develop an algorithm parameterized by the largest hyperedge size for finding a maximum-weight stable -matching in such hypergraphs.
Finally, we consider a superclass of subpath hypergraphs, subtree hypergraphs, where hyperedges correspond to subtrees of an underlying tree. While these hypergraphs are not necessarily unimodular, they are still normal, which ensures the existence of a stable matching by the results of Lovász [15] and Scarf [19]. For the matching case without capacities, we provide a polynomial-time algorithm, which contrasts our result that computing a stable -matching for general capacities is -hard.
Possible applications that motivate the study of SHM for various hypergraph classes include problems related to budgeting in transportation networks, project selection management in companies, or coalition formation in politics; see the full version of our paper [4].
Our findings, summarized in Table 1, contribute to the understanding of stable matchings in structured hypergraphs, bridging theoretical guarantees with computational feasibility.
Matching | b-Matching | |||
Stable | Max-Weight Stable | Stable | Max-Weight Stable | |
UDA | P[R3.3] | NPh, XP()[T10,T11] | ?, XP()[T11] | NPh, XP()[T10,T11] |
Laminar | P [7] | NPh, XP() [T17,T18] | P [T15] | NPh, XP() [T17,T18] |
Subpath | P [7] | NPh, XP() [T17,T18] | ?, XP() [T18] | W[1]h, XP() [T24,T18] |
Subtree | P[T25] | NPh[T17] | NPh[T26] | NPh[T17] |
1.2 Related Work
In their seminal paper, Gale and Shapley [12] provided a model and an algorithmic solution for college admission problems. Their solution concept is called stability, which means that an application is fairly rejected by a college if the college filled its quota with better applicants. Gale and Shapley showed that their so-called deferred-acceptance (DA) algorithm always finds a stable solution that is optimal for the students if they are proposing in the algorithm.
The work of Gale and Shapley [12] inspired extensive research in mathematics, computer science, operations research, as well as in economics and game theory. For an overview, we recommend the reader to consult the book of Manlove [16] in computer science, the books of Roth and Sotomayor [18] and Haeringer [13] in economics. Besides the theoretical research, the DA algorithm has also been used in many important applications, firstly in the US resident allocation scheme (called NRMP) since 1952 [17] and also in several nationwide college admission and school choice programs.
One of our motivating problems originates in the Hungarian university scheme where it is possible to apply for a so-called dual program that consist of a normal university major together with an internship at a company. For a student to get accepted to such a dual program, both the university and the company have to grant admission, and these parties can have different rankings. Note that this feature is not integrated in the current admission system, as the hiring decisions of the companies are not shared with the central coordinators when conducting the matching algorithm, which causes serious coordination problems, see a detailed description of the problem by Fleiner et al. [10].
Rather independently from the topic of matching under preferences, Scarf [19] showed that so-called balanced NTU-games (a family of cooperative games with non-transferable utility) have non-empty core by providing a finite algorithm that computes a core solution in such games. Instead of introducing these game-theoretical notions, we only interpret and use Scarf’s Lemma in the context of stable matchings and -matchings in hypergraphs.
The Stable Hypergraph Matching problem, introduced by Aharoni and Fleiner [1], is essentially equivalent to the problem of finding a core solution in simple NTU-games, also known as core stability in hedonic coalition formation games [3, 21, 2]; in the hypergraph formulation of these problems, vertices represent agents and hyperedges represent the possible coalitions. The setting where agents have capacities, giving rise to the SHM problem, was introduced by Biró and Fleiner [5] who proposed a general framework and proved the existence of fractional stable solutions using Scarf’s Lemma for -matching problems. They also highlighted that the matching polytope has the integer property for normal hypergraphs, therefore the solution determined by Scarf’s algorithm for the SHM problem is always integer and thus corresponds to a stable matching.
However, the running time of computing a fractional solution by Scarf’s algorithm is not polynomial in general. The PPAD-hardness of computing a fractional stable matching was proved by Kintali et al. [14] and was linked with several other PPAD-hard combinatorial problems. Recently Csáji extended these PPAD-hardness results for the fractional stable matching problem for three-partite hypergraphs and for the stable allocation with couples problem [8]. On the positive side, for certain stable matching problems it was shown that Scarf’s algorithm terminates in polynomial time for some appropriately defined pivot rule. Very recently Faenza et al. [9] showed this property for the classical stable marriage problem, and Chandrasekaran et al. [7] for SHM for so-called arborescence hypergraphs (see Section 2 for the definition). Even though arborescence hypergraphs include subpath hypergraphs, the results by Chandrasekaran et al. [7] do not imply any of our results, as they involve neither capacities nor optimization over stable matchings.
Organization.
We start by introducing the necessary notation and formally define our studied computational problems in Section 2. We proceed with the University Dual Admission (UDA) problem in Section 3 as a practical example of SHM. We move on to more abstract unimodular hypergraph classes in Section 4: in Section 4.1 we study the class of laminar hypergraphs, while in Section 4.2 we focus on the more general class of subpath hypergraphs. We examine subtree hypergraphs in Section 5, and finally conclude in Section 6.
Results marked with () have their proofs deferred to the full version of our paper [4].
2 Preliminaries
In Section 2.1 we define the concepts related to hypergraphs that we need in our paper, and in Section 2.2 we provide the definition of the computational problems we investigate.
2.1 Notation and Terminology
We use the notation for each positive integer . We let , and denote the set of integers, non-negative integers, reals, and non-negative reals, respectively. For the basic graph terminology and related standard notation we use, see the full version [4].
Matrices, polyhedra and Scarf’s Lemma.
For a matrix , we let denote its th row. A matrix is totally unimodular or TU if each subdeterminant of has value in . Totally unimodular matrices are known for their useful properties. Most importantly, if is TU and is integral, then all extreme points of the polyhedron are integral. A point in the polyhedron is an extreme point if it cannot be written as a strictly convex combination of two different points in the polyhedron. That is, there are no and such that .
A matrix is a network matrix if it can be obtained from a directed graph and an edge set of for which is a spanning tree of in the undirected sense, via the following method. With each row of we associate an edge , and with each column we associate an edge . Given edges and , let denote the unique cycle (in the undirected sense) contained in . Then, the entry of at the intersection of row and column has value
-
, if is contained in , and the edges and have the same orientation along ;
-
, if is contained in , and and have a different orientation along , and
-
, if is not contained in the cycle .
It is well known that network matrices are totally unimodular (see [20, Theorem 13.20]).
The following is a key lemma of Scarf [19], useful for many stable matching problems.
Lemma 1 (Scarf [19]).
Let be a matrix such that every column of has a nonzero element, and let . Suppose that every row has a strict ordering over those columns for which . Then there exists an extreme point of that dominates every column in some row, where we say that dominates column in row if , , and for all such that . Also, such an extreme point can be found by a finite algorithm.
Hypergraphs, matchings and -matchings.
A hypergraph contains a set of vertices and a set of hyperedges; we may simply refer to hyperedges as edges when this causes no confusion. We will say that a hyperedge is incident to a vertex if . The incidence matrix of a hypergraph has rows and columns, and the entry at the intersection of column and hyperedge is if is incident to , and otherwise. For a subset , let .
Given a hypergraph , a matching is a subset that satisfies that for every . A matching leaves a vertex unmatched if , otherwise it covers . Given capacities for each , we say that is a -matching if for each . For a -matching , we say that is unsaturated in if , saturated if , and oversaturated if .
Hypergraph classes.
Let us now describe the hypergraph classes relevant to our paper.
Let be a hypergraph, and let be any partial hypergraph of , obtained by deleting some of its edges. The chromatic index of a hypergraph, denoted , is the smallest number of colors required to color its edges such that no two edges of the same color share a common vertex. It is clear that the maximum degree – the largest number of edges incident to any single vertex – provides a lower bound for .
Definition 2.
A hypergraph is normal if for every partial hypergraph of .
Lovász [15] provided an alternative characterization of normal hypergraphs.
Theorem 3 (Lovász).
A hypergraph is normal if and only if all extreme points of the polyhedron are integral, where is the incidence matrix of .
An important subclass of normal hypergraphs is the class of unimodular hypergraphs.
Definition 4.
A hypergraph is unimodular if its incidence matrix is totally unimodular.
Next, we introduce subclasses of unimodular hypergraphs.
-
A network hypergraph is a hypergraph whose incidence matrix is a network matrix.
-
Arborescence hypergraphs are a subclass of network hypergraphs: is an arborescence hypergraph if there is an arborescence over such that each edge of forms a directed path in .
-
Subpath hypergraphs are the special case of arborescence hypergraphs where the underlying arborescence is required to be a path. Formally, is a subpath hypergraph if there exists a directed path over such that each edge of forms a subpath in .
-
A laminar hypergraph is a hypergraph for which there are no two hyperedges that satisfy and . Laminar hypergraphs are known to be subpath hypergraphs; although this seems to be folklore, we provide a proof in the full version of our paper [4].
Finally, we define a superclass of arborescence hypergraphs. A hypergraph is a subtree hypergraph if there is a tree on the ground set such that each hyperedge induces a subtree of . While subtree hypergraphs are not necessarily unimodular, they still form a subclass of normal hypergraphs [6, Section 4.4].
The full version of our paper [4] offers a full, graphical overview of the inclusion relations among these hypergraph classes.
2.2 Stable Hypergraph Matching
Let us start by defining the Stable Hypergraph Matching and Stable Hypergraph -Matching problems. Let be a hypergraph. For each we are given a strict preference list over the set of hyperedges containing . In the case of Stable Hypergraph -Matching, we are also given capacities for each .
Definition 5.
A hyperedge is dominated by a (-)matching at some vertex if is saturated in and for each hyperedge . A hyperedge blocks if and there exists no vertex at which dominates . A (-)matching is stable if no hyperedge blocks it.
The most important question in such instances is to find a stable matching or -matching. Hence, we get the following computational problem.
Stable Hypergraph -Matching or SHM
Input:
A hypergraph with capacities and strict preferences over incident edges for each vertex in .
Output:
Find a stable hypergraph -matching in .
Stable Hypergraph Matching (or SHM) is defined analogously for matchings instead of -matchings. It is clear that SHM is a subcase of SHM where we have .
For Unimod, Subpath, Subtree, we denote by -SHM and -SHM the restrictions of SHM and SHM to unimodular, subpath, or subtree hypergraphs, respectively.
As was observed by Aharoni and Fleiner [1], every stable hypergraph matching for an instance of SHM with hypergraph can be seen as an integral point in the polyhedron that dominates every column according to the preferences , where is the incidence matrix of . Thus, Scarf’s Lemma and Theorem 3 imply the existence of a stable matching if the hypergraph is normal. Furthermore, for an instance of SHM, the integral points of the polyhedron that dominate every column correspond to the stable hypergraph -matchings, where (with a slight abuse of notation) is the vector containing the capacities of the vertices. If the incidence matrix is TU, then all extreme points of this polyhedron are integral, and thus Scarf’s Lemma guarantees the existence of a stable -matching whenever the underlying hypergraph is unimodular. The guaranteed existence of a stable matching or stable -matching makes the class of normal hypergraphs and its subclass, unimodular hypergraphs, particularly interesting and useful.
Although the existence of a stable matching or -matching may be guaranteed in restricted hypergraph classes, it is also of interest to find a maximum-weight stable hypergraph matching. For this, an optimization variant of SHM (and SHM) can be formulated by associating a weight with each hyperedge. Given a weight function over a set of hyperedges, we extend it by setting for each .
Maximum-Weight SHM or MaxW-SHM
Input:
A hypergraph with capacities , weights , and strict preferences over incident edges for each vertex in .
Output:
Find a maximum-weight stable hypergraph -matching in .
We will refer to the optimization variant of the matching case, i.e., SHM as Maximum-Weight SHM or MaxW-SHM. For Unimod, Subpath, Subtree, we denote by -MaxW-SHM and -MaxW-SHM the restrictions of MaxW-SHM and MaxW-SHM to unimodular, subpath, or subtree hypergraphs, respectively.
We remark that in the special case when the hypergraph is a bipartite graph, MaxW-SHM coincides with the maximum-weight stable -matching problem (MaxW-SM) which is solvable in polynomial time [11].
3 The University Dual Admission Problem
In this section, we introduce a practically relevant problem in student allocation which, as we will show, can also be modeled as a special case of Unimod-SHM.
The problem is motivated by practical situations where certain programs in higher education are funded jointly as a result of cooperation between universities and companies, leading to a more complicated dual admission system. In our model, motivated by a real scenario in Hungarian higher education, we assume that such programs, funded by various companies, can be treated independently from each other (even though different programs might be funded by the same company) – hence, we shift the focus from the funding companies to the programs themselves.
Formally, we have a set of universities, a set of programs for each university , and a set of students. The set of programs is denoted by . We may refer to the set of students, universities, and programs together as the set of agents. Each university has a capacity , and each program has a quota .
The students apply to both a university and a program available at university . Since each program uniquely determines the university offering it, this can alternatively be viewed as students applying simply to programs.111Nevertheless, universities play an important role in the admission problem, as will become clear in the definition of a stable assignment (Section 3). Thus, for each student we assume a strict preference order over the set of programs acceptable for . Additionally, each university has a strict preference order over the students, and each program has a strict ordering over the students. A triple is an acceptable triple if finds acceptable; note that we do not consider acceptability for universities or programs explicitly, as we implicitly assume that a student finds a program acceptable only if both the program and university offering it finds the student acceptable as well. We may treat acceptable triples as subsets of of size .
An assignment is a function mapping each student either to a program that is acceptable for , or to the special symbol meaning that is left unassigned. For simplicity, we assume that a program is acceptable for if and only if it is preferred by to . For a program , we let denote the set of students assigned to it by , and similarly, for a university we let denote the set of students assigned by to some program in . An assignment is feasible if for each and for each ; we say that a university or a program is unsaturated if the corresponding inequality is strict, otherwise it is saturated.
Definition 6.
A feasible assignment for an instance of UDA is stable if there is no blocking student–university–program triple, that is, a triple such that the following three conditions hold:
-
(i)
;
-
(ii)
satisfies one of the followings:
-
is unsaturated,
-
there is a student such that , or
-
;
-
-
(iii)
the program is unsaturated, or there is a student such that .
We are ready to formally define the corresponding computational problem.
University Dual Admission or UDA
Input:
An instance of UDA as described above.
Question:
Find a feasible and stable assignment for .
Let us remark that the above problem can easily be used to model a situation where students may apply either to university–program pairs or only to universities: to allow for this option, we simply need to create a dummy program for each university with quota whose preferences are identical to the preferences of .
A very natural idea to solve UDA is to use a Gale–Shapley-like proposal–rejection algorithm and iterate it until it outputs a stable matching. We give an example where a student-proposing variant of the Gale–Shapley algorithm goes into an infinite loop when used on an instance of UDA, even if students propose in a lexicographic order. It is also possible to create instances where universities or programs propose but the algorithm still cycles in a similar way. This suggests that the problem should be solved in a different manner.
3.1 Formulating UDA as a Special Case of SHM
In this section, we first show that UDA can be formulated as a special case of the Unimod-SHM, and as a consequence, a stable assignment always exists for every instance of UDA. By contrast, we also prove that a stable assignment of maximum size is -hard to find.
Definition 7.
Given an instance of UDA, let denote the hypergraph associated with whose vertices are the agents in and whose hyperedges are the acceptable triples in . We say that a hypergraph has the UDA property if it can arise as for some instance of UDA.
We call UDA-SHM and UDA-MaxW-SHM the restriction of SHM and MaxW-SHM to hypergraphs having the UDA property, respectively.
To create an instance of SHM that is equivalent with our instance of UDA, we also need to define a strict ranking over the hyperedges of incident to each student, university, or program. For a student , his preference list in can be viewed as a preference list over its incident hyperedges: prefers a hyperedge over if and only if . For a program , the preference order similarly defines a ranking over the incident hyperedges, as each such hyperedge contains the same university . For a university , we extend its preference list to all incident hyperedges the following way. We let prefer to if and only if either or and . Let denote the preferences of agent in thus defined.
Additionally, we define the capacity function over the vertices of as
Theorem 8 ().
Stable assignments of an instance of UDA correspond bijectively to the stable -matchings of the instance of SHM.
Theorem 9.
For each instance of UDA, the associated hypergraph is a network hypergraph.
Proof.
We create a directed graph together with a spanning tree in the undirected graph obtained by replacing each arc of by an edge between and . We will show that the incidence matrix of is exactly the network matrix that corresponds to with the spanning tree .
We create a vertex in for each student, university, and program, and we further define an additional vertex . Formally, we set The set of arcs is defined as follows. First, for each program at some university , we add an arc . Second, for each university , we add an arc . Third, for each student , we add an arc . Let denote the set of arcs defined so far. Finally, for each acceptable triple , i.e., for each hyperedge in , we add an arc . It is straightforward to see that is a spanning tree in . Let be the network matrix associated with and . Note that the edges of are in a one-to-one correspondence with the vertices of the hypergraph , i.e., the set of agents in . Furthermore, the edges of are in a one-to-one correspondence with the hyperedges of .
Thus, it only remains to show that is indeed the incidence matrix of , i.e., if a vertex is contained in a hyperedge , then the corresponding entry in is 1, and 0 otherwise. To see this, consider the unique cycle defined by an arc corresponding to some hyperedge , which is the cycle formed by the four edges , , , and . Observe that contains exactly three arcs of , namely the arcs of corresponding to the three vertices (i.e., agents) incident to . Hence, there are exactly three non-zero entries in the column of corresponding to , and these three entries are in the three rows that correspond to the vertices incident to . Moreover, since all arcs of have the same orientation along , each of these three entries of has value , as required.
While Theorems 8 and 9 guarantee the existence of a stable assignment for every UDA instance, a maximum-size stable assignment is -hard to find, where the size of an assignment is the number of students it assigns to some program.
Theorem 10 ().
Finding a maximum-size stable assignment in an instance of UDA is -hard, even if all capacities are one.
To handle this computational difficulty, we formulate an integer program whose solutions are exactly the stable assignments for an instance of UDA; see the full version [4].
3.2 An XP Algorithm for UDA-MaxW-SHM
Let us describe an algorithm for an instance of UDA-MaxW-SHM, where over vertex set is a hypergraph that satisfies the UDA property. Let . We can assume that , where the vertices satisfy that for any , we have .
The pseudocode of the algorithm is given in Algorithm 1. As a first step, we guess a strategy , that is, for each we guess whether it will be saturated in the solution, and if so, what will be the worst hyperedge adjacent to . Then, we create an instance of MaxW-SM, the maximum-weight bipartite stable -matching problem. The underlying graph of will be the bipartite graph where contains an edge if (i) there is a (unique) vertex such that and (ii) for that vertex , , where we assume that always holds. The preferences of the agents in are the projection of their original preferences. This is well defined, as each edge uniquely defines a hyperedge ; we further set , , and so that capacities and weights remain the same.
Let us say that a -matching in is valid if, satisfies that for each , whenever , and otherwise.
For a given strategy , the algorithm proceeds by computing a maximum-weight stable -matching in . If is valid, then it adds the -matching corresponding to to a set . If is not valid, then we discard the guessed strategy . Finally, we output a maximum-weight stable -matching from .
Theorem 11.
UDA-MaxW-SHM can be solved in time, where correspond to the class of universities and is the maximum degree of a vertex .
Proof.
We show that at the end of Algorithm 1, will contain a maximum-weight stable -matching for .
Claim 12.
If is a valid stable -matching in , then the corresponding -matching is feasible and stable in .
Proof.
Let be a valid stable -matching in and let be defined as in the statement of the claim. Then, is a feasible -matching in : for , follows from , and the capacities of the agents are respected due to the validity of . It remains to show that is stable in .
For a hyperedge , let . Suppose on the contrary that a hyperedge blocks . First, if , then as (respectively, ) is either unsaturated in both and , or () for some () implying (); this means that the edge blocks , a contradiction. Second, if , then . In particular, and due to the validity of we know that is saturated in . Moreover, by construction, any edge satisfies . Therefore, is saturated in with hyperedges that are not worse for than . Hence cannot block , a contradiction.
Claim 13.
Suppose that is a stable -matching in . Define such that is the worst hyperedge in according to if is saturated in , and otherwise. Then every stable -matching in is valid.
Proof.
Let be the -matching in defined as . By the definition of , it holds that , and moreover, is valid by construction. We claim that is stable in .
To show that is stable in , assume for the sake of contradiction that some edge blocks . Then, both and are either unsaturated or prefer to some edge in . Since is stable, this means that the hyperedge must be dominated at . Therefore, we get that is saturated in and . However, then the edge cannot be contained in , a contradiction.
Due to the many-to-many extension of the well-known Rural Hospitals Theorem (see e.g., [11]), for any stable -matching in , we have for all . Hence, all stable -matchings of must be valid, because for any stable -matching and its corresponding -matching in , we have for by the UDA property. This concludes the proof.
As we know that a stable -matching for exists, Section 3.2 guarantees that by iterating over all possible strategies, the algorithm is bound to find the strategy corresponding to the maximum-weight stable -matching . By Sections 3.2 and 3.2, will be a valid stable -matching for , and since any valid -matching gives a stable -matching in with , the algorithm indeed puts or a stable -matching with the same weight in .
Since there are at most possible strategies to check, and for each one them, the instance and a maximum-weight stable -matching in can be computed in time by a result of Fleiner [11], the claimed running time also follows.
3.3 Further Results
On the positive side, we define a relaxed notion of stability in UDA, called half-stability, which intuitively means that for a triple to block, if the program is saturated, then the university and the program should be able to agree on a student that can be rejected; we show that we can find a half-stable assignment in polynomial time. See the full version of our paper [4] for further details.
Remark 14.
If for all universities, then a simple deferred acceptance algorithm between the students and universities produces a stable assignment; see the full version [4].
4 SHM for Unimodular Hypergraphs
We proceed to study Unimod-SHM in further classes of unimodular hypergraphs.
4.1 Laminar Hypergraphs
We construct a polynomial-time algorithm that finds a stable -matching if the hypergraph is laminar. As laminar hypergraphs are unimodular, the existence of a stable -matching is guaranteed. We present our algorithm for this problem in Algorithm 2.
Theorem 15.
Laminar-SHM is solved in polynomial time by Algorithm 2.
Proof.
First, let us show that the set returned by Algorithm 2 is a -matching. Observe that whenever some hyperedge is added to on line 7, the set constructed on line 9 covers every vertex that became oversaturated as a consequence of adding . Therefore, also covers these vertices, so after the removal of all hyperedges of from the matching, the resulting set again satisfies all capacity constraints. Therefore, the algorithm indeed returns a -matching .
It remains to show that is stable. Consider the iteration of lines 4–10 during Algorithm 2 where some hyperedge is picked on line 4, and let and denote the current -matching at the beginning and at the end of this iteration, respectively. We need the following claim.
Claim 16.
For any edge added to the -matching at line 7, the set is a family of pairwise disjoint hyperedges whose union is a subset of , with .
Proof.
Since the algorithm always picks an inclusion-wise minimal hyperedge on line 4, the laminarity of implies that every hyperedge that had been checked (i.e., put into ) before is either a subset of or is disjoint from it. In particular, since the algorithm only puts hyperedges of the current -matching into , we get that all hyperedges in are contained in (recall that shares at least one oversaturated vertex with each hyperedge in ). Since contains only the inclusion-wise maximal sets from , the laminarity of implies that the hyperedges in are pairwise disjoint.
To see , it suffices to observe the following. Since blocks the current -matching , for each that is oversaturated in we know that cannot be the worst hyperedge incident to in .
Consider now the iteration during which is picked on line 4. If the algorithm adds to the current -matching on line 4, then , otherwise . Hence, the above claim implies for each , since can only be incident to at most one hyperedge in . Moreover, if for some , then the worst hyperedge in is weakly preferred by to the worst hyperedge in : this is obvious if , and if , then prefers to at least one hyperedge in , so ’s worst hyperedge cannot be worse than before, as is the only new hyperedge in not in already. Hence, whenever some vertex becomes saturated with hyperedges better than some , then this remains true during the remainder of the algorithm. We refer to this observation as the saturation-monotonicity of the algorithm.
To prove the stability of , consider an arbitrary edge and the iteration during which is examined at line 4. If is not added to on line 7, then some vertex incident to must be saturated in with hyperedges that are all preferred to by . By the saturation-monotonicity of the algorithm, this remains true for the returned -matching , so cannot block . By contrast, if is added to on line 7, then must have been removed at some point on line 10 during a later iteration as a consequence of adding some hyperedge to the -matching on line 7 for which . By our construction of , we know that is the worst hyperedge for some vertex in , so after removing from the -matching , vertex is saturated with hyperedges that are all preferred by to . Again, by the saturation-monotonicity of the algorithm, this remains true for during the algorithm, so cannot block . Thus, is indeed a stable -matching for .
In every iteration, a hyperedge of gets added to , so there are iterations. As each iteration can be performed in linear time, the running time is polynomial.
We complement Theorem 15 by a hardness result for a very restricted weight function.
Theorem 17 ().
The MaxW-Laminar-SHM problem is -complete on laminar hypergraphs, even if all edges have weight with the exception of a single edge of weight .
4.2 Subpath Hypergraphs
Moving our focus to instances of SHM where the underlying hypergraph is a subpath hypergraph, we present an algorithm for the MaxW-Subpath-SHM problem that runs in polynomial time if the maximum size of a hyperedge in is bounded by a constant.
Theorem 18.
MaxW-Subpath-SHM can be solved in time for an instance (, where is the maximum capacity of a vertex, is the maximum size of an edge in , is the maximum degree of a vertex, and is the maximum absolute value of over .
A brute-force approach to solve the MaxW-Subpath-SHM problem would be to consider the edges one-by-one and enumerate all possible -matchings that do not violate the capacities and that may turn out to be stable in the end. However, such a brute-force method would not yield a polynomial-time algorithm even if is constant. Hence, we apply a more sophisticated approach using dynamic programming: we process edges one-by-one, but instead of recording all possible partial solutions, we only maintain a smaller set of -matchings that, in a certain sense, represents all possible strategies for obtaining a stable -matching. We start by introducing the necessary concepts.
Strategies.
A strategy over a given set of vertices is a function such that is incident to for each unless . The interpretation of a strategy is that is the planned threshold of , that is, the worst edge that we plan to put into the -matching among those incident to ; the symbol corresponds to being unsaturated. We extend the notation such that holds for each incident to .
Definition 19.
A -matching realizes a strategy over w.r.t. some if
-
(i)
is compatible with , meaning that for each :
-
if , then holds for every , and
-
if , then ;
-
-
(ii)
for each with , and
-
(iii)
every edge in that blocks is planned to be dominated by where we say that plans to dominate an edge if there exists some such that .
We call a strategy realizable for an edge set if some -matching realizes it w.r.t. .
Observe that if a strategy plans to dominate an edge at some vertex and is a -matching compatible with that also satisfies , then cannot block , because is dominated by at , meaning that contains edges incident to , and prefers each of them to .
Given a strategy over and a -matching compatible with , we say that is complete on a vertex set for if for each such that .
The algorithm.
Let be our instance of MaxW-Subpath-SHM with a subpath hypergraph , and let be the ordering of witnessing the subpath property of . That is, for each hyperedge there exist indices such that .
For a hyperedge , we write and we say that is the endpoint of . Let be an ordering of where implies , that is, we order the edges increasingly according to their endpoints. Let , and let contain the last vertices contained in , that is, .
Our algorithm considers each set , and computes a set of pairs where is a strategy over and is a -matching in that realizes . We will ensure that is representative for in the following sense:
Definition 20.
Set is -representative for if the following holds:
whenever there is a strategy and a -matching realizing with respect to ,
then there is a -matching equivalent to on for which and .
Here, is equivalent to on ,
if for each ; this is denoted by .
The operation of
updating with means that
we put into
unless
there is some pair already in for which is equivalent on to and .
We initialize to contain only where is the function with empty domain. For to , we build the set as follows; Algorithm 3 contains a formal description.
- Adjusting the domain from to :
-
For each , check whether is complete for on . If not, then we will not be able to make complete by adding edges from , so we ignore the pair . Otherwise, we change the domain of from to (forgetting all values assigned to vertices of ) as follows: We set for each to all possible values in , and for each strategy over obtained this way, we put into a set .
- Computing based on :
-
For each we check whether still realizes with respect to by checking if (i) plans to dominate , and (ii) for each , the threshold does not coincide with . If these conditions hold, then realizes with respect to . Hence, we update with . Next, we check whether we can add to : if adding does not violate the capacities and yields a -matching compatible with , then we update with .
The algorithm finishes by checking whether contains a pair where is complete for on , and if so, outputs among all such -matchings one that maximizes .
Lemma 21 ().
If Algorithm 3 puts a pair into for some , then realizes with respect to .
Proof sketch..
We use induction on . The case is trivial, so assume that the lemma holds for .
First, suppose that was added to on line 14, so . Let be selected on line 4 in the cycle during which was put into on line 10. By induction,
-
(a)
is compatible with ,
-
(b)
for every where , and
-
(c)
every edge in that blocks is planned to be dominated by .
First, observe that is compatible with : the compatibility conditions for each follow immediately from due to (a), while the compatibility condition for each holds irrespective of the value of , because edges of have no vertices in .
Second, by our assumption that Algorithm 3 added to on line 14, we know that for each incident to . Hence, if for some , then , and consequently, (because vertices of are not contained in any edge of ). Therefore, (b) implies . Third, it remains to show that every edge that blocks is planned to be dominated by . First note that Algorithm 3 checks that this holds for explicitly on line 13, so we may assume . By (c), we know that every edge in that blocks is planned to be dominated by , so there is some such that . On the one hand, if , then is planned to be dominated by too, because . On the other hand, if , then Algorithm 3 must have confirmed on line 10 that is complete on (otherwise it would not have put into ), which implies that dominates at . Thus, does not block , proving that every edge in that blocks is planned to be dominated by . This finishes the proof that realizes with respect to .
Lemma 22 ().
Set computed by Algorithm 3 is -representative for for each .
Proof sketch..
We prove the lemma by induction on . Clearly, the lemma trivially holds for , so let us assume that the statement holds for .
To prove that remains -representative for , it suffices to show the following: if is such that realizes with respect to , then the algorithm updates with some pair either at line 14 or at line 17 for which (note that is transitive) and .
Given and , let us define the strategy over as follows:
where is the worst edge in according to . Note that is complete on vertices of for . We distinguish between two cases.
Case A:
. It is then straightforward to check that realizes w.r.t. ; see [4] for a detailed proof. Therefore, by induction there exists a -matching with such that and .
Recall that is complete on for , and thus implies that is also complete on for . Hence, passes the test on line 5. As Algorithm 3 tries all possible ways to extend , it follows that . Now, since realizes w.r.t. but , we get that for any . Additionally, plans to dominate : if blocks , then this is because realizes w.r.t. (by our assumptions), and if does not block , then it is dominated at some vertex , which in turn implies that is saturated by and , that is, indeed plans to dominate . Therefore, Algorithm 3 updates with at line 14.
Case B:
. Consider the -matching . It is then straightforward to check that realizes w.r.t. ; see again [4]. Therefore, by induction there exists a -matching with such that and .
Recall that is complete on for , and thus implies that is also complete on for . Therefore, passes the test on line 5. As Algorithm 3 tries all possible ways to extend , it follows that . Since and is compatible with , we know that for each . By and since is a -matching, we know for each ; since , it is also clear that for each . Therefore, the pair satisfies the conditions on line 15 and so Algorithm 3 updates with at line 17. By and , this finishes the proof of the lemma.
Proof of Theorem 18.
Let us first prove that Algorithm 3 solves MaxW-Subpath-SHM correctly on subpath hypergraphs.
First, we show that the output is stable. Observe that if Algorithm 3 returns a -matching on line 22, then realizes on , and thus plans to dominate every edge blocking . However, as is complete for (due to the condition on line 20), in fact dominates every edge that plans to dominate. Thus, no edge may block .
Assume now that is a maximum-weight stable -matching in our instance. Let be the strategy over defined as
It is clear that realizes over . Thus, by Section 4.2 there exists a -matching satisfying for which and . Moreover, as is complete on for and , we know that is complete on for as well. Hence, Algorithm 3 will set to at least on line 21 at latest when it examines the pair , and will thus return a stable -matching of weight at least on line 22, which must be a maximum-weight stable -matching.
To bound the running time of Algorithm 3, note that the number of possible strategies for a given set is at most where is the maximum number of edges incident to any vertex. Given a strategy over , we also know since this set does not contain two -matchings that are equivalent on . This yields
There are iterations, and the computation of from is proportional to , as any line of the algorithm can be performed in time. Thus, we obtain that the total running time is , as promised.
Remark 23.
We remark that Algorithm 3 can be used to decide whether a stable -matching exists that contains a given set of “forced” edges (or is disjoint from a given set “forbidden” edges) by setting an appropriate weight function. Furthermore, it can also be used to decide the existence of a stable -matching that saturates (or does not saturate) a given vertex . Indeed, to decide whether some stable -matching saturates , it suffices to add a newly created hyperedge incident only to , extend the preferences of such that becomes the least-favorite edge according to , and decide whether this modified instance admits a stable -matching that does not contain . Deciding whether some stable -matching leaves unsaturated can be done analogously, using the same construction but searching for a stable -matching that contains .
Theorem 24 shows that the running time of the algorithm in Theorem 18 cannot be improved to an FPT algorithm with parameter , not even if we additionally parameterize the problem with the maximum capacity and severely restrict the weight function.
Theorem 24 ().
The MaxW-Subpath-SHM problem is -hard when parameterized by , where is the maximum capacity of a vertex and is the maximum size of an edge, even if all edges have weight with the exception of a single edge of weight .
5 SHM for Subtree Hypergraphs
We now turn our focus to the class of subtree hypergraphs. As these are not necessarily unimodular, so an instance of Subtree-SHM may not admit a stable -matching. However, as subtree hypergraphs are still normal, Subtree-SHM is guaranteed to be solvable.
We start by presenting a polynomial-time algorithm that solves Subtree-SHM. Before explaining our algorithm, let us introduce some additional notation. Let be a subtree hypergraph and let be the underlying tree, that is, for each hyperedge , the set of vertices contained in induces a subtree of . Let be a fixed vertex of and consider the rooted tree with root . For each vertex , let be the distance of and in , that is the number of edges of the (unique) path of between and . For each hyperedge , let be the (unique) vertex of that is closest to in , and define .
Given an instance of Subtree-SHM, where is a subtree hypergraph with underlying tree , algorithm Subtree-SHM does the following (see Algorithm 4 for a pseudocode). First, it finds a hyperedge such that is furthest from in ; for simplicity, let us write for . Then it deletes and every hyperedge incident to that are less preferred by than , and recursively calls itself on the remaining hypergraph. Finally, it builds a matching by adding to the output of the recursive call if is not covered by .
Theorem 25.
Algorithm 4 solves Subtree-SHM in polynomial time.
Proof.
The algorithm runs in polynomial time, because Subtree-SHM is called at most times recursively, and in each call, it only needs to compute the farthest hyperedge and delete those hyperedges incident to that are worse than for .
We show that the output is a stable hypergraph matching. We use induction on . If , then the output of Algorithm 4 is clearly a stable hypergraph matching.
Hence, assume that . Let be the hyperedge chosen by the algorithm in the first iteration. By induction, is a stable hypergraph matching in the subtree hypergraph .
First, suppose that saturates , so Algorithm 4 outputs . Then, is clearly a matching. Also, no hyperedge of blocks by induction. Finally, no hyperedge of blocks either, because is covered with some hyperedge such that for every by the choice of .
Suppose now that does not saturate , and the output is therefore . The fact that is a subtree hypergraph and that is chosen so that it maximizes implies that any hyperedge that intersects must also contain . Hence, as does not cover , is a matching. By induction, no hyperedge of blocks , and thus . Finally, no hyperedge of blocks , because for every and is saturated by .
We conclude that the output is a stable matching.
A natural question to ask whether a stable -matching can still be found efficiently in the SHM setting. Sadly, the answer is no, even with very severe restrictions.
Theorem 26 ().
Deciding if there exists an stable hypergraph -matching in an instance of Subtree-SHM is -hard, even if the underlying tree is a star, only one vertex has capacity greater than 1, and all hyperedge sizes are at most 4.
Remark 27.
Using the reduction presented in the proof of Theorem 26 and the fact that the problem of finding a stable fractional hypergraph matching is -complete even if each hyperedge has size [8], it is straightforward to verify that the problem of finding a stable fractional hypergraph matching in an instance of Subtree-SHM satisfying the conditions of Theorem 26 is -complete too.
6 Conclusions
We studied stable hypergraph matchings and -matchings, focusing on structured hypergraph families. We introduced the University Dual Admission problem and showed that it can be regarded as a special case of Unimod-SHM. We identified multiple classes of hypergraphs where stable (-)matchings can be found efficiently, and provided contrasting proofs of intractability; see Table 1 for a summary.
Besides some open questions in Table 1, the main problem we leave open for further research is whether it is possible to find a stable matching in an arbitrary instance of Unimod-SHM in polynomial time. Our complexity results seem to suggest that the problem might be computationally hard (e.g., PPAD-hard) in general; however, for special cases there is a potential for efficient combinatorial algorithms. In particular, resolving the complexity of this problem for network hypergraphs would be of great interest. More generally, the development of new techniques to attain stable solutions for instances of SHM and SHM is an important direction for future research that is motivated by various practical application such as the Hospitals/Residents with Couples problem [16, Chapter 5.3].
References
- [1] Ron Aharoni and Tamás Fleiner. On a lemma of Scarf. Journal of Combinatorial Theory, Series B, 87(1):72–80, 2003. doi:10.1016/S0095-8956(02)00028-X.
- [2] Haris Aziz and Florian Brandl. Existence of stability in hedonic coalition formation games. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), volume 2, pages 763–770, 2012. URL: http://dl.acm.org/citation.cfm?id=2343806.
- [3] Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez. Core in a simple coalition formation game. Social Choice and Welfare, 18(1):135–153, 2001. doi:10.1007/s003550000067.
- [4] Péter Biró, Gergely Csáji, and Ildikó Schlotter. Stable hypergraph matching in unimodular hypergraphs. arXiv:2502.08827 [cs.GT], 2025. doi:10.48550/arXiv.2502.08827.
- [5] Péter Biró and Tamás Fleiner. Fractional solutions for capacitated NTU-games, with applications to stable matchings. Discrete Optimization, 22:241–254, 2016. doi:10.1016/j.disopt.2015.02.002.
- [6] Alain Bretto. Hypergraph Theory: An Introduction. Mathematical Engineering. Springer Cham, 2013.
- [7] Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, and Jay Sethuraman. Scarf’s algorithm on arborescence hypergraphs. arXiv:2412.03397 [cs.DM], 2024. doi:10.48550/arXiv.2412.03397.
- [8] Gergely Csáji. On the complexity of stable hypergraph matching, stable multicommodity flow and related problems. Theoretical Computer Science, 931:1–16, 2022. doi:10.1016/j.tcs.2022.07.025.
- [9] Yuri Faenza, Chengyue He, and Jay Sethuraman. Scarf’s algorithm and stable marriages. arXiv:2303.00791 [math.CO], 2023. doi:10.48550/arXiv.2303.00791.
- [10] Rita Fleiner, András Ferkai, and Péter Biró. College admission problem for university dual education. In Proceedings of the IEEE 17th World Symposium on Applied Machine Intelligence and Informatics (SAMI 2019), pages 31–36. IEEE, 2019. doi:10.1109/SAMI.2019.8782783.
- [11] Tamás Fleiner. On the stable -matching polytope. Mathematical Social Sciences, 46(2):149–158, 2003. doi:10.1016/S0165-4896(03)00074-X.
- [12] David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962. doi:10.2307/2312726.
- [13] Guillaume Haeringer. Market Design: Auctions and Matching. MIT Press, 2018.
- [14] Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, and Shang-Hua Teng. Reducibility among fractional stability problems. SIAM Journal on Computing, 42(6):2063–2113, 2013. doi:10.1137/120874655.
- [15] László Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3):253–267, 1972. doi:10.1016/0012-365X(72)90006-4.
- [16] David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. World Scientific, 2013. doi:10.1142/8591.
- [17] Alvin E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92(6):991–1016, 1984. doi:10.1086/261272.
- [18] Alvin E. Roth and Marilda A. O. Sotomayor. Two-sided Matching: a Study in Game-theoretic Modeling and Analysis. Econometric Society Monographs, Cambridge, 1990.
- [19] Herbert E. Scarf. The core of an N person game. Econometrica, 35(1):50–69, 1967. doi:10.2307/1909383.
- [20] Alexander Schrijver. Combinatorial Optimization. Springer-Verlag Berlin Heidelberg, 2003.
- [21] Gerhard J. Woeginger. Core stability in hedonic coalition formation. In Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), volume 7741 of Lecture Notes in Computer Science, pages 33–50. Springer, 2013. doi:10.1007/978-3-642-35843-2_4.