Our input is a marriage instance G = (A ∪ B, E), i.e., it is a bipartite graph where every vertex has strict preferences over its neighbors. The preferences that a vertex has on its neighbors extend naturally to preferences over matchings. A maximum matching M that does not lose an election against any maximum matching (where vertices cast votes) is a popular maximum-matching. These matchings are useful in practice - they always exist and can be efficiently computed [Kavitha, SICOMP 2014]. Suppose preferences change; then the problem is to update the current matching M_0 via a short voting path to a popular maximum-matching, where a length-𝓁 voting path from M_0 to M_𝓁 is a sequence of maximum matchings ⟨M_0,M_1,…,M_𝓁⟩ such that each matching is more popular than its predecessor. There are maximum matchings from which there is no voting path (of any length) to a popular maximum-matching [Bhattacharya et al., ICALP 2015]. We show a polynomial-time algorithm to decide if there exists a short voting path, i.e. one of length ≤ 2, from a given maximum matching to a popular maximum-matching and find one, if so. Voting paths motivate natural relaxations of popularity: pseudo-popular maximum-matchings and mostly-popular maximum-matchings; these yield more egalitarian or optimal solutions than popular maximum-matchings. We show polynomial-time algorithms to compute such optimal solutions that go beyond popularity. In particular, we give a combinatorial characterization of pseudo-popular maximum-matchings in terms of forced vertices and forbidden edges. We also show a polynomial-time algorithm to compute at most |E| = m popular maximum-matchings such that any maximum matching that loses to some popular maximum-matching loses to at least one of these m matchings.

Let G be a bipartite graph where every vertex has a strict preference order over its neighbors. The preferences of a vertex over its neighbors extend naturally to preferences over matchings. A matching N is more popular than matching M if the vertices that prefer N to M outnumber those that prefer M to N. A matching M is popular if there is no matching more popular than M. Every stable matching is popular, thus popular matchings always exist in G and can be efficiently computed. We consider the following problem: edges in G have utilities and it is only max-utility matchings that are relevant. Our goal is to find a popular max-utility matching, i.e., a max-utility matching M such that there is no max-utility matching more popular than M. We show there always exists a popular max-utility matching; furthermore, such a matching can be efficiently computed. The popular critical matching algorithm is the key subroutine in our algorithm. Given a set of prioritized or critical vertices in G, we are interested in only those matchings that match as many critical vertices as possible. We call such matchings “critical” and seek a popular critical matching, i.e., a critical matching M such that there is no critical matching more popular than M. We show popular critical matchings always exist in G and a min-size/max-size such matching can be efficiently computed. We focus on max-size critical matchings and show a compact extended formulation for the popular max-critical matching polytope, i.e., the polytope of max-size critical matchings that are popular within the set of all max-size critical matchings. Thus we can efficiently solve linear optimization problems over the set of popular max-size critical matchings.

Our input is an undirected weighted graph G = (V,E) on n vertices along with a source set S ⊆ V. The problem is to preprocess G and build a compact data structure such that upon query Qu(s,v,f) where (s,v) ∈ S×V and f is any faulty edge, we can quickly find a good estimate (i.e., within a small multiplicative stretch) of the s-v distance in G-f. We use a fault-tolerant ST-distance oracle from the work of Bilò et al. (STACS 2018) to construct an S×V approximate distance oracle or sourcewise approximate distance oracle of size Õ(|S|n + n^{3/2}) with multiplicative stretch at most 5. We construct another fault-tolerant sourcewise approximate distance oracle of size Õ(|S|n + n^{4/3}) with multiplicative stretch at most 13. Both the oracles have O(1) query answering time.

Abstract We consider the popular matching problem in a roommates instance G on n vertices, i.e., G is a graph where each vertex has a strict preference order over its neighbors. A matching M is popular if there is no matching N such that the vertices that prefer N to M outnumber those that prefer M to N. It is known that it is NP-hard to decide if G admits a popular matching or not. There is no better algorithm known for this problem than the brute force algorithm that enumerates all matchings and tests each for popularity—this could take n! time. Here we show an $$O^*(k^n)$$ O ∗ ( k n ) time algorithm for this problem, where $$k < 7.32$$ k < 7.32 . We use the recent breakthrough result on the maximum number of stable matchings possible in a roommates instance to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called truly popular matchings that are “popular fractional” and show an $$O^*(2^n)$$ O ∗ ( 2 n ) time algorithm for the truly popular matching problem in G. We also identify a subclass of max-size popular matchings called super-dominant matchings and show a linear time algorithm for the super-dominant roommates problem.

