9 Search Results for "Nasre, Meghana"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.11
Stability Notions for Hospital Residents with Sizes

Authors: Haricharan Balasundaram, J. B. Krishnashree, Girija Limaye, and Meghana Nasre

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The Hospital Residents problem with sizes (HRS) is a generalisation of the well-studied hospital residents (HR) problem. In the HRS problem, an agent a has a size s(a) and the agent occupies s(a) many positions of the hospital h when assigned to h. The notion of stability in this setting is suitably modified, and it is known that deciding whether an HRS instance admits a stable matching is NP-hard under severe restrictions. In this work, we explore a variation of stability, which we term occupancy-based stability. This notion was defined by McDermid and Manlove (J. of Comb. Opt. 2010) but remained unexplored to the best of our knowledge. In our work, we show that every HRS instance admits an occupancy-stable matching. We further show that computing a maximum-size occupancy-stable matching is NP-hard. We complement our hardness result by providing an approximation algorithm with a guarantee strictly better than 3 for the max-size occupancy-stable matching problem. Given that the classical notion of stability adapted for HRS is not guaranteed to exist in general, we show a practical restriction under which a stable matching is guaranteed to exist. We present an efficient algorithm to output a stable matching in the restricted HRS instances. We also provide an alternate NP-hardness proof for the decision version of the stable matching problem for HRS which imposes a severe restriction on the number of neighbours of non-unit sized agents.
Cite as

