Search

We consider a matching problem in a bipartite graph $G$ where every vertex has a capacity and a strict preference order on its neighbors. Furthermore, there is a cost function on the edge set. We assume $G$ admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible for us and we are interested in those perfect matchings that are popular within the set of perfect matchings. It is known that such matchings (called popular perfect matchings) always exist and can be efficiently computed. What we seek here is not any popular perfect matching, but a min-cost one. We show a polynomial-time algorithm for finding such a matching; this is via a characterization of popular perfect matchings in $G$ in terms of stable matchings in a colorful auxiliary instance. This is a generalization of such a characterization that was known in the one-to-one setting.

Our input is 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 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. Our algorithm is combinatorial, and can be regarded as a primal-dual algorithm. It searches for an arborescence along with its dual certificate, a chain of subsets of $E$, witnessing its popularity. In fact, our algorithm solves the more general popular common base problem in the intersection of two matroids, where one matroid is the partition matroid defined by any partition $E = \bigcup_{v\in V} \delta(v)$ and the other is an arbitrary matroid on $E$ of rank $|V|$, with each $v \in V$ having a partial order over elements in $\delta(v)$. We extend our algorithm to the case with forced or forbidden edges. We also study the related popular colorful forest (or more generally, the popular common independent set) problem where edges are partitioned into color classes, and the task is to find a colorful forest that is popular within the set of all colorful forests. For the case with weak rankings, we formulate the popular colorful forest polytope, and thus show that a minimum-cost popular colorful forest can be computed efficiently. By contrast, we prove that it is NP-hard to compute a minimum-cost popular arborescence, even when rankings are strict., Comment: 28 pages, 15 figures

Let $G = (A \cup 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 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., Comment: A preliminary version of this paper appeared in Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 70:1--70:18, 2020

We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ where nodes in $A$ are agents having preferences in partial order over their neighbors, while nodes in $B$ are objects without preferences. We propose a polynomial-time combinatorial algorithm based on LP duality that finds a maximum matching or assignment in $G$ that is popular among all maximum matchings, if there exists one. Our algorithm can also be used to achieve a trade-off between popularity and cardinality by imposing a penalty on unmatched nodes in $A$. We also provide an $O^*(|E|^k)$ algorithm that finds an assignment whose unpopularity margin is at most $k$; this algorithm is essentially optimal, since the problem is $\mathsf{NP}$-complete and $\mathsf{W}_l[1]$-hard with parameter $k$. We also prove that finding a popular assignment of minimum cost when each edge has an associated binary cost is $\mathsf{NP}$-hard, even if agents have strict preferences. By contrast, we propose a polynomial-time algorithm for the variant of the popular assignment problem with forced/forbidden edges. Finally, we present an application in the context of housing markets., Comment: Preliminary version appeared in Proc. of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), SIAM, pp. 103-123, 2022. The paper now contains Subsections 4.1 and 4.2, an addition to the previous version

Given a graph $G = (V,E)$ where every vertex has a weak ranking over its neighbors, we consider the problem of computing an optimal matching as per agent preferences. Classical notions of optimality such as stability and its relaxation popularity could fail to exist when $G$ is non-bipartite. In light of the non-existence of a popular matching, we consider its relaxations that satisfy universal existence. We find a positive answer in the form of semi-popularity. A matching $M$ is semi-popular if for a majority of the matchings $N$ in $G$, $M$ does not lose a head-to-head election against $N$. We show that a semi-popular matching always exists in any graph $G$ and complement this existence result with a fully polynomial-time randomized approximation scheme (FPRAS). A special subclass of semi-popular matchings is the set of Copeland winners -- the notion of Copeland winner is classical in social choice theory and a Copeland winner always exists in any voting instance. We study the complexity of computing a matching that is a Copeland winner and show there is no polynomial-time algorithm for this problem unless $\mathsf{P} = \mathsf{NP}$., Comment: A preliminary version of this paper appeared in the Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), pages 957-965. An earlier version of this paper was uploaded on arXiv under the title "Matchings and Copeland's Method" (arXiv:2105.13729v2)

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., Comment: 17 pages and 4 figures

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 prove that an EFX allocation of chores always exists. 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., Comment: 21 pages, 1 figure

Let $G$ be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching $B$ is popular if $B$ does 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 if $G$ admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and 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 the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that "approximately popular" branchings always exist.

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 results are two bi-criteria algorithms that find in polynomial time a near-popular or quasi-popular matching of cost at most opt. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than opt. Key to the other algorithm is 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. This version of the paper goes beyond the conference version [12] in the following two points: (i) the algorithm for finding a quasi-popular matching of cost at most that of a min-cost popular fractional matching is new; (ii) the proofs from Section 6.1 and Section 7.3 are now self-contained (the conference version used constructions from [10] to show these lower bounds).