Abstract. We consider a matching problem in a bipartite graph [Formula: see text] where vertices have strict preferences over their neighbors. A matching [Formula: see text] is popular if for any matching [Formula: see text], the number of vertices that prefer [Formula: see text] to [Formula: see text] is at least the number that prefer [Formula: see text] to [Formula: see text]; thus [Formula: see text] does not lose a head-to-head election against any matching where vertices are voters. It is easy to find popular matchings; however, when there are edge costs, it is NP-hard to find (or approximate) a min-cost popular matching. This hardness motivates relaxations of popularity. Here we introduce fairly popular matchings. A fairly popular matching may lose elections but there is no good matching (w.r.t. popularity) that defeats a fairly popular matching. In particular, any matching that defeats a fairly popular matching does not occur in the support of a popular mixed matching. We show that a min-cost fairly popular matching can be computed in polynomial time and the fairly popular matching polytope has a compact extended formulation. We also show it is NP-complete to decide if there exists a popular matching that is more popular than a given matching. Interestingly, there exists a set of at most [Formula: see text] popular matchings in [Formula: see text] (where [Formula: see text]) such that if a matching is defeated by some popular matching in [Formula: see text], then it has to be defeated by one of the matchings in this set.

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 a matching problem in a bipartite graph $$G = (A \cup B, E)$$ G = ( A ∪ B , E ) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their rankings. Stable matchings always exist in G and are easy to find, however popular matchings need not exist in G and it is NP-complete to decide if one exists. This motivates the “approximately popular” matching problem. A well-known measure of approximate popularity is low unpopularity factor . We show that when each tie in G has length at most k , there always exists a stable matching whose unpopularity factor is at most k and such a matching can be computed in polynomial time. Thus when ties have bounded length, there always exists a near-popular stable matching. This can be considered to be a generalization of Gärdenfors’ result (1975) which showed that when rankings are strict, every stable matching is popular. We then extend our result to the hospitals/residents setting, i.e., vertices in B have capacities. There are several applications where the size of the matching is its most important attribute. When ties are one-sided and of length at most k , we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2 k .

Abstract. Let [Formula: see text] be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching [Formula: see text] in [Formula: see text] is a popular max-matching if there is no maximum matching more popular than [Formula: see text]. In other words, for any maximum matching [Formula: see text], the number of nodes that prefer [Formula: see text] to [Formula: see text] is at least the number of nodes that prefer [Formula: see text] to [Formula: see text]. It is known that popular max-matchings always exist in [Formula: see text] and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function [Formula: see text], and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching.

Let G = (A ∪ B, E) be a bipartite graph where the set A consists of agents or main players and the set B consists of jobs or secondary players. Every vertex in A ∪ B has a strict ranking of its neighbors. A matching M is popular if for any matching N , the number of vertices that prefer M to N is at least the number that prefer N to M . Popular matchings always exist in G since every stable matching is popular. A matching M is A -popular if for any matching N , the number of agents (i.e., vertices in A ) that prefer M to N is at least the number of agents that prefer N to M . Unlike popular matchings, A -popular matchings need not exist in a given instance G and there is a simple linear time algorithm to decide if G admits an A -popular matching and compute one, if so. We consider the problem of deciding if G admits a matching that is both popular and A -popular and finding one, if so. We call such matchings fully popular . A fully popular matching is useful when A is the more important side—so along with overall popularity, we would like to maintain “popularity within the set A ”. A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial-time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.

In fair division problems, we are given a set S of m items and a set N of n agents with individual preferences, and the goal is to find an allocation of items among agents so that each agent finds the allocation fair. There are several established fairness concepts and envy-freeness is one of the most extensively studied ones. However envy-free allocations do not always exist when items are indivisible and this has motivated relaxations of envy-freeness: envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are two well-studied relaxations. We consider the problem of finding EF1 and EFX allocations for utility functions that are not necessarily monotone, and propose four possible extensions of different strength to this setting. In particular, we present a polynomial time algorithm for finding an EF1 allocation for two agents with arbitrary utility functions. An example is given showing that EFX allocations need not exist for two agents with non-monotone, non-additive, identical utility functions. However, when all agents have monotone (not necessarily additive) identical utility functions, we give a pseudo-polynomial time algorithm that always finds an EFX allocation of chores. As a step toward understanding the general case, we discuss two subclasses of utility functions: Boolean utilities that are {0,+1}-valued functions, and negative Boolean utilities that are {0,−1}-valued functions. For the latter, we give a polynomial time algorithm that finds an EFX allocation when the utility functions are identical.

We consider the many-to-many bipartite matching problem in the presence of two-sided preferences and two-sided lower quotas. The input to our problem is a bipartite graph G=(A U B, E), where each vertex in A U B specifies a strict preference ordering over its neighbors. Each vertex has an upper quota and a lower quota denoting the maximum and minimum number of vertices that can be assigned to it from its neighborhood. In the many-to-many setting with two-sided lower quotas, informally, a critical matching is a matching which fulfils vertex lower quotas to the maximum possible extent. This is a natural generalization of the definition of critical matching in the one-to-one setting [Kavitha T., FSTTCS 2021]. Our goal in the given problem is to find a popular matching in the set of critical matchings. A matching is popular in a given set of matchings if it remains undefeated in a head-to-head election with any matching in that set. Here, vertices cast votes between pairs of matchings. We show that there always exists a matching that is popular in the set of critical matchings. We present an efficient algorithm to compute such a matching of the largest size. We prove the popularity of our matching using a dual certificate.

