Abstract 1 Introduction 2 Preliminaries 3 The University Dual Admission Problem 4 SH𝒃M for Unimodular Hypergraphs 5 SH𝒃M for Subtree Hypergraphs 6 Conclusions References

Stable Hypergraph Matching in Unimodular Hypergraphs

Péter Biró ORCID HUN-REN Centre for Economic and Regional Studies, Budapest, Hungary Gergely Csáji ORCID HUN-REN Centre for Economic and Regional Studies, Budapest, Hungary
Eötvös Loránd University, Budapest, Hungary
Ildikó Schlotter ORCID HUN-REN Centre for Economic and Regional Studies, Budapest, Hungary
Abstract

We study the 𝖭𝖯-hard Stable Hypergraph Matching (SHM) problem and its generalization allowing capacities, the Stable Hypergraph b-Matching (SHbM) 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 b-matching is guaranteed to exist. However, no polynomial-time algorithm is known for finding a stable matching or b-matching in unimodular hypergraphs.

We identify subclasses of unimodular hypergraphs where SHM and SHbM are tractable such as laminar hypergraphs or so-called subpath hypergraphs with bounded-size hyperedges; for the latter case, even a maximum-weight stable b-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 SHbM 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 b-matching is 𝖭𝖯-hard.

Keywords and phrases:
stable hypergraph matching, Scarf’s Lemma, unimodular hypergraphs, university dual admission
Category:
Track A: Algorithms, Complexity and Games
Funding:
Péter Biró: Supported by the Hungarian Scientific Research Fund (OTKA grant no. K143858).
Gergely Csáji: Supported by the Hungarian Scientific Research Fund (OTKA grant no. K143858) and by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme (grant no. C2258525).
Ildikó Schlotter: Supported by the Hungarian Academy of Sciences under its János Bolyai Research Scholarship.
Copyright and License:
[Uncaptioned image] © Péter Biró, Gergely Csáji, and Ildikó Schlotter; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithms
; Theory of computation Algorithmic mechanism design ; Mathematics of computing Hypergraphs
Related Version:
Full Version: https://doi.org/10.48550/arXiv.2502.08827 [4]
Acknowledgements:
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 Puppis

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 b-Matching (SHbM) problem, where we are given a hypergraph whose vertices represent agents, with each agent v having preferences over the incident hyperedges and, additionally, a capacity value b(v). The task is to find a stable b-matching, i.e., a set M of hyperedges where each agent v is adjacent to at most b(v) hyperedges in M, and no hyperedge e outside M is “desirable” for all agents in e; 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 SHbM 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 SHbM 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 b-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 (b-)matchings in different hypergraph classes. Furthermore, we consider not only the problem of finding any stable (b-)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 SHbM 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 b-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 b-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 b-matching for general capacities is 𝖭𝖯-hard.

Possible applications that motivate the study of SHbM 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.

Table 1: Computational complexity of finding an arbitrary or a maximum-weight stable (b-)matching in different hypergraph classes. NPh,P,XP, and W[1]h refers to 𝖭𝖯-hardness, polynomial-time solvability, solvability in 𝖷𝖯, and 𝖶[1]-hardness (the latter two with the given parameter), respectively. Parameter max is the size of the largest hyperedge and nU is the number of universities. Recall the hierarchy of hypergraphs which we may write informally as {laminar}{subpath}{subtree}.
Matching b-Matching
Stable Max-Weight Stable Stable Max-Weight Stable
UDA P[R3.3] NPh, XP(nU)[T10,T11] ?, XP(nU)[T11] NPh, XP(nU)[T10,T11]
Laminar P [7] NPh, XP(max) [T17,T18] P [T15] NPh, XP(max) [T17,T18]
Subpath P [7] NPh, XP(max) [T17,T18] ?, XP(max) [T18] W[1]h, XP(max) [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 b-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 SHbM 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 b-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 SHbM. 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 []={1,2,,} 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 A, we let Ai denote its ith row. A matrix A is totally unimodular or TU if each subdeterminant of A has value in {1,0,1}. Totally unimodular matrices are known for their useful properties. Most importantly, if A is TU and b is integral, then all extreme points of the polyhedron {xm:Axb,x0} are integral. A point z in the polyhedron {xm:Axb,x0} 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 λ(0,1) and z1,z2{xm:Axb,x0} such that z=λz1+(1λ)z2.

A matrix A is a network matrix if it can be obtained from a directed graph G=(V,E) and an edge set FE of G for which (V,F) is a spanning tree of G in the undirected sense, via the following method. With each row of A we associate an edge fF, and with each column we associate an edge eEF. Given edges fF and eEF, let Ce,f denote the unique cycle (in the undirected sense) contained in (V,F{e}). Then, the entry of A at the intersection of row f and column e has value

  • 1, if f is contained in Ce,f, and the edges e and f have the same orientation along Ce,f;

  • 1, if f is contained in Ce,f, and e and f have a different orientation along Ce,f, and

  • 0, if f is not contained in the cycle Ce,f.

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 A+n×m be a matrix such that every column of A has a nonzero element, and let b+n. Suppose that every row i[n] has a strict ordering i over those columns j[m] for which Aij>0. Then there exists an extreme point of {xm:Axb,x0} that dominates every column in some row, where we say that xm dominates column j in row i if Aij>0, Aix=bi, and kij for all k[m] such that Aikxk>0. Also, such an extreme point can be found by a finite algorithm.

Hypergraphs, matchings and 𝒃-matchings.

A hypergraph =(V,) contains a set V of vertices and a set 2V of hyperedges; we may simply refer to hyperedges as edges when this causes no confusion. We will say that a hyperedge e is incident to a vertex vV if ve. The incidence matrix of a hypergraph =(V,) has |V| rows and || columns, and the entry at the intersection of column vV and hyperedge e is 1 if e is incident to v, and 0 otherwise. For a subset F, let F(v):={eFve}.

Given a hypergraph =(V,), a matching is a subset M that satisfies that |M(v)|1 for every vV. A matching M leaves a vertex v unmatched if M(v)=, otherwise it covers v. Given capacities b(v)+ for each vV, we say that M is a b-matching if |M(v)|b(v) for each vV. For a b-matching M, we say that v is unsaturated in M if |M(v)|<b(v), saturated if |M(v)|=b(v), and oversaturated if |M(v)|>b(v).

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 χe(), 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 χe().

Definition 2.

A hypergraph is normal if χe()=Δ() 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 {xm:Ax1,x0} are integral, where A 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: =(V,) is an arborescence hypergraph if there is an arborescence F over V such that each edge of  forms a directed path in F.

  • Subpath hypergraphs are the special case of arborescence hypergraphs where the underlying arborescence is required to be a path. Formally, =(V,) is a subpath hypergraph if there exists a directed path F over V such that each edge of  forms a subpath in F.

  • A laminar hypergraph is a hypergraph =(V,) for which there are no two hyperedges e1,e2 that satisfy e1e2 and e2e1. 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 =(V,) is a subtree hypergraph if there is a tree F=(V,E) on the ground set V such that each hyperedge induces a subtree of F. 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 b-Matching problems. Let =(V,) be a hypergraph. For each vV we are given a strict preference list v over the set (v) of hyperedges containing v. In the case of Stable Hypergraph b-Matching, we are also given capacities b(v)+ for each vV.

Definition 5.

A hyperedge e is dominated by a (b-)matching M at some vertex vV if v is saturated in M and fve for each hyperedge fM(v). A hyperedge f blocks M if fM and there exists no vertex vf at which M dominates f. A (b-)matching is stable if no hyperedge blocks it.

The most important question in such instances is to find a stable matching or b-matching. Hence, we get the following computational problem.

Stable Hypergraph b-Matching or SHbM
Input: A hypergraph =(V,) with capacities b:V and strict preferences (v)vV over incident edges for each vertex in V. Output: Find a stable hypergraph b-matching in .

Stable Hypergraph Matching (or SHM) is defined analogously for matchings instead of b-matchings. It is clear that SHM is a subcase of SHbM where we have b1.

For Π{Unimod, Subpath, Subtree}, we denote by Π-SHM and Π-SHbM the restrictions of SHM and SHbM to unimodular, subpath, or subtree hypergraphs, respectively.

As was observed by Aharoni and Fleiner [1], every stable hypergraph matching for an instance (,(v)vV) of SHM  with hypergraph =(V,) can be seen as an integral point in the polyhedron {xm:Ax1,x0} that dominates every column according to the preferences (v)vV, where A 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 (,b,(v)vV) of SHbM, the integral points of the polyhedron {xm:Axb,0x1} that dominate every column correspond to the stable hypergraph b-matchings, where b (with a slight abuse of notation) is the vector containing the capacities of the vertices. If the incidence matrix A is TU, then all extreme points of this polyhedron are integral, and thus Scarf’s Lemma guarantees the existence of a stable b-matching whenever the underlying hypergraph is unimodular. The guaranteed existence of a stable matching or stable b-matching makes the class of normal hypergraphs and its subclass, unimodular hypergraphs, particularly interesting and useful.

Although the existence of a stable matching or b-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 SHbM (and SHM) can be formulated by associating a weight with each hyperedge. Given a weight function w: over a set  of hyperedges, we extend it by setting w(M)=eMw(e) for each M.

Maximum-Weight SHbor MaxW-SHbM
Input: A hypergraph =(V,) with capacities b:V, weights w:, and strict preferences (v)vV over incident edges for each vertex in V. Output: Find a maximum-weight stable hypergraph b-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-SHbM the restrictions of MaxW-SHM and MaxW-SHbM to unimodular, subpath, or subtree hypergraphs, respectively.

We remark that in the special case when the hypergraph is a bipartite graph, MaxW-SHbM  coincides with the maximum-weight stable b-matching problem (MaxW-SbM) 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 U={u1,,unU} of universities, a set Pi={pi1,,piki} of programs for each university uiU, and a set S={s1,,snS} of students. The set of programs is denoted by P=i[nU]Pi. We may refer to the set of students, universities, and programs together as the set of agents. Each university uiU has a capacity c(ui), and each program pikP has a quota q(pik).

The students apply to both a university uiU and a program pikPi available at university ui. Since each program pikP uniquely determines the university ui 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 sjS we assume a strict preference order sj over the set of programs acceptable for sj. Additionally, each university uiU has a strict preference order ui over the students, and each program pikP has a strict ordering pik over the students. A triple (sj,ui,pik) is an acceptable triple if sj finds pik 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 SUP of size 3.

An assignment μ is a function μ:SP{} mapping each student sjS either to a program that is acceptable for sj, or to the special symbol  meaning that sj is left unassigned. For simplicity, we assume that a program is acceptable for sj if and only if it is preferred by sj to . For a program pikP, we let μ(pik) denote the set of students assigned to it by μ, and similarly, for a university uiU we let μ(ui) denote the set of students assigned by μ to some program in Pi. An assignment μ is feasible if |μ(ui)|c(ui) for each uiU and |μ(pik)|q(pik) for each pikP; 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 (sj,ui,pik) such that the following three conditions hold:

  1. (i)

    piksjμ(sj);

  2. (ii)

    ui satisfies one of the followings:

    • ui is unsaturated,

    • there is a student sjμ(ui) such that sjuisj, or

    • sjμ(ui);

  3. (iii)

    the program pik is unsaturated, or there is a student sj′′μ(pik) such that sjpiksj′′.

We are ready to formally define the corresponding computational problem.

University Dual Admission or UDA
Input: An instance I=(S,U,P,c,q,(a)aSUP) of UDA as described above. Question: Find a feasible and stable assignment for I.

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 uiU with quota c(ui) whose preferences are identical to the preferences of ui.

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 SH𝒃M

In this section, we first show that UDA can be formulated as a special case of the Unimod-SHbM, 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 I of UDA, let I=(SUP,I) denote the hypergraph associated with I whose vertices are the agents in I and whose hyperedges are the acceptable triples in I. We say that a hypergraph has the UDA property if it can arise as I for some instance I of UDA.

We call UDA-SHbM and UDA-MaxW-SHbM the restriction of SHbM and MaxW-SHbM to hypergraphs having the UDA property, respectively.

To create an instance of SHbM that is equivalent with our instance I of UDA, we also need to define a strict ranking over the hyperedges of I incident to each student, university, or program. For a student sjS, his preference list sj in I can be viewed as a preference list over its incident hyperedges: sj prefers a hyperedge {sj,ui,pik} over {sj,ui,pik} if and only if piksjpik. For a program pikP, the preference order pik similarly defines a ranking over the incident hyperedges, as each such hyperedge contains the same university ui. For a university uiU, we extend its preference list to all incident hyperedges the following way. We let ui prefer {sj,ui,pik} to {sj,ui,pik} if and only if either sjuisj or sj=sj and piksjpik. Let a denote the preferences of agent aSUP in I thus defined.

Additionally, we define the capacity function b:SUP over the vertices of I as

b(a)={1, if aS,c(ui), if a=uiU,q(pik), if a=pikP.
Theorem 8 ().

Stable assignments of an instance I=(S,U,P,c,q,(a)aSUP) of UDA correspond bijectively to the stable b-matchings of the instance I=(I,b,(a)aSUP) of SHbM.

Theorem 9.

For each instance I of UDA, the associated hypergraph I is a network hypergraph.

Proof.

We create a directed graph D=(V,E) together with a spanning tree F in the undirected graph D¯=(V,E¯) obtained by replacing each arc (u,v) of D by an edge between u and v. We will show that the incidence matrix of I is exactly the network matrix that corresponds to D with the spanning tree F.

We create a vertex in V for each student, university, and program, and we further define an additional vertex x. Formally, we set V={v(a):aSUP}{x}. The set E of arcs is defined as follows. First, for each program pik at some university ui, we add an arc e(pik)=(v(pik),v(ui)). Second, for each university ui, we add an arc e(ui)=(v(ui),x). Third, for each student sj, we add an arc e(sj)=(x,v(sj)). Let EF={e(a):aSUP} denote the set of arcs defined so far. Finally, for each acceptable triple (sj,ui,pik), i.e., for each hyperedge in I, we add an arc (v(sj),v(pik)). It is straightforward to see that F:={{u,v}:(u,v)EF} is a spanning tree in D¯. Let A be the network matrix associated with D and F. Note that the edges of F are in a one-to-one correspondence with the vertices of the hypergraph I, i.e., the set of agents in I. Furthermore, the edges of EF are in a one-to-one correspondence with the hyperedges of I.

Thus, it only remains to show that A is indeed the incidence matrix of I, i.e., if a vertex vV is contained in a hyperedge e^I, then the corresponding entry in A is 1, and 0 otherwise. To see this, consider the unique cycle Ce^ defined by an arc (v(sj),v(pik)) corresponding to some hyperedge e^={sj,ui,pik}, which is the cycle formed by the four edges (v(sj),v(pil)), e(pik), e(ui), and e(sj). Observe that Ce^ contains exactly three arcs of F, namely the arcs of D corresponding to the three vertices (i.e., agents) incident to e^. Hence, there are exactly three non-zero entries in the column of A corresponding to e^, and these three entries are in the three rows that correspond to the vertices incident to e^. Moreover, since all arcs of Ce^ have the same orientation along Ce^, each of these three entries of A has value 1, 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-SH𝒃M

Let us describe an algorithm for an instance I=(,b,w,(v)vV) of UDA-MaxW-SHbM, where =(V,) over vertex set V=SUP is a hypergraph that satisfies the UDA property. Let U={u1,,unU}. We can assume that P=

i[nU]
Pi
, where the vertices pPi satisfy that for any pe, we have {ui,p}e.

The pseudocode of the algorithm is given in Algorithm 1. As a first step, we guess a strategy σ:U{}, that is, for each uiU we guess whether it will be saturated in the solution, and if so, what will be the worst hyperedge adjacent to ui. Then, we create an instance Iσ of MaxW-SbM, the maximum-weight bipartite stable b-matching problem. The underlying graph of Iσ will be the bipartite graph Gσ=(SP,Eσ) where Eσ contains an edge {s,p} if (i) there is a (unique) vertex uU such that e={s,u,p} and (ii) for that vertex u, euσ(u), where we assume that eu always holds. The preferences of the agents in Iσ are the projection of their original preferences. This is well defined, as each edge {s,p}Eσ uniquely defines a hyperedge {s,u,p}; we further set b(s)=b(s), b(p)=b(p), and w({s,p})=w({s,u,p}) so that capacities and weights remain the same.

Let us say that a b-matching M in Iσ is valid if, M:={{s,u,p}{s,p}M} satisfies that for each uU, |M(u)|=b(u) whenever σ(u), and |M(u)|<b(u) otherwise.

For a given strategy σ, the algorithm proceeds by computing a maximum-weight stable b-matching M in Iσ. If M is valid, then it adds the b-matching M:={{s,u,p}{s,p}M} corresponding to M to a set T. If M is not valid, then we discard the guessed strategy σ. Finally, we output a maximum-weight stable b-matching from T.

Algorithm 1 UDA-MaxW-SHbM(=(V,),b,w,(v)vV) where defined over SUP has the UDA property.
Theorem 11.

UDA-MaxW-SHbM can be solved in 𝒪((ΔU+1)|U|)poly(||) time, where U correspond to the class of universities and ΔU is the maximum degree of a vertex uU.

Proof.

We show that at the end of Algorithm 1, T will contain a maximum-weight stable b-matching for I.

Claim 12.

If M is a valid stable b-matching in Iσ, then the corresponding b-matching M={{s,u,p}{s,p}M} is feasible and stable in I.

Proof.

Let M be a valid stable b-matching in Iσ and let M be defined as in the statement of the claim. Then, M is a feasible b-matching in I: for vSP, |M(v)|b(v) follows from b(v)=b(v), and the capacities of the agents uU are respected due to the validity of M. It remains to show that M is stable in I.

For a hyperedge e={s,u,p}, let eI={s,p}. Suppose on the contrary that a hyperedge e={s,u,p} blocks M. First, if eIEσ, then as p (respectively, s) is either unsaturated in both M and M, or epf (esf) for some fM(p) (fM(s)) implying eIpfIM (eIsfIM); this means that the edge eI blocks M, a contradiction. Second, if {s,p}Eσ, then σ(u)ue. In particular, σ(u) and due to the validity of M we know that u is saturated in M. Moreover, by construction, any edge {s,p}M satisfies {s,u,p}uσ(u). Therefore, u is saturated in M with hyperedges that are not worse for u than σ(u). Hence e cannot block M, a contradiction.

Claim 13.

Suppose that M is a stable b-matching in I. Define σ:U{} such that σ(u) is the worst hyperedge in M(u) according to u if u is saturated in M, and otherwise. Then every stable b-matching M in Iσ is valid.

Proof.

Let M be the b-matching in Iσ defined as M={{s,p}:{s,u,p}M}. By the definition of σ, it holds that MEσ, and moreover, M is valid by construction. We claim that M is stable in Iσ.

To show that M is stable in Iσ, assume for the sake of contradiction that some edge {s,p}Eσ blocks M. Then, both s and p are either unsaturated or prefer {s,p} to some edge in M. Since M is stable, this means that the hyperedge e={s,u,p} must be dominated at u. Therefore, we get that u is saturated in M and σ(u)ue. However, then the edge {s,p} cannot be contained in Eσ, a contradiction.

Due to the many-to-many extension of the well-known Rural Hospitals Theorem (see e.g., [11]), for any stable b-matching M′′ in Iσ, we have |M′′(v)|=|M(v)| for all vSP. Hence, all stable b-matchings of Iσ must be valid, because for any stable b-matching N and its corresponding b-matching N in I, we have |N(ui)|=pPi|N(p)| for uiU by the UDA property. This concludes the proof.

As we know that a stable b-matching for I 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 b-matching M. By Sections 3.2 and 3.2, M={{s,p}{s,u,p}M} will be a valid stable b-matching for Iσ, and since any valid b-matching N gives a stable b-matching N in I with w(N)=w(N), the algorithm indeed puts M or a stable b-matching with the same weight in T.

Since there are at most (ΔU+1)|U| possible strategies to check, and for each one them, the instance Iσ and a maximum-weight stable b-matching in Iσ can be computed in poly(||) 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 c(u)=1 for all universities, then a simple deferred acceptance algorithm between the students and universities produces a stable assignment; see the full version [4].

4 SH𝒃M for Unimodular Hypergraphs

We proceed to study Unimod-SHbM in further classes of unimodular hypergraphs.

4.1 Laminar Hypergraphs

We construct a polynomial-time algorithm that finds a stable b-matching if the hypergraph =(V,) is laminar. As laminar hypergraphs are unimodular, the existence of a stable b-matching is guaranteed. We present our algorithm for this problem in Algorithm 2.

Algorithm 2 Laminar-SHbM(,b,(v)vV) where =(V,) is laminar.
Theorem 15.

Laminar-SHbM is solved in polynomial time by Algorithm 2.

Proof.

First, let us show that the set returned by Algorithm 2 is a b-matching. Observe that whenever some hyperedge f is added to M on line 7, the set Xf constructed on line 9 covers every vertex v that became oversaturated as a consequence of adding f. Therefore, Yf also covers these vertices, so after the removal of all hyperedges of Yf from the matching, the resulting set again satisfies all capacity constraints. Therefore, the algorithm indeed returns a b-matching M.

It remains to show that M is stable. Consider the iteration of lines 410 during Algorithm 2 where some hyperedge f is picked on line 4, and let Mf and Mf denote the current b-matching at the beginning and at the end of this iteration, respectively. We need the following claim.

Claim 16.

For any edge f added to the b-matching at line 7, the set Yf is a family of pairwise disjoint hyperedges whose union is a subset of f, with fYf.

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 f is either a subset of f or is disjoint from it. In particular, since the algorithm only puts hyperedges of the current b-matching into Xf, we get that all hyperedges in Xf are contained in f (recall that f shares at least one oversaturated vertex with each hyperedge in Xf). Since Yf contains only the inclusion-wise maximal sets from Xf, the laminarity of Xf implies that the hyperedges in Yf are pairwise disjoint.

To see fYf, it suffices to observe the following. Since f blocks the current b-matching Mf, for each vV that is oversaturated in Mf{f} we know that f cannot be the worst hyperedge incident to v in Mf(v){f}.

Consider now the iteration during which f is picked on line 4. If the algorithm adds f to the current b-matching Mf on line 4, then Mf=Mf{f}Yf, otherwise Mf=Mf. Hence, the above claim implies |Mf(v)||Mf(v)| for each vV, since v can only be incident to at most one hyperedge in Yf. Moreover, if |Mf(v)|=b(v) for some vV, then the worst hyperedge in Mf(v) is weakly preferred by v to the worst hyperedge in Mf(v): this is obvious if vf, and if vf, then v prefers f to at least one hyperedge in Mf(v), so v’s worst hyperedge cannot be worse than before, as f is the only new hyperedge in Mf(v) not in Mf(v) already. Hence, whenever some vertex becomes saturated with hyperedges better than some e, 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 M, consider an arbitrary edge fM and the iteration during which f is examined at line 4. If f is not added to Mf on line 7, then some vertex v incident to f must be saturated in Mf with hyperedges that are all preferred to f by v. By the saturation-monotonicity of the algorithm, this remains true for the returned b-matching M, so f cannot block M. By contrast, if f is added to Mf on line 7, then f must have been removed at some point on line 10 during a later iteration as a consequence of adding some hyperedge e to the b-matching Me on line 7 for which fYe. By our construction of Ye, we know that f is the worst hyperedge for some vertex uV in Me(u), so after removing Ye from the b-matching Me{e}, vertex u is saturated with hyperedges that are all preferred by u to f. Again, by the saturation-monotonicity of the algorithm, this remains true for u during the algorithm, so f cannot block M. Thus, M is indeed a stable b-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 0 with the exception of a single edge of weight 1.

4.2 Subpath Hypergraphs

Moving our focus to instances of SHbM where the underlying hypergraph  is a subpath hypergraph, we present an algorithm for the MaxW-Subpath-SHbM problem that runs in polynomial time if the maximum size of a hyperedge in  is bounded by a constant.

Theorem 18.

MaxW-Subpath-SHbM can be solved in O((Δ(bmax+1))max||logω) time for an instance (=(V,),b,w,(v)vV), where bmax is the maximum capacity of a vertex, max is the maximum size of an edge in , Δ is the maximum degree of a vertex, and ω is the maximum absolute value of w(e) over e.

A brute-force approach to solve the MaxW-Subpath-SHbM problem would be to consider the edges one-by-one and enumerate all possible b-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 max 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 b-matchings that, in a certain sense, represents all possible strategies for obtaining a stable b-matching. We start by introducing the necessary concepts.

Strategies.

A strategy over a given set WV of vertices is a function σ:W{} such that σ(w) is incident to w for each wW unless σ(w)=. The interpretation of a strategy is that σ(w) is the planned threshold of w, that is, the worst edge that we plan to put into the b-matching among those incident to w; the symbol corresponds to being unsaturated. We extend the notation w such that ew holds for each e incident to w.

Definition 19.

A b-matching M realizes a strategy σ over W w.r.t. some if

  1. (i)

    M is compatible with σ, meaning that for each wW:

    • if σ(w), then ewσ(w) holds for every eM(w), and

    • if σ(w)=, then |M(w)|<c(w);

  2. (ii)

    σ(w)M(w) for each wW with σ(w), and

  3. (iii)

    every edge in M that blocks M is planned to be dominated by σ where we say that σ plans to dominate an edge e if there exists some wW such that σ(w)we.

We call a strategy realizable for an edge set  if some b-matching realizes it w.r.t. .

Observe that if a strategy σ plans to dominate an edge e at some vertex w and M is a b-matching compatible with σ that also satisfies |M(w)|=b(w), then e cannot block M, because e is dominated by M at w, meaning that M contains b(w) edges incident to w, and w prefers each of them to e.

Given a strategy σ over W and a b-matching compatible with σ, we say that M is complete on a vertex set WW for σ if |M(v)|=b(v) for each vW such that σ(v).

The algorithm.

Let (,b,w,(v)vV) be our instance of MaxW-Subpath-SHbM with a subpath  hypergraph =(V,), and let v1,,vn be the ordering of V witnessing the subpath property of . That is, for each hyperedge e there exist indices ij such that e={vi,vi+1,,vj}.

For a hyperedge e, we write l(e)=max{i:vie} and we say that vl(e) is the endpoint of e. Let e1,,em be an ordering of where l(ei)<l(ej) implies i<j, that is, we order the edges increasingly according to their endpoints. Let i={e1,,ei}, and let Li contain the last max vertices contained in i, that is, Li={vj:max{0,l(ei)max}<jl(ei)}.

Our algorithm considers each set i={e1,,ei}, and computes a set Si of pairs (σ,M) where σ is a strategy over Li and M is a b-matching in (V,i) that realizes σ. We will ensure that Si is representative for i in the following sense:

Definition 20.

Set Si is w-representative for i if the following holds: whenever there is a strategy σ and a b-matching M realizing σ with respect to i, then there is a b-matching M equivalent to M on Li for which (σ,M)Si and w(M)w(M). Here, M is equivalent to M on Li, if |M(v)|=|M(v)| for each vLi; this is denoted by MLiM.
The operation of updating Si with (σ,M) means that we put (σ,M) into Si unless there is some pair (σ,M^) already in Si for which M^ is equivalent on Li to M and w(M^)w(M).

We initialize S0 to contain only (σ,) where σ is the function with empty domain. For i=1 to m, we build the set Si as follows; Algorithm 3 contains a formal description.

Adjusting the domain from Li1 to Li:

For each (σ,M)Si1, check whether M is complete for σ on Li1Li. If not, then we will not be able to make σ complete by adding edges from i1, so we ignore the pair (σ,M). Otherwise, we change the domain of σ from Li1 to Li (forgetting all values assigned to vertices of Li1Li) as follows: We set σ(v) for each vLiLi1 to all possible values in {e:ve}{}, and for each strategy σ over Li obtained this way, we put (σ,M) into a set Ti.

Computing Si based on ei:

For each (σ,M)Ti we check whether M still realizes σ with respect to i by checking if (i) σ plans to dominate ei, and (ii) for each vei, the threshold σ(v) does not coincide with ei. If these conditions hold, then M realizes σ with respect to i. Hence, we update Si with (σ,M). Next, we check whether we can add ei to M: if adding ei does not violate the capacities and yields a b-matching compatible with σ, then we update Si with (σ,M{ei}).

The algorithm finishes by checking whether Sm contains a pair (σ,M) where M is complete for σ on Lm, and if so, outputs among all such b-matchings M one that maximizes w(M).

Algorithm 3 MaxW-Subpath-SHbM(=(V,),b,w,(v)vV) where is a subpath hypergraph.
Lemma 21 ().

If Algorithm 3 puts a pair (σ,M) into Si for some i[m], then M realizes σ with respect to i.

Proof sketch..

We use induction on i. The case i=0 is trivial, so assume that the lemma holds for i1.

First, suppose that (σ,M) was added to Si on line 14, so Mi1. Let (σ,M)Si1 be selected on line 4 in the cycle during which (σ,M) was put into Ti on line 10. By induction,

  1. (a)

    M is compatible with σ,

  2. (b)

    σ(v)M(v) for every vLi1 where σ(v)i1, and

  3. (c)

    every edge in i1M that blocks M is planned to be dominated by σ.

First, observe that M is compatible with σ: the compatibility conditions for each vLi1Li follow immediately from σ(v)=σ(v) due to (a), while the compatibility condition for each vLiLi1 holds irrespective of the value of σ(v), because edges of Mi1 have no vertices in LiLi1.

Second, by our assumption that Algorithm 3 added (σ,M) to Si on line 14, we know that σ(v)ei for each v incident to ei. Hence, if σ(v)i for some vLi, then σ(v)i1, and consequently, vLiLi1 (because vertices of LiLi1 are not contained in any edge of i1). Therefore, (b) implies σ(v)=σ(v)M(v). Third, it remains to show that every edge eiM that blocks M is planned to be dominated by σ. First note that Algorithm 3 checks that this holds for ei explicitly on line 13, so we may assume eei. By (c), we know that every edge in i1M that blocks M is planned to be dominated by σ, so there is some vLi1 such that σ(v)ve. On the one hand, if vLiLi1, then e is planned to be dominated by σ too, because σ(v)=σ(v). On the other hand, if vLi1Li, then Algorithm 3 must have confirmed on line 10 that M is complete on v (otherwise it would not have put (σ,M) into Ti), which implies that M dominates e at v. Thus, e does not block M, proving that every edge in iM that blocks M is planned to be dominated by σ. This finishes the proof that M realizes σ with respect to i.

The case when (σ,M) was put into Si on line 17 is similar; see the full version [4].

Lemma 22 ().

Set Si computed by Algorithm 3 is w-representative for i for each i[m].

Proof sketch..

We prove the lemma by induction on i. Clearly, the lemma trivially holds for i=0, so let us assume that the statement holds for i1.

To prove that Si remains w-representative for i, it suffices to show the following: if (σ,M) is such that Mi realizes σ with respect to i, then the algorithm updates Si with some pair (σ,M) either at line 14 or at line 17 for which MLiM (note that Li is transitive) and w(M)w(M).

Given σ and M, let us define the strategy σ over Li1 as follows:

σ(v)={σ(v),if vLi1Li;,if vLi1Li and |M(v)|<b(v);worst(M,v),if vLi1Li and |M(v)|=b(v)

where worst(M,v) is the worst edge in M(v) according to v. Note that M is complete on vertices of Li1Li for σ. We distinguish between two cases.

Case A:

eiM. It is then straightforward to check that M realizes σ w.r.t. i1; see [4] for a detailed proof. Therefore, by induction there exists a b-matching M with w(M)w(M) such that (σ,M)Si1 and MLi1M.

Recall that M is complete on Li1Li for σ, and thus MLi1M implies that M is also complete on Li1Li for σ. Hence, (σ,M) passes the test on line 5. As Algorithm 3 tries all possible ways to extend σ, it follows that (σ,M)Ti. Now, since M realizes σ w.r.t. i but eiM, we get that eiσ(v) for any vei. Additionally, σ plans to dominate ei: if ei blocks M, then this is because M realizes σ w.r.t. i (by our assumptions), and if ei does not block M, then it is dominated at some vertex vLi, which in turn implies that v is saturated by M and worst(M,v)=σ(v)vei, that is, σ indeed plans to dominate ei. Therefore, Algorithm 3 updates Si with (σ,M) at line 14.

Case B:

eiM. Consider the b-matching M=M{ei}. It is then straightforward to check that M realizes σ w.r.t. i1; see again [4]. Therefore, by induction there exists a b-matching M with w(M)w(M) such that (σ,M)Si1 and MLi1M.

Recall that M is complete on Li1Li for σ, and thus MLi1M implies that M is also complete on Li1Li for σ. Therefore, (σ,M) passes the test on line 5. As Algorithm 3 tries all possible ways to extend σ, it follows that (σ,M)Ti. Since eiM and M is compatible with σ, we know that eivσ(v) for each vLi. By MLi1M and since M{ei}=M is a b-matching, we know |M(v)|<b(v) for each veiLi1; since Mi1, it is also clear that |M(v)|=0<b(v) for each vLiLi1. Therefore, the pair (σ,M) satisfies the conditions on line 15 and so Algorithm 3 updates Si with (σ,M{ei}) at line 17. By M{ei}LiM{ei}=M and w(M{ei})w(M)+w(ei)=w(M), this finishes the proof of the lemma.

Proof of Theorem 18.

Let us first prove that Algorithm 3 solves MaxW-Subpath-SHbM correctly on subpath hypergraphs.

First, we show that the output is stable. Observe that if Algorithm 3 returns a b-matching M on line 22, then M realizes σ on , and thus σ plans to dominate every edge blocking M. However, as M is complete for σ (due to the condition on line 20), M in fact dominates every edge that σ plans to dominate. Thus, no edge may block M.

Assume now that M is a maximum-weight stable b-matching in our instance. Let σ be the strategy over Lm defined as

σ(v)={,if |M(v)|<b(v);worst(M,v),if |M(v)|=b(v).

It is clear that M realizes σ over . Thus, by Section 4.2 there exists a b-matching M satisfying w(M)w(M) for which (σ,M)Sm and MLmM. Moreover, as M is complete on Lm for σ and MLmM, we know that M is complete on Lm for σ as well. Hence, Algorithm 3 will set w to at least w(M)w(M) on line 21 at latest when it examines the pair (σ,M), and will thus return a stable b-matching of weight at least w(M) on line 22, which must be a maximum-weight stable b-matching.

To bound the running time of Algorithm 3, note that the number of possible strategies for a given set Li is at most Δ|Li|Δmax where Δ is the maximum number of edges incident to any vertex. Given a strategy σ over Li, we also know |{M:(σ,M)Si}|(bmax+1)|Li|(bmax+1)max since this set does not contain two b-matchings that are equivalent on Li. This yields

|Si|(Δ(bmax+1))max.

There are m iterations, and the computation of Si from Si1 is proportional to |Si1|+|Si|, as any line of the algorithm can be performed in O(maxlogω) time. Thus, we obtain that the total running time is O((Δ(bmax+1))maxmlogω), as promised.

 Remark 23.

We remark that Algorithm 3 can be used to decide whether a stable b-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 b-matching that saturates (or does not saturate) a given vertex v. Indeed, to decide whether some stable b-matching saturates v, it suffices to add a newly created hyperedge ev incident only to v, extend the preferences of v such that ev becomes the least-favorite edge according to v, and decide whether this modified instance admits a stable b-matching that does not contain ev. Deciding whether some stable b-matching leaves v unsaturated can be done analogously, using the same construction but searching for a stable b-matching that contains ev.

Theorem 24 shows that the running time of the algorithm in Theorem 18 cannot be improved to an FPT algorithm with parameter max, not even if we additionally parameterize the problem with the maximum capacity and severely restrict the weight function.

Theorem 24 ().

The MaxW-Subpath-SHbM problem is 𝖶[1]-hard when parameterized by bmax+max, where bmax is the maximum capacity of a vertex and max is the maximum size of an edge, even if all edges have weight 0 with the exception of a single edge of weight 1.

5 SH𝒃M 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-SHbM may not admit a stable b-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 =(V,) be a subtree hypergraph and let T=(V,F) be the underlying tree, that is, for each hyperedge e, the set of vertices contained in e induces a subtree of T. Let r be a fixed vertex of V and consider the rooted tree T with root r. For each vertex v, let distT(r,v) be the distance of r and v in T, that is the number of edges of the (unique) path of T between r and v. For each hyperedge e, let topT,r(e) be the (unique) vertex of e that is closest to r in T, and define distT,r(e):=distT(r,topT,r(e)).

Given an instance (,(v)vV) of Subtree-SHM, where =(V,) is a subtree hypergraph with underlying tree T, algorithm Subtree-SHM does the following (see Algorithm 4 for a pseudocode). First, it finds a hyperedge f such that topT,r(f) is furthest from r in T; for simplicity, let us write rf for topT,r(f). Then it deletes f and every hyperedge incident to rf that are less preferred by rf than f, and recursively calls itself on the remaining hypergraph. Finally, it builds a matching by adding f to the output M of the recursive call if rf is not covered by M.

Algorithm 4 Subtree-SHM(,(v)vV) where =(V,) is a subtree hypergraph with underlying tree T rooted at rV.
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 f and delete those hyperedges incident to rf=topT,r(f) that are worse than f for rf.

We show that the output M is a stable hypergraph matching. We use induction on ||. If =, then the output M= of Algorithm 4 is clearly a stable hypergraph matching.

Hence, assume that . Let f be the hyperedge chosen by the algorithm in the first iteration. By induction, M is a stable hypergraph matching in the subtree hypergraph (V,(Xf{f})).

First, suppose that M saturates rf, so Algorithm 4 outputs M. Then, M is clearly a matching. Also, no hyperedge of (Xf{f}) blocks M by induction. Finally, no hyperedge of Xf{f} blocks M either, because rf is covered with some hyperedge eM such that erffrff for every fXf by the choice of Xf.

Suppose now that M does not saturate rf, and the output is therefore M{f}. The fact that is a subtree hypergraph and that f is chosen so that it maximizes distT,r(f) implies that any hyperedge that intersects f must also contain rf. Hence, as M does not cover rf, M{f} is a matching. By induction, no hyperedge of (Xf{f}) blocks M, and thus M{f}. Finally, no hyperedge of Xf blocks M{f}, because frff for every fXf and rf is saturated by M{f}.

We conclude that the output is a stable matching.

A natural question to ask whether a stable b-matching can still be found efficiently in the SHbM setting. Sadly, the answer is no, even with very severe restrictions.

Theorem 26 ().

Deciding if there exists an stable hypergraph b-matching in an instance of Subtree-SHbM 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 3 [8], it is straightforward to verify that the problem of finding a stable fractional hypergraph matching in an instance of Subtree-SHbM satisfying the conditions of Theorem 26 is 𝖯𝖯𝖠𝖣-complete too.

6 Conclusions

We studied stable hypergraph matchings and b-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-SHbM. We identified multiple classes of hypergraphs where stable (b-)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 SHbM 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 b-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.