2 Search Results for "Chatterjee, Kushagra"

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-dev.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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.35
Pairwise Reachability Oracles and Preservers Under Failures

Authors: Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let G = (V, E) be a directed graph on n-nodes, and P ⊆ V× V be a set of vertex pairs in G. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we provide extremal bounds for sparse fault-tolerant reachability preservers, resilient to two or more failures. Prior to this work, such oracles and reachability preservers were widely studied for the special scenario of single-source and all-pairs settings. However, for the scenario of arbitrary pairs, no prior (non-trivial) results were known for dual (or more) failures, except those implied from the single-source setting. One of the main questions is whether it is possible to beat the O(n |P|) size bound (derived from the single-source setting) for reachability oracle and preserver for dual failures (or O(2^k n|P|) bound for k failures). We answer this question affirmatively. Below we summarize our contributions. - For an n-vertex directed graph G = (V, E) and P ⊆ V× V, we present a construction of O(n √{|P|}) sized dual fault-tolerant pairwise reachability oracle with constant query time. We further provide a matching (up to the word size) lower bound of Ω(n √{|P|}) on the size (in bits) of the oracle for the dual fault setting, thereby proving that our oracle is (near-)optimal. - Next, we provide a construction of O(n + min{|P|√ n,~n√{|P|}}) sized oracle with O(1) query time, resilient to single node/edge failure. In particular, for |P| bounded by O(√n) this yields an oracle of just O(n) size. We complement the upper bound with a lower bound of Ω(n^{2/3}|P|^{1/2}) (in bits), refuting the possibility of a linear-sized oracle for P of size ω(n^{2/3}). - We also present a construction of O(n^{4/3} |P|^{1/3}) sized pairwise reachability preservers resilient to dual edge/vertex failures. Previously, such preservers were known to exist only under single failure and had O(n+min{|P|√n,~n√ {|P|}}) size [Chakraborty and Choudhary, ICALP'20]. We also show a lower bound of Ω(n √{|P|}) edges on the size of dual fault-tolerant reachability preservers, thereby providing a sharp gap between single and dual fault-tolerant reachability preservers for |P| = o(n). - Finally, we provide a generic pairwise reachability preserver construction that provides a o(2^k n |P|) sized subgraph resilient to k failures, for any k ≥ 1. Before this work, we only knew of an O(2^k n |P|) bound implied from the single-source setting [Baswana, Choudhary, and Roditty, STOC'16].
Cite as

Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary. Pairwise Reachability Oracles and Preservers Under Failures. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2022.35,
  author =	{Chakraborty, Diptarka and Chatterjee, Kushagra and Choudhary, Keerti},
  title =	{{Pairwise Reachability Oracles and Preservers Under Failures}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.35},
  URN =		{urn:nbn:de:0030-drops-163768},
  doi =		{10.4230/LIPIcs.ICALP.2022.35},
  annote =	{Keywords: Fault-tolerant, Reachability Oracle, Reachability Preservers, Graph sparsification, Lower bounds}
}
  • Refine by Author
  • 2 Chatterjee, Kushagra
  • 1 Chakraborty, Diptarka
  • 1 Choudhary, Keerti
  • 1 Nimbhorkar, Prajakta

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 Fault-tolerant
  • 1 Graph sparsification
  • 1 Lower bounds
  • 1 Matching
  • 1 Popular feasible Matching
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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