The classical stable marriage problem asks for a matching between a set of men and a set of women with no blocking pairs, which are pairs formed by a man and a woman who would both prefer switching from their current status to be paired up together. When both men and women have strict preferences over the opposite group, all stable matchings have the same cardinality, and the famous Gale-Shapley algorithm can be used to find one. Differently, if we allow ties in the preference lists, finding a stable matching of maximum cardinality is an NP-hard problem, already when the ties are one-sided, that is, they appear only in the preferences of one group. For this reason, many researchers have focused on developing approximation algorithm for this problem. In this paper, we give a refined analysis of an approximation algorithm given by Huang and Telikepalli (IPCO14) for the stable marriage problem with one-sided ties, which shows an improved 13/9 -approximation factor for the problem. Interestingly, our analysis is tight.

We consider a matching problem in a bipartite graph G = (A∪B, E) where each node in A is an agent having preferences in partial order over her neighbors, while nodes in B are objects with no preferences. The size of our matching is more important than node preferences–thus, we are interested in maximum matchings only. Any pair of maximum matchings in G (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment such that there is no better or “more popular” assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem (Abraham et al., 2007). Popular assignments need not exist in every input instance. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an O∗ (|E|k) time algorithm for deciding if there exists an assignment with unpopularity margin at most k. We then show that this algorithm is essentially optimal by proving that the problem is NP-complete and Wl[1]-hard with parameter k. We also consider the minimum-cost popular assignment problem when there are edge costs, and show this problem to be NP-hard. This hardness holds even when all edge costs are in {0,1} and agents have strict preferences. By contrast, we propose a polynomial-time algorithm to the problem of deciding if there exists a popular assignment with a given set of forced/forbidden edges (this tractability holds even for partially ordered preferences). Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in G.

An instance of the marriage problem is given by a graph $G = (A \cup B,E)$, together with, for each vertex of $G$, a strict preference order over its neighbors. A matching $M$ of $G$ is popular in the marriage instance if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exists and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. Thus, every dominant matching is a max-size popular matching, and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings. The goal of this paper is to show that there are instead differences in the tractability of stable and dominant matchings and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable; however, it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed to show not only positive results on popular matchings (as is known) but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp., max-size) popular matching that is not stable (resp., dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when $G$ is nonbipartite.

We consider a matching problem in a marriage instance G. Every node has a strict preference order ranking its neighbors. There is a set C of prioritized or critical nodes and we are interested in only those matchings that match as many critical nodes as possible. Such matchings are useful in several applications and we call them critical matchings. A stable matching need not be critical. We consider a well-studied relaxation of stability called popularity. Our goal is to find a popular critical matching, i.e., a weak Condorcet winner within the set of critical matchings where nodes are voters. We show that popular critical matchings always exist in G and min-size/max-size such matchings can be efficiently computed.

Let $G$ be a bipartite graph where every node has a strict ranking of its neighbors. For every node, its preferences over neighbors extend naturally to preferences over matchings. Matching $N$ is more popular than matching $M$ if the number of nodes that prefer $N$ to $M$ is more than the number that prefer $M$ to $N$. A maximum matching $M$ in $G$ is a "popular max-matching" if there is no maximum matching in $G$ that is more popular than $M$. Such matchings are relevant in applications where the set of admissible solutions is the set of maximum matchings and we wish to find a best maximum matching as per node preferences. It is known that a popular max-matching always exists in $G$. Here we show a compact extended formulation for the popular max-matching polytope. So when there are edge costs, a min-cost popular max-matching in $G$ can be computed in polynomial time. This is in contrast to the min-cost popular matching problem which is known to be NP-hard. We also consider Pareto-optimality, which is a relaxation of popularity, and show that computing a min-cost Pareto-optimal matching/max-matching is NP-hard.

Abstract Our input is a complete graph G on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is popular. A matching M is popular if M does not lose a head-to-head election against any matching $$M'$$ M ′ : here each vertex casts a vote for the matching in $$\{M,M'\}$$ { M , M ′ } in which it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes $$\texttt {NP}$$ NP -complete for even n, as we show here. This is one of the few graph theoretic problems efficiently solvable when n has one parity and $$\texttt {NP}$$ NP -complete when n has the other parity.

Let G = (A ∪ B, E) be a bipartite graph on n vertices where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if there is no matching N such that vertices that prefer N to M outnumber those that prefer M to N. Popular matchings always exist in G since every stable matching is popular. Thus it is easy to find a popular matching in G - however it is NP-hard to compute a min-cost popular matching in G when there is a cost function on the edge set; moreover it is NP-hard to approximate this to any multiplicative factor. An O^*(2ⁿ) algorithm to compute a min-cost popular matching in G follows from known results. Here we show: - an algorithm with running time O^*(2^{n/4}) ≈ O^*(1.19ⁿ) to compute a min-cost popular matching; - assume all edge costs are non-negative - then given ε > 0, a randomized algorithm with running time poly(n,1/(ε)) to compute a matching M such that cost(M) is at most twice the optimal cost and with high probability, the fraction of all matchings more popular than M is at most 1/2+ε.