Let $G = (A \cup B, E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ 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 exist 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 indeed there are 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 not only to show positive results on popular matching (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 non-bipartite., Comment: A previous version of this paper was updated on arxiv under the name "Popularity, stability, and the dominant matching polytope"

Our input is a complete graph $G = (V,E)$ on $n$ vertices where each vertex has a strict ranking of all other vertices in $G$. Our 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'$, where each vertex casts a vote for the matching in $\{M,M'\}$ where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching exists or not. The popular matching problem in $G$ is easy to solve for odd $n$. Surprisingly, the problem becomes NP-hard for even $n$, as we show here., Comment: Appeared at FSTTCS 2018

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 stable and dominant matchings are the only two tractable subclasses of popular matchings in bipartite graphs; more precisely, we show that it is NP-complete to decide if $G$ admits a popular matching that is neither stable nor dominant. We also show a number of related hardness results, such as (tight) inapproximability of the maximum weight popular matching problem. 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., Comment: arXiv admin note: text overlap with arXiv:1804.00141

We consider the popular matching problem in a roommates instance with strict preference lists. While popular matchings always exist in a bipartite instance, they need not exist in a roommates instance. The complexity of the popular matching problem in a roommates instance has been an open problem for several years and here we show it is NP-hard. A sub-class of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs. We show that the dominant matching problem in a roommates instance is also NP-hard and this is the case even when the instance admits a stable matching., Comment: 13 pages, 3 figures

We consider the max-size popular matching problem in a roommates instance G = (V,E) with strict preference lists. A matching M is popular if there is no matching M' in G such that the vertices that prefer M' to M outnumber those that prefer M to M'. We show it is NP-hard to compute a max-size popular matching in G. This is in contrast to the tractability of this problem in bipartite graphs where a max-size popular matching can be computed in linear time. We define a subclass of max-size popular matchings called strongly dominant matchings and show a linear time algorithm to solve the strongly dominant matching problem in a roommates instance. We consider a generalization of the max-size popular matching problem in bipartite graphs: this is the max-weight popular matching problem where there is also an edge weight function w and we seek a popular matching of largest weight. We show this is an NP-hard problem and this is so even when w(e) is either 1 or 2 for every edge e. We also show an algorithm with running time O*(2^{n/4}) to find a max-weight popular matching matching in G = (A U B,E)$ on n vertices., Comment: 26 pages, 10 figures

This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications., Comment: An extended abstract of this work will be presented in DISC 2016

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 lists of $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 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., Comment: A shortened version of this paper has appeared at ICALP 2015

Given a bipartite graph G = (A u B, E) with strict preference lists and and edge e*, we ask if there exists a popular matching in G that contains the edge e*. We call this the popular edge problem. A matching M is popular if there is no matching M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. It is known that every stable matching is popular; however G may have no stable matching with the edge e* in it. In this paper we identify another natural subclass of popular matchings called "dominant matchings" and show that if there is a popular matching that contains the edge e*, then there is either a stable matching that contains e* or a dominant matching that contains e*. This allows us to design a linear time algorithm for the popular edge problem. We also use dominant matchings to efficiently test if every popular matching in G is stable or not.

Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ 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 $\cP \subseteq V\times V$. Such $\cP$-spanners were studied before [Coppersmith,Elkin'05] only in the special case that $f(\cdot)$ 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 $\cP$) and of the best known spanners (with the same $f(\cdot)$). In more detail, for arbitrary $\cP$, we show that there exists a $\mathcal{P}$-spanner of size $O(n(|\cP|\log n)^{1/4})$ with $f(d)=d+4\log n$. Alternatively, for any $\eps>0$, there exists a $\cP$-spanner of size $O(n|\cP|^{1/4}\sqrt{\frac{\log n}{\eps}})$ with $f(d)=(1+\eps)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\times S)$-spanner of size $O(n\sqrt{|S|})$ with $f(d)=d+2$, and an $(S\times 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., Comment: Full version of STACS 2013 paper; 13 pages, 2 figures

We present two on-line 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 {\em 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 $\Omega(n^2 2^{\sqrt{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 $\Theta(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., Comment: 31 pages

We consider an extension of the {\em popular matching} problem in this paper. The input to the popular matching problem is a bipartite graph G = (A U B,E), where A is a set of people, B is a set of items, and each person a belonging to A ranks a subset of items in an order of preference, with ties allowed. The popular matching problem seeks to compute a matching M* between people and items such that there is no matching M where more people are happier with M than with M*. Such a matching M* is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item b belonging to B is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to "augment" G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of sqrt{n1}/2, where n1 is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of "constructing" a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is "fixed", we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn1) time, where m is the number of edges.

We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online topological ordering have many applications, including online cycle detection, which is to discover the first edge that introduces a cycle under an arbitrary sequence of edge insertions in a directed graph. In this paper we present efficient algorithms for the online topological ordering problem. We first present a simple algorithm with running time O(n^{5/2}) for the online topological ordering problem. This is the current fastest algorithm for this problem on dense graphs, i.e., when m > n^{5/3}. We then present an algorithm with running time O((m + nlog n)\sqrt{m}); this is more efficient for sparse graphs. Our results yield an improved upper bound of O(min(n^{5/2}, (m + nlog n)sqrt{m})) for the online topological ordering problem.