Meghana Nasre

We consider the problem of computing popular matchings in a bipartite graph G = (R ∪ H, E) where R and H denote a set of res-idents and a set of hospitals respectively. Each hospital h has a positive capacity denoting the number of residents that can be matched to h. The residents and the hospitals specify strict preferences over each other. This is the well-studied Hospital Residents (HR) problem which is a generaliza-tion of the Stable Marriage (SM) problem. The goal is to assign residents to hospitals optimally while respecting the capacities of the hospitals. Sta-bility is a well-accepted notion of optimality in such problems. However, motivated by the need for larger cardinality matchings, alternative notions of optimality like popularity have been investigated in the SM setting. In this paper, we consider a generalized HR setting – namely the Laminar Classified Stable Matchings (LCSM+) problem. Here, additionally, hospi-tals can specify classifications over residents in their preference lists and classes have upper quotas. We show the following new results: We define a notion of popularity and give a structural characterization of popular matchings for the LCSM+ problem. Assume n = |R| + |H| and m = |E|. We give an O(mn) time algorithm for computing a maximum cardinality popular matching in an LCSM+ instance. We give an O(mn2) time algo-rithm for computing a matching that is popular amongst the maximum cardinality matchings in an LCSM+ instance.

The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using Δ + 1 or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS’17, and Solomon and Wein in ESA’18. In SODA’18, Bhattacharya et al. presented a randomized algorithm that uses Δ + 1 colors and achieves amortized O(log Δ) update time. In STACS’20, Henzinger and Peng presented a randomized (Δ + 1) -coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized (Δ + 1) -coloring algorithm with amortized O(1) update time. While works of Bhattacharya et al., and Henzinger and Peng are very efficient in terms of update time, they do not address the number of recolorings per update. We bridge this gap by providing efficient update time algorithms with constant number of recolorings. Moreover our algorithm is deterministic as opposed to the works of Bhattacharya et al. in SODA’18, and Henzinger and Peng in STACS’20. Next, we study bipartite graphs which can be optimally colored in the static setting. We show that even in the incremental setting (where edges are added to the graph and no edge can be deleted), there is a bad update sequence which forces the update time to be at least Ω (log n) in the amortized setting and Ω (n) in the worst case. This possibly explains the lack of any results on dynamic coloring specific to bipartite graphs. We circumvent this lower bound by proposing two approaches. Firstly, we allow the use of more than two colors and obtain significantly better update time. Second, we introduce the idea of implicit coloring. If the color of a vertex is explicitly stored in a data structure and updated at end of every update then we call such an algorithm as explicit coloring algorithm. All prior work on dynamic coloring uses explicit coloring algorithms. We show that using implicit coloring we can obtain near constant update time and query time for incremental coloring for bipartite case. We also bound the number of recolorings to near constant. We also show an efficient implicit fully dynamic algorithm for bipartite graphs. All our algorithms are deterministic and use simple data structures. Hence, we believe that our algorithms are of practical importance.

The Hospital Residents setting models important problems like school choice, assignment of undergraduate students to degree programs, among many others. In this setting, fixed quotas are associated with programs that limit the number of agents that can be assigned to them. Motivated by scenarios where all agents must be matched, we propose and study the cost-based allocation setting, which allows controlled flexibility with respect to quotas. In our model, we seek to compute a matching that matches all agents and is optimal with respect to preferences, and minimizes either a local or a global objective on costs. We show that there is a sharp contrast – minimizing the local objective is polynomial-time solvable, whereas minimizing the global objective is hard to approximate within a specific constant factor unless P= NP. On the positive side, we present approximation algorithms for the global objective in the general case and a particular hard case. We achieve the approximation guarantee for the particular case via a linear programming based algorithm.

We consider the hospital-residents problem where both hospitals and residents can have lower quotas. The input is a bipartite graph G = (R ∪ H, E), each vertex in R ∪ H has a strict preference ordering over its neighbors. The sets R and H denote the sets of residents and hospitals respectively. Each hospital has an upper and a lower quota denoting the maximum and minimum number of residents that can be assigned to it. Residents have upper quota equal to one, however, there may be a requirement that some residents must not be left unassigned in the output matching. We call this as the residents’ lower quota. We show that whenever the set of matchings satisfying all the lower and upper quotas is nonempty, there always exists a matching that is popular among the matchings in this set. We give a polynomial-time algorithm to compute such a matching.

Let G=(A∪P,E) be a bipartite graph where A denotes a set of applicants, P denotes a set of posts and ranks on the edges denote preferences of the agents over posts. A matching M in G is rank-maximal if it matches the maximum number of applicants to their top-rank post, subject to this, the maximum number of applicants to their second rank post and so on. In this paper, we develop a switching graph characterization of rank-maximal matchings, which is a useful tool that encodes all rank-maximal matchings in an instance. The characterization leads to simple and efficient algorithms for several interesting problems. In particular, we give an efficient algorithm to compute the set of rank-maximal pairs in an instance. We show that the problem of counting the number of rank-maximal matchings is #P-complete and also give an FPRAS for the problem. Finally, we consider the problem of deciding whether a rank-maximal matching is popular among all the rank-maximal matchings in a given instance, and give an efficient algorithm for the problem.