Abstract LetGbe a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences overbranchings, i.e., directed forests; a branchingBispopularifBdoes not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide ifGadmits a popular branching or not. We give a characterization of popular branchings in terms ofdual certificatesand use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate thepopular branching polytopein the original space and also show that our algorithm can be modified to compute a branching withleast unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute m goods to n agents in a “fair” manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is “envy-freeness up to any good” (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when n = 3. We show there is always a partition of the set of goods into n + 1 subsets (X1, …, Xn, P) where for i ϵ [n], Xi is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we have: (1) envy-freeness up to any good, (2) no agent values P higher than her own bundle, and (3) fewer than n goods go to charity, i.e., |P| < n (typically m ≫ n). Our proof is constructive. When agents have additive valuations and |P| is large (i.e., when |P| is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 4/7 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 1/2 known for an approximate GMMS allocation.

Let G = (A ∪ B, E) be an instance of the stable marriage problem where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings are a well-studied generalization of stable matchings, introduced with the goal of enlarging the set of admissible solutions, while maintaining a certain level of fairness. Every stable matching is a min-size popular matching. Unfortunately, when there are edge costs, it is NP-hard to find a popular matching of minimum cost – even worse, the min-cost popular matching problem is hard to approximate up to any factor. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most opt by paying the price of mildly relaxing popularity. Our main positive result is a bi-criteria algorithm that finds in polynomial time a near-popular or “quasi-popular” matching of cost at most opt. Key to the algorithm are a number of results for certain polytopes related to matchings. In particular, we give a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost, and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.

We consider the popular matching problem in a graph G = (V,E) on n vertices with strict preferences. A matching M is popular if there is no matching N in G such that vertices that prefer N to M outnumber those that prefer M to N. It is known that it is NP-hard to decide if G has a popular matching or not. There is no faster algorithm known for this problem than the brute force algorithm that could take n! time. Here we show a simply exponential time algorithm for this problem, i.e., one that runs in O^*(k^n) time, where k is a constant. We use the recent breakthrough result on the maximum number of stable matchings possible in such instances to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called truly popular matchings and show an O^*(2^n) time algorithm for the truly popular matching problem.

We consider the landscape of popular matchings in a bipartite graph G where every vertex has strict preferences over its neighbors. This is a very well-studied model in two-sided matching markets. A matching M is popular if it does not lose a head-to-head election against any matching, where each vertex casts a vote for the matching where it gets a better assignment. Roughly speaking, a popular matching is one such that there is no matching where more vertices are happier. The notion of popularity is more relaxed than stability: a classical notion studied for the last several decades. Popular matchings always exist in G since stable matchings always exist in a bipartite graph and every stable matching is popular. Algorithmically speaking, the landscape of popular matching seems to have only a few bright spots. Every stable matching is a min-size popular matching and there are also simple linear time algorithms for computing a max-size popular matching and for the popular edge problem. All these algorithms reduce the popular matching problem to an appropriate question in stable matchings and solve the corresponding stable matching problem. We now know NP-hardness results for many popular matching problems. These include the min-cost/max-weight popular matching problem and the problem of deciding if G admits a popular matching that is neither a min-size nor a max-size popular matching. For non-bipartite graphs, it is NP-hard to even decide if a popular matching exists or not. A mixed matching is a probability distribution or a lottery over matchings. A popular mixed matching is one that never loses a head-to-head election against any mixed matching. As an allocation mechanism, a popular mixed matching has several nice properties. Moreover, finding a max-weight or min-cost popular mixed matching in G is easy (by solving a linear program). Interestingly, there is always an optimal popular mixed matching Pi with a simple structure: Pi = {(M_0,1/2),(M_1,1/2)} where M_0 and M_1 are matchings in G. Popular mixed matchings always exist in non-bipartite graphs as well and can be computed in polynomial time.

We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one. We show that it is NP-complete to decide if a bipartite graph admits a popular matching that is neither stable nor dominant. This gives rise to the anomaly that though it is easy to find min-size and max-size popular matchings in bipartite graphs, it is NP-complete to decide if there exists any popular matching whose size is sandwiched between the two extremes. We also show a number of related hardness results, such as (tight) 1/2-inapproximability of the maximum cost popular matching problem when costs are nonnegative. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph: we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not; we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth, or decide there is no popular matching.

Our input is a bipartite graph G=(A\cup B,E) where each vertex in A\cup B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to cap(a)\geq 1 many courses while each course b seeks cap(b)\geq 1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G - a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.

Our input instance is a bipartite graph G = (A ∪ B, E) where A is a set of applicants, B is a set of jobs, and each vertex u ∊ A ∪ B has a preference list ranking its neighbors in a strict order of preference. For any two matchings M and T in G, let φ (M, T) be the number of vertices that prefer M to T. A matching M is popular if φ(Μ, T) ≥ φ(Τ,M) for all matchings T in G. There is a utility function w : E → ℚ and we consider the problem of matching applicants to jobs in a popular and utility-optimal manner. A popular mixed matching could have a much higher utility than all popular matchings, where a mixed matching is a probability distribution over matchings, i.e., a mixed matching Π = {(M0, p0),…, (Mk, pk)} for some matchings M0,…,Mk and for all i. The function φ(·,) easily extends to mixed matchings; a mixed matching Π is popular if φ(Π,Λ) > φ(Λ, Π) for all mixed matchings Λ in G. Motivated by the fact that a popular mixed matching could have a much higher utility than all popular matchings, we study the popular fractional matching polytope Pg. Our main result is that this polytope is half-integral and in the special case where a stable matching in G is a perfect matching, this polytope is integral. This implies that there is always a max-utility popular mixed matching Π such that where M0 and M1 are matchings in G. As Π can be computed in polynomial time, an immediate consequence of our result is that in order to implement a max-utility popular mixed matching in G, we need just a single random bit. We analyze PG whose description may have exponentially many constraints via an extended formulation with a linear number of constraints. The linear program that gives rise to this formulation has an unusual property: self-duality. In other words, this linear program is identical to its dual program. This is a rare case where an LP of a natural problem has such a property. The self-duality of this LP plays a crucial role in our proof of half-integrality of PG. We also show that our result carries over to the roommates problem, where the graph G need not be bipartite. The polytope of popular fractional matchings is still half-integral here and so we can compute a max-utility popular half-integral matching in G in polynomial time. To complement this result, we also show that the problem of computing a max-utility popular (integral) matching in a roommates instance is NP-hard.

We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: In particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference list of any $b \in B$ may contain ties. A matching $M$ is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to $M$ exceeds the number of vertices that prefer $M$ to $M'$. We show that the problem of deciding whether $G$ admits a popular matching or not is $\mathsf{NP}$-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of $b$ are tied in $b$'s list and $b$ desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in $B$ have no preferences and do not care whether they are matched or not.

In an instance G = (A union B, E) of the stable marriage problem with strict and possibly incomplete preference lists, a matching M is popular if there is no matching M0 where the vertices that prefer M' to M outnumber those that prefer M to M'. All stable matchings are popular and there is a simple linear time algorithm to compute a maximum-size popular matching. More generally, what we seek is a min-cost popular matching where we assume there is a cost function c : E -> Q. However there is no polynomial time algorithm currently known for solving this problem. Here we consider the following generalization of a popular matching called a popular half-integral matching: this is a fractional matching ~x = (M_1 + M_2)/2, where M1 and M2 are the 0-1 edge incidence vectors of matchings in G, such that ~x satisfies popularity constraints. We show that every popular half-integral matching is equivalent to a stable matching in a larger graph G^*. This allows us to solve the min-cost popular half-integral matching problem in polynomial time.

Let G = (V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch \beta if for every (u,v) \in V \times V, \mathsf{dist}_H(u,v) \le \mathsf{dist}_G(u,v) + \beta. The problem of computing sparse spanners with small stretch \beta is well-studied. Here we consider the following relaxation: we are given \p\subseteq V \times V and we seek a sparse subgraph H where \mathsf{dist}_H(u,v)\le \mathsf{dist}_G(u,v) + \beta for each (u,v) \in \p. Such a subgraph is called a pairwise spanner with additive stretch \beta and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: \p = S \times V and \p = S \times T, where S\subseteq V and T\subseteq V, and show sparser pairwise spanners for these cases.

Let $G = (V,E)$ be an undirected unweighted graph on $n$ vertices. A subgraph $H$ of $G$ is called a purely additive spanner of $G$ with stretch $\beta$ if for each $(u,v) \in V \times V$, the $u$-$v$ distance in $H$ is at most $\delta_G(u,v) + \beta$. We currently know sparse purely additive spanners with $\beta = O(1)$ only for $\beta = 2,4,6$. When $\beta = 2$, the size of the spanner is $O(n^{3/2})$; when $\beta = 4$, the size of the spanner is $O(n^{1.4}\log^{0.2}n)$; and when $\beta = 6$, the size of the spanner is $O(n^{4/3})$. The following is a natural relaxation of the above problem: we care for only certain distances, these are captured by the set $\mathcal{P} \subseteq V \times V$, and the problem is to construct a sparse subgraph $H$ (also called a $\mathcal{P}$-spanner), where for every $(u,v) \in \mathcal{P}$, the $u$-$v$ distance in $H$ is at most $\delta_G(u,v) + \beta$. In this paper we show algorithms to construct the following for $\beta = 2$: a $\mathcal{P}$-spanner of size $\tilde{O}(n|\mathcal{P}|^{1/3})$ for any $\mathcal{P}\subseteq V\times V$ and a $\mathcal{P}$-spanner of size $\tilde{O}(n|\mathcal{P}|^{1/4})$ when $\mathcal{P} = S \times V$, where $S \subseteq V$. Our $\mathcal{P}$-spanner with additive stretch 2 leads to a simple deterministic construction of a purely additive spanner with stretch 4 and size $O(n^{1.4}\log^{0.2}n)$. We also consider a variant of the $\mathcal{P}$-spanner problem where the set $\mathcal{P}$ is implicitly given via a distance threshold $D$. That is, $\mathcal{P} = \{(u,v): \delta_G(u,v) \ge D\}$. We refer to such a $\mathcal{P}$-spanner as an approximate $D$-preserver. A $D$-preserver is a subgraph where distances $\ge D$ are exactly preserved and $D$-preservers of size $O(n^2/D)$ are known. For a given $D \in \mathbb{Z}^+$ and any integer $k \ge 1$, we construct an $\tilde{O}(n^{3/2}/D^{k/(2k+2)})$-sized subgraph where distances $\ge D$ are approximated with an additive stretch of $4k$. In particular, when $k = \lfloor\log D\rfloor$, this subgraph has size $\tilde{O}(n\cdot\sqrt{n/D})$.

Given a bipartite graph $G = (\mathcal{A}\cup\mathcal{B}, E)$ where each vertex ranks its neighbors in a strict order of preference, the problem of computing a stable matching is classical and well studied. A stable matching has size at least $\frac{1}{2}|M_{\max}|$, where $M_{\max}$ is a maximum size matching in $G$, and there are simple examples where this bound is tight. It is known that a stable matching is a minimum size popular matching. A matching $M$ is said to be popular if there is no matching where more vertices are better off than in $M$. In this paper we show the first linear time algorithm for computing a maximum size popular matching in $G$. A maximum size popular matching is guaranteed to have size at least $\frac{2}{3}|M_{\max}|$, and this bound is tight. We then consider the following problem: is there a maximum size matching $M^*$ that is popular within the set of maximum size matchings in $G$, that is, $|M^*| = |M_{\max}|$ and there is no maximum size matching that is more popular than $M^*$? We show that such a matching $M^*$ always exists and can be computed in $O(mn_0)$ time, where $m = |E|$ and $n_0 = \min(|\mathcal{A}|,|\mathcal{B}|)$. Though the above matching $M^*$ is popular restricted to the set of maximum size matchings, in the entire set of matchings in $G$, its unpopularity factor could be as high as $n_0-1$. On the other hand, a maximum size popular matching could be of size only $\frac{2}{3}|M_{\max}|$. In between these two extremes, we show there is an entire spectrum of matchings: for any integer $k$, where $2 \le k \le n_0$, there is a matching $M_k$ in $G$ of size at least $\frac{k}{k+1}|M_{\max}|$ whose unpopularity factor is at most $k-1$. Also, such a matching $M_k$ can be computed in $O(km)$ time by a simple generalization of our maximum size popular matching algorithm.

Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.

Given an undirected n-node unweighted graph G = (V, E), a spanner with stretch function f(.) is a subgraph H \subseteq G such that, if two nodes are at distance d in G, then they are at distance at most f(d) in H. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the u-v distance only for pairs (u,v) in a given set P \subseteq V x V. Such P-spanners were studied before [Coppersmith,Elkin'05] only in the special case that f(.) is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same P) and of the best known spanners (with the same f(.)). In more detail, for arbitrary P, we show that there exists a P-spanner of size O(n(|P|log n)^{1/4}) with f(d) = d + 4 log n. Alternatively, for any epsislon > 0, there exists a P-spanner of size O(n|P|^{1/4} sqrt{(log n) / epsilon}) with f(d) = (1 + epsilon)d + 4. We also consider the relevant special case that there is a critical set of nodes S \subseteq V, and we wish to approximate either the distances within nodes in S or from nodes in S to any other node. We show that there exists an (S x S)-spanner of size O(n sqrt{|S|}) with f(d) = d + 2, and an (S x V)-spanner of size O(n sqrt{|S| log n}) with f(d) = d + 2 log n. All the mentioned pairwise spanners can be constructed in polynomial time.

Our input is a graph $G = (V, E)$ where each vertex ranks its neighbors in a strict order of preference. The problem is to compute a matching in $G$ that captures the preferences of the vertices in a popular way. Matching $M$ is more popular than matching $M'$ if the number of vertices that prefer $M$ to $M'$ is more than those that prefer $M'$ to $M$. The unpopularity factor of $M$ measures by what factor any matching can be more popular than $M$. We show that $G$ always admits a matching whose unpopularity factor is $O(\log|V|)$, and such a matching can be computed in linear time. In our problem the optimal matching would be a least unpopularity factor matching---we show that computing such a matching is NP-hard. In fact, for any $\epsilon > 0$, it is NP-hard to compute a matching whose unpopularity factor is at most $4/3 - \epsilon$ of the optimal.

Let G = (V, E) be a graph with positive integral edge weights. Our problem is to find a matching of maximum weight in G. We present a simple iterative algorithm for this problem that uses a maximum cardinality matching algorithm as a subroutine. Using the current fastest maximum cardinality matching algorithms, we solve the maximum weight matching problem in O(W√nm logn(n2/m)) time, or in O(W nω) time with high probability, where n = |V|, m = |E|, W is the largest edge weight, and ω < 2.376 is the exponent of matrix multiplication. In relatively dense graphs, our algorithm performs better than all existing algorithms with W = o(log1.5 n). Our technique hinges on exploiting Edmonds’ matching polytope and its dual.

Given a bipartite graph G = (A ∪ B, E) where each vertex ranks its neighbors in a strict order of preference, we consider the problem of computing a largest matching in the set of popular matchings in G. A matching M is said to be popular if there is no matching where more vertices are happier than in M. The set of popular matchings is non-empty since every stable matching is popular and it is known that stable matchings always exist in G. The problem of computing a popular matching of maximum size in G = (A ∪ B, E) was considered in [8] where an O(mn0) algorithm was shown, where m = |E| and n0 = min(|A|, |B|). Here we show an O(m) algorithm for this problem. A largest popular matching need not be a maximum cardinality matching in G. There are many applications where maximum cardinality is one of the requirements, and so the next problem that we consider is the following: if M is the set of maximum cardinality matchings in G, compute M* ∊ M that is popular within M. That is, we want a maximum cardinality matching M* such that there is no matching in M that is more popular than M*. We show that such a matching M* always exists and can be computed in O(mn0) time. Though the above matching M* is popular in the set of maximum cardinality matchings, in the entire set of matchings in G, its unpopularity factor could be as high as n0 − 1. On the other hand, a largest popular matching could be of size only ⅔|M*|. In between these two extremes, we show that there is an entire spectrum of matchings: for any integer k, where 2 ≤ k ≤ n0, there is a matching Mk in G of size at least whose unpopularity factor is at most k − 1; also such a matching Mk can be computed in O(mk) time by a simple generalization of our largest popular matching algorithm.

We present two online algorithms for maintaining a topological order of a directed n -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O( m 3/2 ) time. For sparse graphs ( m / n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O( n 5/2 ) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Ω( n 2 2 √2 lg n ) time by relating its performance to a generalization of the k -levels problem of combinatorial geometry. A completely different algorithm running in Θ( n 2 log n ) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Refereed conferences require every submission to be reviewed by members of a program committee (PC) in charge of selecting the conference program. There are many software packages available to manage the review process. Typically, in a bidding phase PC members express their personal preferences by ranking the submissions. This information is used by the system to compute an assignment of the papers to referees (PC members). We study the problem of assigning papers to referees . We propose to optimize a number of criteria that aim at achieving fairness among referees/papers. Some of these variants can be solved optimally in polynomial time, while others are NP-hard, in which case we design approximation algorithms. Experimental results strongly suggest that the assignments computed by our algorithms are considerably better than those computed by popular conference management software.

Let $G=(V,E)$ be a weighted undirected graph having nonnegative edge weights. An estimate $\hat{\delta}(u,v)$ of the actual distance $\delta(u,v)$ between $u,v\in V$ is said to be of stretch t if and only if $\delta(u,v)\leq\hat{\delta}(u,v)\leq t\cdot\delta(u,v)$. Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1–24].

We consider a variant of the popular matching problem here. The input instance is a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$, where vertices in $\mathcal{A}$ are called applicants and vertices in $\mathcal{P}$ are called posts. Each applicant ranks a subset of posts in an order of preference, possibly involving ties. A matching M is popular if there is no other matching $M'$ such that the number of applicants who prefer their partners in $M'$ to M exceeds the number of applicants who prefer their partners in M to $M'$. However, the “more popular than” relation is not transitive; hence this relation is not a partial order, and thus there need not be a maximal element here. Indeed, there are simple instances that do not admit popular matchings. The questions of whether an input instance G admits a popular matching and how to compute one if it exists were studied earlier by Abraham et al. Here we study reachability questions among matchings in G, assuming that $G=(\mathcal{A}\cup\mathcal{P},E)$ admits a popular matching. A matching $M_k$ is reachable from $M_0$ if there is a sequence of matchings $\langle M_0,M_1,\dots,M_k\rangle$ such that each matching is more popular than its predecessor. Such a sequence is called a length-k voting path from $M_0$ to $M_k$. We show an interesting property of reachability among matchings in G: there is always a voting path of length at most 2 from any matching to some popular matching. Given a bipartite graph $G=(\mathcal{A}\cup\mathcal{P},E)$ with n vertices and m edges and any matching $M_0$ in G, we give an $O(m\sqrt{n})$ algorithm to compute a shortest-length voting path from $M_0$ to a popular matching; when preference lists are strictly ordered, we have an $O(m+n)$ algorithm. This problem has applications in dynamic matching markets, where applicants and posts can enter and leave the market, and applicants can also change their preferences arbitrarily. After any change, the current matching may no longer be popular, in which case we are required to update it. However, our model demands that we switch from one matching to another only if there is consensus among the applicants to agree to the switch. Hence we need to update via a voting path that ends in a popular matching. Thus our algorithm has applications here.

An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2 k −1, 0)-spanner of size O ( n 1+1/ k ) and an (additive) (1,2)-spanner of size O ( n 3/2 ). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O ( n 4/3 ). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k , a ( k , k −1)-spanner with size O ( kn 1+1/ k ) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

We consider the problem of maintaining information about the rank of a matrix $M$ under changes to its entries. For an $n \times n$ matrix $M$, we show an amortized upper bound of $O(n^{\omega-1})$ arithmetic operations per change for this problem, where $\omega < 2.376$ is the exponent for matrix multiplication, under the assumption that there is a {\em lookahead} of up to $\Theta(n)$ locations. That is, we know up to the next $\Theta(n)$ locations $(i_1,j_1),(i_2,j_2),\ldots,$ whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner.

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_{2}$ generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m 2 n+mn 2log n) algorithm. When the edge weights are integers, we have an O(m 2 n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight.

We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have nonnegative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A $\{-1,0,1\}$ edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get $-1$. The vector space over $\mathbb{Q}$ generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for this vector space. We seek a cycle basis where the sum of weights of the cycles is minimum. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in $\tilde{O}(m^{\omega+1}n)$ time, where $\omega < 2.376$ is the exponent of matrix multiplication. We present an $O(m^3n+m^2n^2\log n)$ algorithm. We obtain our algorithm by using fast matrix multiplication over rings and an efficient extension of Dijkstra's algorithm to compute a shortest cycle in G whose dot product with a function on its edge set is nonzero. We also present a simple $O(m^2n+mn^2\log n)$ Monte Carlo algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem a $\{0,1\}$ edge incidence vector is associated with each cycle and the vector space over $\mathbb{Z}_2$ generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in $O(m^2n + mn^2\log n)$ time and our randomized algorithm for directed graphs matches this running time.

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).

We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving ties. We say that a matching M is popular if there is no matching $M'$ such that the number of applicants preferring $M'$ to M exceeds the number of applicants preferring M to $M'$. In this paper, we give the first polynomial-time algorithms to determine if an instance admits a popular matching and to find a largest such matching, if one exists. For the special case in which every preference list is strictly ordered (i.e., contains no ties), we give an $O(n + m)$ time algorithm, where n is the total number of applicants and posts and m is the total length of all of the preference lists. For the general case in which preference lists may contain ties, we give an $O(\sqrt{n}m)$ time algorithm.

An instance of the stable marriage problem is an undirected bipartite graph G = ( X ∪ W , E ) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no two of which share an endpoint. An edge e = ( a , b ) ∈ E ∖ M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M , and b is unmatched, strictly prefers a to its partner in M , or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an O ( nm ) algorithm for computing strongly stable matchings, where n is the number of vertices and m the number of edges. The previous best algorithm had running time O ( m 2 ). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an O ( m ∑ h∈H p h ) algorithm for computing a strongly stable matching in the hospitals-residents problem, where p h is the quota of a hospital h . The previous best algorithm had running time O ( m 2 ).

Let G = (V, E) be a weighted undirected graph with |V| = n and |E| = m. An estimate deltacirc(u,v) of the distance delta(u,v) in G between u,v isin V is said to be of stretch t iff delta(u,v) les deltacirc(u,v) les t middot delta(u,v). The most efficient algorithms known for computing small stretch distances in G are the approximate distance oracles of (M. Thorup and U. Zwick, 2005) and the three algorithms in (E. Cohen and U. Zwick, 2001) to compute all-pairs stretch t distances for t = 2, 7/3, and 3. We present faster algorithms for these problems. For any integer k ges 1, Thorup and Zwick (2005) gave an O(kmn1k/) algorithm to construct a data structure of size O(kn1 + 1k/) which, given a query (u,v) isin V times V, returns in O(k) time, a 2k - 1 stretch estimate of delta(u, v). But for small values of k, the time to construct the oracle is rather high. Here we present an O(n2log n) algorithm to construct such a data structure of size O(kn1+1k/) for all integers k ges 2. Our query answering time is O(k) for k > 2 and Theta (log n) for k = 2. We use a new generic scheme for all-pairs approximate shortest paths for these results. This scheme also enables us to design faster algorithms for all-pairs t-stretch distances for t = 2 and 7/3, and compute all-pairs almost stretch 2 distances in O(n2log n) time

Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. A rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. This is a relevant concept in any practical matching situation and it was first studied by Irving [2003].We give an algorithm to compute a rank-maximal matching with running time O (min( n + C , C √ n ) m ), where C is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.

An error-correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message. Katz and Trevisan (2000) showed that any such code C: {0, 1} /spl rarr/ /spl Sigma//sup m/ with a decoding algorithm that makes at most q probes must satisfy m = /spl Omega/((n/log |/spl Sigma/|)/sup q/(q-1)/). They assumed that the decoding algorithm is non-adaptive, and left open the question of proving similar bounds for adaptive decoders. We improve the results of Katz and Trevisan (2000) in two ways. First, we give a more direct proof of their result. Second, and this is our main result, we prove that m = /spl Omega/((n/log|/spl Sigma/|)/sup q/(q-1)/) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothing an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method.