3 Search Results for "Trehan, Chhaya"


Document
When You Come at the King You Best Not Miss

Authors: Oded Lachish, Felix Reidl, and Chhaya Trehan

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)


Abstract
A tournament is an orientation of a complete graph. We say that a vertex x in a tournament T controls another vertex y if there exists a directed path of length at most two from x to y. A vertex is called a king if it controls every vertex of the tournament. It is well known that every tournament has a king. We follow Shen, Sheng, and Wu [Jian Shen et al., 2003] in investigating the query complexity of finding a king, that is, the number of arcs in T one has to know in order to surely identify at least one vertex as a king. The aforementioned authors showed that one always has to query at least Ω(n^{4/3}) arcs and provided a strategy that queries at most O(n^{3/2}). While this upper bound has not yet been improved for the original problem, [Biswas et al., 2017] proved that with O(n^{4/3}) queries one can identify a semi-king, meaning a vertex which controls at least half of all vertices. Our contribution is a novel strategy which improves upon the number of controlled vertices: using O(n^{4/3} polylog n) queries, we can identify a (1/2+2/17)-king. To achieve this goal we use a novel structural result for tournaments.

Cite as

Oded Lachish, Felix Reidl, and Chhaya Trehan. When You Come at the King You Best Not Miss. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{lachish_et_al:LIPIcs.FSTTCS.2022.25,
  author =	{Lachish, Oded and Reidl, Felix and Trehan, Chhaya},
  title =	{{When You Come at the King You Best Not Miss}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{25:1--25:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.25},
  URN =		{urn:nbn:de:0030-drops-174177},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.25},
  annote =	{Keywords: Digraphs, tournaments, kings, query complexity}
}
Document
APPROX
(1+ε)-Approximate Shortest Paths in Dynamic Streams

Authors: Michael Elkin and Chhaya Trehan

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)


Abstract
Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2κ-1 versus n^{1+1/κ}, for an integer parameter κ. (In fact, existing solutions also incur an extra factor of 1+ε in the stretch for weighted graphs, and an additional factor of log^{O(1)}n in the space.) The only existing solution of the second type uses n^{1/2 - O(1/κ)} passes over the stream (for space O(n^{1+1/κ})), and applies only to unweighted graphs. In this paper we show that (1+ε)-approximate single-source shortest paths can be computed with Õ(n^{1+1/κ}) space using just constantly many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs. Moreover, the same result applies for multi-source shortest paths, as long as the number of sources is O(n^{1/κ}). We achieve these results by devising efficient dynamic streaming constructions of (1 + ε, β)-spanners and hopsets. On our way to these results, we also devise a new dynamic streaming algorithm for the 1-sparse recovery problem. Even though our algorithm for this task is slightly inferior to the existing algorithms of [S. Ganguly, 2007; Graham Cormode and D. Firmani, 2013], we believe that it is of independent interest.

Cite as

Michael Elkin and Chhaya Trehan. (1+ε)-Approximate Shortest Paths in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.APPROX/RANDOM.2022.51,
  author =	{Elkin, Michael and Trehan, Chhaya},
  title =	{{(1+\epsilon)-Approximate Shortest Paths in Dynamic Streams}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{51:1--51:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  URN =		{urn:nbn:de:0030-drops-171733},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  annote =	{Keywords: Shortest Paths, Dynamic Streams, Approximate Distances, Spanners, Hopsets}
}
Document
On the Termination of Flooding

Authors: Walter Hussak and Amitabh Trehan

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
Flooding is among the simplest and most fundamental of all graph/network algorithms. Consider a (distributed network in the form of a) finite undirected graph G with a distinguished node v that begins flooding by sending copies of the same message to all its neighbours and the neighbours, in the next round, forward the message to all and only the neighbours they did not receive the message from in that round and so on. We assume that nodes do not keep a record of the flooding event, thus, raising the possibility that messages may circulate infinitely even on a finite graph. We call this history-less process amnesiac flooding (to distinguish from a classic distributed implementation of flooding that maintains a history of received messages to ensure a node never sends the same message again). Flooding will terminate when no node in G sends a message in a round, and, thus, subsequent rounds. As far as we know, the question of termination for amnesiac flooding has not been settled - rather, non-termination is implicitly assumed. In this paper, we show that surprisingly synchronous amnesiac flooding always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. In particular, synchronous flooding terminates in e rounds, where e is the eccentricity of the source node, if and only if G is bipartite, and, otherwise, in j rounds where e < j ≤ e+d+1 and d is the diameter of G. Since e is bounded above by d, this implies termination times of at most d and of at most 2d + 1 for bipartite and non-bipartite graphs respectively. This suggests that if communication/broadcast to all nodes is the motivation, the history-less amnesiac flooding is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. Moreover, the clear separation in the termination times of bipartite and non-bipartite graphs may suggest possible mechanisms for distributed discovery of the topology/distances in an arbitrary graph. For comparison, we also show that, for asynchronous networks, however, an adversary can force the process to be non-terminating.

Cite as

Walter Hussak and Amitabh Trehan. On the Termination of Flooding. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{hussak_et_al:LIPIcs.STACS.2020.17,
  author =	{Hussak, Walter and Trehan, Amitabh},
  title =	{{On the Termination of Flooding}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.17},
  URN =		{urn:nbn:de:0030-drops-118786},
  doi =		{10.4230/LIPIcs.STACS.2020.17},
  annote =	{Keywords: Flooding algorithm, Network algorithms, Distributed algorithms, Graph theory, Termination, Bipartiteness, Communication, Broadcast}
}
  • Refine by Author
  • 2 Trehan, Chhaya
  • 1 Elkin, Michael
  • 1 Hussak, Walter
  • 1 Lachish, Oded
  • 1 Reidl, Felix
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Shortest paths
  • Show More...

  • Refine by Keyword
  • 1 Approximate Distances
  • 1 Bipartiteness
  • 1 Broadcast
  • 1 Communication
  • 1 Digraphs
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 1 2020

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