Haricharan Balasundaram, J. B. Krishnashree, Girija Limaye, and Meghana Nasre. Stability Notions for Hospital Residents with Sizes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balasundaram_et_al:LIPIcs.FSTTCS.2025.11,
  author =	{Balasundaram, Haricharan and Krishnashree, J. B. and Limaye, Girija and Nasre, Meghana},
  title =	{{Stability Notions for Hospital Residents with Sizes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.11},
  URN =		{urn:nbn:de:0030-drops-250914},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.11},
  annote =	{Keywords: Stable matchings, Hospital Residents with sizes, Approximation algorithms, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.20
Group Fairness and Multi-Criteria Optimization in School Assignment

Authors: Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
We consider the problem of assigning students to schools when students have different utilities for schools and schools have limited capacities. The students belong to demographic groups, and fairness over these groups is captured either by concave objectives, or additional constraints on the utility of the groups. We present approximation algorithms for this assignment problem with group fairness via convex program rounding. These algorithms achieve various trade-offs between capacity violation and running time. We also show that our techniques easily extend to the setting where there are arbitrary constraints on the feasible assignment, capturing multi-criteria optimization. We present simulation results that demonstrate that the rounding methods are practical even on large problem instances, with the empirical capacity violation being much better than the theoretical bounds.
Cite as

Santhini K. A., Kamesh Munagala, Meghana Nasre, and Govind S. Sankar. Group Fairness and Multi-Criteria Optimization in School Assignment. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{k.a._et_al:LIPIcs.FORC.2025.20,
  author =	{K. A., Santhini and Munagala, Kamesh and Nasre, Meghana and S. Sankar, Govind},
  title =	{{Group Fairness and Multi-Criteria Optimization in School Assignment}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.20},
  URN =		{urn:nbn:de:0030-drops-231471},
  doi =		{10.4230/LIPIcs.FORC.2025.20},
  annote =	{Keywords: School Assignment, Approximation Algorithms, Group Fairness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.70
Colorful Vertex Recoloring of Bipartite Graphs

Authors: Boaz Patt-Shamir, Adi Rosén, and Seeun William Umboh

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider the problem of vertex recoloring: we are given n vertices with their initial coloring, and edges arrive in an online fashion. The algorithm is required to maintain a valid coloring by means of vertex recoloring, where recoloring a vertex incurs a cost. The problem abstracts a scenario of job placement in machines (possibly in the cloud), where vertices represent jobs, colors represent machines, and edges represent "anti affinity" (disengagement) constraints. Online coloring in this setting is a hard problem, and only a few cases were analyzed. One family of instances which is fairly well-understood is bipartite graphs, i.e., instances in which two colors are sufficient to satisfy all constraints. In this case it is known that the competitive ratio of vertex recoloring is Θ(log n). In this paper we propose a generalization of the problem, which allows using additional colors (possibly at a higher cost), to improve overall performance. Concretely, we analyze the simple case of bipartite graphs of bounded largest bond (a bond of a connected graph is an edge-cut that partitions the graph into two connected components). From the upper bound perspective, we propose two algorithms. One algorithm exhibits a trade-off for the uniform-cost case: given Ω(logβ) ≤ c ≤ O(log n) colors, the algorithm guarantees that its cost is at most O((log n)/c) times the optimal offline cost for two colors, where n is the number of vertices and β is the size of the largest bond of the graph. The other algorithm is designed for the case where the additional colors come at a higher cost, D > 1: given Δ additional colors, where Δ is the maximum degree in the graph, the algorithm guarantees a competitive ratio of O(log D). From the lower bounds viewpoint, we show that if the cost of the extra colors is D > 1, no algorithm (even randomized) can achieve a competitive ratio of o(log D). We also show that in the case of general bipartite graphs (i.e., of unbounded bond size), any deterministic online algorithm has competitive ratio Ω(min(D,log n)).
Cite as

Boaz Patt-Shamir, Adi Rosén, and Seeun William Umboh. Colorful Vertex Recoloring of Bipartite Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 70:1-70:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pattshamir_et_al:LIPIcs.STACS.2025.70,
  author =	{Patt-Shamir, Boaz and Ros\'{e}n, Adi and Umboh, Seeun William},
  title =	{{Colorful Vertex Recoloring of Bipartite Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{70:1--70:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.70},
  URN =		{urn:nbn:de:0030-drops-228955},
  doi =		{10.4230/LIPIcs.STACS.2025.70},
  annote =	{Keywords: online algorithms, competitive analysis, resource augmentation, graph coloring}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.54
Popular Edges with Critical Nodes

Authors: Kushagra Chatterjee and Prajakta Nimbhorkar

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
In the popular edge problem, the input is a bipartite graph G = (A ∪ B,E) where A and B denote a set of men and a set of women respectively, and each vertex in A∪ B has a strict preference ordering over its neighbours. A matching M in G is said to be popular if there is no other matching M' such that the number of vertices that prefer M' to M is more than the number of vertices that prefer M to M'. The goal is to determine, whether a given edge e belongs to some popular matching in G. A polynomial-time algorithm for this problem appears in [Cseh and Kavitha, 2018]. We consider the popular edge problem when some men or women are prioritized or critical. A matching that matches all the critical nodes is termed as a feasible matching. It follows from [Telikepalli Kavitha, 2014; Kavitha, 2021; Nasre et al., 2021; Meghana Nasre and Prajakta Nimbhorkar, 2017] that, when G admits a feasible matching, there always exists a matching that is popular among all feasible matchings. We give a polynomial-time algorithm for the popular edge problem in the presence of critical men or women. We also show that an analogous result does not hold in the many-to-one setting, which is known as the Hospital-Residents Problem in literature, even when there are no critical nodes.
Cite as

Kushagra Chatterjee and Prajakta Nimbhorkar. Popular Edges with Critical Nodes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.ISAAC.2022.54,
  author =	{Chatterjee, Kushagra and Nimbhorkar, Prajakta},
  title =	{{Popular Edges with Critical Nodes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.54},
  URN =		{urn:nbn:de:0030-drops-173399},
  doi =		{10.4230/LIPIcs.ISAAC.2022.54},
  annote =	{Keywords: Matching, Stable Matching, Popular feasible Matching}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.30
Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas

Authors: Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We consider the hospital-residents problem where both hospitals and residents can have lower quotas. The input is a bipartite graph G = (ℛ∪ℋ,E), each vertex in ℛ∪ℋ has a strict preference ordering over its neighbors. The sets ℛ and ℋ 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 non-empty, 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.
Cite as

Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, and Ankita Sarkar. Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nasre_et_al:LIPIcs.FSTTCS.2021.30,
  author =	{Nasre, Meghana and Nimbhorkar, Prajakta and Ranjan, Keshav and Sarkar, Ankita},
  title =	{{Popular Matchings in the Hospital-Residents Problem with Two-Sided Lower Quotas}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.30},
  URN =		{urn:nbn:de:0030-drops-155419},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.30},
  annote =	{Keywords: Matching, Popularity, Lower quota, Preferences}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.9
How Good Are Popular Matchings?

Authors: Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
In this paper, we consider the Hospital Residents problem (HR) and the Hospital Residents problem with Lower Quotas (HRLQ). In this model with two sided preferences, stability is a well accepted notion of optimality. However, in the presence of lower quotas, a stable and feasible matching need not exist. For the HRLQ problem, our goal therefore is to output a good feasible matching assuming that a feasible matching exists. Computing matchings with minimum number of blocking pairs (Min-BP) and minimum number of blocking residents (Min-BR) are known to be NP-Complete. The only approximation algorithms for these problems work under severe restrictions on the preference lists. We present an algorithm which circumvents this restriction and computes a popular matching in the HRLQ instance. We show that on data-sets generated using various generators, our algorithm performs very well in terms of blocking pairs and blocking residents. Yokoi [Yokoi, 2017] recently studied envy-free matchings for the HRLQ problem. We propose a simple modification to Yokoi's algorithm to output a maximal envy-free matching. We observe that popular matchings outperform envy-free matchings on several parameters of practical importance, like size, number of blocking pairs, number of blocking residents. In the absence of lower quotas, that is, in the Hospital Residents (HR) problem, stable matchings are guaranteed to exist. Even in this case, we show that popularity is a practical alternative to stability. For instance, on synthetic data-sets generated using a particular model, as well as on real world data-sets, a popular matching is on an average 8-10% larger in size, matches more number of residents to their top-choice, and more residents prefer the popular matching as compared to a stable matching. Our comprehensive study reveals the practical appeal of popular matchings for the HR and HRLQ problems. To the best of our knowledge, this is the first study on the empirical evaluation of popular matchings in this setting.
Cite as

Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat. How Good Are Popular Matchings?. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{am_et_al:LIPIcs.SEA.2018.9,
  author =	{A M, Krishnapriya and Nasre, Meghana and Nimbhorkar, Prajakta and Rawat, Amit},
  title =	{{How Good Are Popular Matchings?}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.9},
  URN =		{urn:nbn:de:0030-drops-89440},
  doi =		{10.4230/LIPIcs.SEA.2018.9},
  annote =	{Keywords: bipartite graphs, hospital residents, lower-quotas, popular matchings}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.44
Popular Matchings with Lower Quotas

Authors: Meghana Nasre and Prajakta Nimbhorkar

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
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 U 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 has an associated upper-quota and a lower-quota. 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 is assigned at least its lower-quota many residents and at most its upper-quota many 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.
Cite as

Meghana Nasre and Prajakta Nimbhorkar. Popular Matchings with Lower Quotas. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nasre_et_al:LIPIcs.FSTTCS.2017.44,
  author =	{Nasre, Meghana and Nimbhorkar, Prajakta},
  title =	{{Popular Matchings with Lower Quotas}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.44},
  URN =		{urn:nbn:de:0030-drops-83937},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.44},
  annote =	{Keywords: bipartite matchings, preferences, hospital residents, lower-quota, popular matchings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.412
Popular Matchings: Structure and Cheating Strategies

Authors: Meghana Nasre

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We consider the cheating strategies for the popular matchings problem. Let G = (\A \cup \p, E) be a bipartite graph where \A denotes a set of agents, p denotes a set of posts and the edges in E are ranked. Each agent ranks a subset of posts in an order of preference, possibly involving ties. A matching M is popular if there exists no matching M' such that the number of agents that prefer M' to M exceeds the number of agents that prefer M to M'. Consider a centralized market where agents submit their preferences and a central authority matches agents to posts according to the notion of popularity. Since a popular matching need not be unique, we assume that the central authority chooses an arbitrary popular matching. Let a_1 be the sole manipulative agent who is aware of the true preference lists of all other agents. The goal of a_1 is to falsify her preference list to get better always, that is, to improve the set of posts she gets matched to in the falsified instance. We show that the optimal cheating strategy for a single agent to get better always can be computed in O(m+n) time when preference lists are all strict and in O(\sqrt{n}m) time when preference lists are allowed to contain ties. Here n = |\A| + |\p| and m = |E|. To compute the cheating strategies, we develop a switching graph characterization of the popular matchings problem involving ties. The switching graph characterization was studied for the case of strict lists by McDermid and Irving (J. Comb. Optim. 2011) and was open for the case of ties. We show an O(\sqrt{n}m) time algorithm to compute the set of popular pairs using the switching graph. These results are of independent interest and answer a part of the open questions posed by McDermid and Irving.
Cite as

Meghana Nasre. Popular Matchings: Structure and Cheating Strategies. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 412-423, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{nasre:LIPIcs.STACS.2013.412,
  author =	{Nasre, Meghana},
  title =	{{Popular Matchings: Structure and Cheating Strategies}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{412--423},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.412},
  URN =		{urn:nbn:de:0030-drops-39520},
  doi =		{10.4230/LIPIcs.STACS.2013.412},
  annote =	{Keywords: bipartite matchings, preferences, cheating strategies}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.241
Rainbow Connectivity: Hardness and Tractability

Authors: Prabhanjan Ananth, Meghana Nasre, and Kanthi K. Sarpatwar

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: 1) For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. 2) For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. (J. Comb. Opt., 2011) where they prove the hardness for the even case. 3) The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. 4) For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.
Cite as

Prabhanjan Ananth, Meghana Nasre, and Kanthi K. Sarpatwar. Rainbow Connectivity: Hardness and Tractability. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 241-251, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.FSTTCS.2011.241,
  author =	{Ananth, Prabhanjan and Nasre, Meghana and Sarpatwar, Kanthi K.},
  title =	{{Rainbow Connectivity: Hardness and Tractability}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{241--251},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.241},
  URN =		{urn:nbn:de:0030-drops-33535},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.241},
  annote =	{Keywords: Computational Complexity, Rainbow Connectivity, Graph Theory, Fixed Parameter Tractable Algorithms}
}
  • Refine by Type
  • 9 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2022
  • 1 2021
  • 2 2018
  • 1 2013
  • Show More...

  • Refine by Author
  • 7 Nasre, Meghana
  • 4 Nimbhorkar, Prajakta
  • 1 A M, Krishnapriya
  • 1 Ananth, Prabhanjan
  • 1 Balasundaram, Haricharan
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Adversary models
  • Show More...

  • Refine by Keyword
  • 2 Matching
  • 2 bipartite matchings
  • 2 hospital residents
  • 2 popular matchings
  • 2 preferences
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact