Bérczi K., Király T., Kobayashi Y., et al. Finding spanning trees with perfect matchings. Discrete Applied Mathematics 371, 137 (2025); https://doi.org/10.1016/j.dam.2025.04.001.

Consider a directed, rooted graph \(G=(V\cup\{r\},E)\) where each vertex in \(V\) has a partial order preference over its incoming edges. The preferences of a vertex naturally extend to preferences over arborescences rooted at \(r\) . We present a polynomial-time algorithm that decides whether a given input instance admits a popular arborescence, i.e., one for which there is no “more popular” arborescence. In fact, our algorithm solves the more general popular common base problem in the intersection of two matroids: we are given an arbitrary matroid \(M=(E,\mathcal{I})\) and a partition matroid \(M_{\text{part}}\) over \(E\) , where partition classes correspond to a set \(V\) of agents with \(|V|={\rm rank}(M)\) and each agent has a partial order preference over its associated partition class; the problem asks for a common base of \(M\) and \(M_{\text{part}}\) such that there is no “more popular” common base. Our algorithm is combinatorial, and can be regarded as a primal–dual algorithm. It searches for a solution along with its dual certificate, a chain of subsets of \(E\) , witnessing its popularity. Our generalized results, expressed in terms of matroids, demonstrate that the identification of agents with vertices of the graph in the popular arborescence problem is not essential. We also study the related popular common independent set problem. For the case with weak rankings, we formulate the popular common independent set polytope, and thus show that a minimum-cost popular common independent set can be computed efficiently. By contrast, we prove that it is \(\mathsf{NP}\) -hard to compute a minimum-cost popular arborescence, even when rankings are strict.

Our input is a directed, rooted graph G = (V ∪ {r}, E) where each vertex in V has a partial order preference over its incoming edges. The preferences of a vertex extend naturally to preferences over arborescences rooted at r. We seek a popular arborescence in G, i.e., one for which there is no “more popular” arborescence. Popular arborescences have applications in liquid democracy or collective decision making; however, they need not exist in every input instance. The popular arborescence problem is to decide if a given input instance admits a popular arborescence or not. We show a polynomial-time algorithm for this problem, whose computational complexity was not known previously.

Abstract. We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama [ Theoret. Comput. Sci., 809 (2020), pp. 265–276] and solved in the special case where matroids are base orderable. Utilizing a newly shown matroid exchange property, we show that the problem is tractable for arbitrary matroids. We further investigate a different notion of popularity, where the agents vote with respect to lexicographic preferences, and show that both existence and verification problems become coNP-hard even in the [Formula: see text]-matching case.

We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions under which there always exists a random assignment that simultaneously satisfies efficiency and envy-freeness. The probabilistic serial mechanism ensures the existence of such an assignment for the unconstrained setting. In this paper, we consider a more general setting in which each agent can consume a set of items only if the set satisfies her feasibility constraint. Such constraints must be taken into account in student course placements, employee shift assignments, and so on. We demonstrate that an efficient and envy-free assignment may not exist even for the simple case of partition matroid constraints, where the items are categorized, and each agent demands one item from each category. We then identify special cases in which an efficient and envy-free assignment always exists. For these cases, the probabilistic serial cannot be naturally extended; therefore, we provide mechanisms to find the desired assignment using various approaches.

Abstract. Let [Formula: see text] be a multigraph with a set [Formula: see text] of terminals. A path in [Formula: see text] is called a [Formula: see text]-path if its ends are distinct vertices in [Formula: see text] and no internal vertices belong to [Formula: see text]. In 1978, Mader showed a characterization of the maximum number of edge-disjoint [Formula: see text]-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint [Formula: see text]-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint [Formula: see text]-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds [ Canad. J. Math., 17, 1965, pp. 449–467]. When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint [Formula: see text]-paths. From this certificate, one can obtain the Edmonds–Gallai type decomposition introduced by Sebő and Szegő [ Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, LNCS 3064, Springer, Berlin, 2004, pp. 256–270]. The algorithm runs in [Formula: see text] time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of [Formula: see text]-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.

Abstract. Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds’ fundamental theorem provides a min-max characterization for the unweighted setting, while Frank’s weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one of the conventional oracles for both matroids. In the present paper, we consider the tractability of the matroid intersection problem under restricted oracles. In particular, we focus on the rank sum, common independence, and maximum rank oracles. We give a strongly polynomial-time algorithm for weighted matroid intersection under the rank sum oracle. In the common independence oracle model, we prove that the unweighted matroid intersection problem is tractable when one of the matroids is a partition matroid and that even the weighted case is solvable when one of the matroids is an elementary split matroid. Finally, we show that the common independence and maximum rank oracles together are strong enough to realize the steps of our algorithm under the rank sum oracle.

Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lower quotas and the objective is to satisfy them as much as possible. When preference lists are strict, the number of residents assigned to each hospital is the same in any stable matching because of the well-known rural hospitals theorem; thus there is no room for algorithmic interventions. However, when ties are introduced to preference lists, this will no longer apply because the number of residents may vary over stable matchings. In this paper, we formulate an optimization problem to find a stable matching with the maximum total satisfaction ratio for lower quotas. We first investigate how the total satisfaction ratio varies over choices of stable matchings in four natural scenarios and provide the exact values of these maximum gaps. Subsequently, we propose a strategy-proof approximation algorithm for our problem; in one scenario it solves the problem optimally, and in the other three scenarios, which are NP-hard, it yields a better approximation factor than that of a naive tie-breaking method. Finally, we show inapproximability results for the above-mentioned three NP-hard scenarios.