We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph G = (V,E) with positive edge weights. For this problem we present a decremental algorithm (that supports the deletion of a vertex, or weight increases on edges incident to a vertex). Our algorithm runs in amortized O(ν∗2 ・ log n) time per update, where n = |V |, and ν∗ bounds the number of edges that lie on shortest paths through any given vertex. Our APASP algorithm can be used for the decremental computation of betweenness centrality (BC), which is widely used in the analysis of large complex networks. No nontrivial decremental algorithm for either problem was known prior to our work. Our method is a generalization of the decremental algorithm of Demetrescu and Italiano [3] for unique shortest paths, and for graphs with ν∗ = O(n), we match the bound in [3]. Thus for graphs with a constant number of shortest paths between any pair of vertices, our algorithm maintains APASP and BC scores in amortized time O(n2 ・ log n) under decremental updates, regardless of the number of edges in the graph.

We consider the well-studied Hospital Residents (HR) problem in the presence of lower quotas (LQ). The input instance consists of a bipartite graph G = (R ? H, E) where R and H denote sets of residents and hospitals, respectively. Every vertex has a preference list that imposes a strict ordering on its neighbors. In addition, each hospital h has an associated upper-quota q+(h) and a lower-quota q-(h). A matching M in G is an assignment of residents to hospitals, and M is said to be feasible if every resident is assigned to at most one hospital and a hospital h is assigned at least q-(h) and at most q+(h) residents. Stability is a de-facto notion of optimality in a model where both sets of vertices have preferences. A matching is stable if no unassigned pair has an incentive to deviate from it. It is well-known that an instance of the HRLQ problem need not admit a feasible stable matching. In this paper, we consider the notion of popularity for the HRLQ problem. A matching M is popular if no other matching M gets more votes than M when vertices vote between M and M. When there are no lower quotas, there always exists a stable matching and it is known that every stable matching is popular. We show that in an HRLQ instance, although a feasible stable matching need not exist, there is always a matching that is popular in the set of feasible matchings. We give an efficient algorithm to compute a maximum cardinality matching that is popular amongst all the feasible matchings in an HRLQ instance.

Exhaustive identification of all possible alternate pathways that exist in metabolic networks can provide valuable insights into cellular metabolism. With the growing number of metabolic reconstructions, there is a need for an efficient method to enumerate pathways, which can also scale well to large metabolic networks, such as those corresponding to microbial communities. We developed MetQuest, an efficient graph-theoretic algorithm to enumerate all possible pathways of a particular size between a given set of source and target molecules. Our algorithm employs a guided breadth-first search to identify all feasible reactions based on the availability of the precursor molecules, followed by a novel dynamic-programming based enumeration, which assembles these reactions into pathways of a specified size producing the target from the source. We demonstrate several interesting applications of our algorithm, ranging from identifying amino acid biosynthesis pathways to identifying the most diverse pathways involved in degradation of complex molecules. We also illustrate the scalability of our algorithm, by studying large graphs such as those corresponding to microbial communities, and identify several metabolic interactions happening therein. MetQuest is available as a Python package, and the source codes can be found at https://github.com/RamanLab/metquest.

Hassin et al. [9] consider the Max-Exp-Cover-R problem to study the facility location problem on a graph in the presence of unreliable links when the link failure is according to the Linear Reliability Order (LRO) model. They showed that for unbounded R the problem is polynomial time solvable and for R = 1 and planar graphs the problem is NP-Complete. In this paper, we study the Max-Exp-Cover-1 problem under the LRO edge failure model. We obtain a fixed parameter tractable algorithm for Max-Exp-Cover-1 problem for bounded treewidth graphs, parameterized by the treewidth. We extend the Baker’s technique (Baker, J. ACM 1994) to obtain PTAS for Max-Exp-Cover-1 problem under the LRO model on planar graphs. We observe that the coverage function of the Max-Exp-Cover-R problem is submodular and the problem admits a (1 - 1/e)-approximation for any failure model in which the expected coverage of a set by another set can be computed in polynomial time.

We consider the problem of computing matchings under two-sided preferences in the presence of lower as well as upper-quota requirements for the resources. In the presence of lower-quotas a feasible matching may not exist and hence we focus on critical matchings. Informally, a critical matching achieves the smallest deficiency. We first consider two well-studied notions of optimality with respect to preferences, namely stability and envy-freeness. There exist instances that do not admit a critical stable matching or a critical envy-free matching. When critical matching satisfying the optimality criteria does not exist, we focus on computing a minimum-deficiency matching among all stable or envy-free matchings. To ensure guaranteed existence of an optimal critical matching, we introduce and study a new notion of optimality, namely relaxed stability. We show that every instance admits a critical relaxed stable matching and it can be efficiently computed. We then investigate the computational complexity of computing maximum size optimal matchings with smallest deficiency. Our results show that computing a maximum size minimum-deficiency envy-free matching and a maximum size critical relaxed stable matching are both hard to approximate within 2119-ϵ, for any ϵ> 0 unless P = NP. For envy-free matchings, we present an approximation algorithm for general instances and a polynomial time exact algorithm for a special case. For relaxed stable matchings, we present a constant factor approximation algorithm for general instances.