We present a polynomial-time $\frac{3}{2}$-approximation algorithm for the problem of finding a maximum-cardinality stable matching in a many-to-many matching model with ties and laminar constraints on both sides. We formulate our problem using a bipartite multigraph whose vertices are called workers and firms, and edges are called contracts. Our algorithm is described as the computation of a stable matching in an auxiliary instance, in which each contract is replaced with three of its copies and all agents have strict preferences on the copied contracts. The construction of this auxiliary instance is symmetric for the two sides, which facilitates a simple symmetric analysis. We use the notion of matroid-kernel for computation in the auxiliary instance and exploit the base-orderability of laminar matroids to show the approximation ratio. In a special case in which each worker is assigned at most one contract and each firm has a strict preference, our algorithm defines a $\frac{3}{2}$-approximation mechanism that is strategy-proof for workers.

Let G = (V, E) be a multigraph with a set T ⊆ V of terminals. A path in G is called a T-path if its ends are distinct vertices in T and no internal vertices belong to T. In 1978, Mader showed a characterization of the maximum number of edge-disjoint T-paths. The original proof was not constructive, and hence it did not suggest an efficient algorithm. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint T-paths. The algorithm adopts an augmenting path approach. More specifically, we introduce a novel concept of augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint T-paths. To design a search procedure for an augmenting walk, we introduce blossoms analogously to the blossom algorithm of Edmonds (1965) for the matching problem, while it is neither a special case nor a generalization of the present problem. When the search procedure terminates without finding an augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint T-paths. Thus the correctness argument of the algorithm serves as an alternative direct proof of Mader's theorem on edge-disjoint T-paths. The algorithm runs in O(|V| • |E|2) time, which is much faster than the best known deterministic algorithm based on a reduction to the linear matroid parity problem.

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor–hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235–1253, 2010 ), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.

In some game-theoretic models, an agent is supposed to choose a subset of available items under a matroid constraint. If an agent always chooses a subset according to the standard greedy algorithm for matroids, then this choice rule fulfills the “substitutability," an essential property for the existence of equilibria in matching market models. In this paper, we introduce a notion of “matroidal choice functions" to capture the entire class of substitutable choice rules under a matroid constraint. For such functions, we provide two characterizations: one is by the behavior of an online greedy algorithm, and the other is by a local condition. We also show that matroidal choice functions extend choice rules defined by the maximization algorithm for valuated matroids and discrete concave functions.

We study a decentralized matching market in which each firm sequentially makes offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision is irrevocable. The acceptance of an offer guarantees her job at the firm, but it may also eliminate chances of better offers from other firms in the future. We formulate this market as a perfect-information extensive-form game played by the workers. Each instance of this game has a unique subgame perfect equilibrium (SPE), which does not necessarily lead to a stable matching and has some perplexing properties. Our aim is to establish the complexity of computing the SPE, or more precisely, deciding whether each offer is accepted in the SPE. We show that the tractability of this problem drastically changes according to the number of potential offers related to each firm and worker. If each firm makes offers to at most two workers (or each worker receives offers from at most two firms), then the problem is efficiently solved by a variant of the deferred acceptance algorithm. In contrast, the problem is PSPACE-hard even if both firms and workers are related to at most three offers.

The stable matching model of Gale and Shapley (1962) has been generalized in various directions such as matroid kernels due to Fleiner (2001) and stable allocations in bipartite networks due to Baïou and Balinski (2002). Unifying these generalizations, we introduce the concept of stable allocations in polymatroid intersection. Our framework includes both integer- and real-variable versions. The integer-variable version corresponds to a special case of the discrete-concave function model due to Eguchi, Fujishige, and Tamura (2003), who established the existence of a stable allocation by showing that a simple extension of the deferred acceptance algorithm of Gale and Shapley finds a stable allocation in pseudo-polynomial time. It has been open to develop a polynomial-time algorithm even for our special case. In this paper, we present the first strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is O(n3γ), where n and γ respectively denote the cardinality of the ground set and the time for computing the saturation and exchange capacities. This is as fast as the best known algorithm for the polymatroid intersection problem.