DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2021.35

Algorithms and Hardness for Multidimensional Range Updates and Queries

Authors: Joshua Lau and Angus Ritossa

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

Traditional orthogonal range problems allow queries over a static set of points, each with some value. Dynamic variants allow points to be added or removed, one at a time. To support more powerful updates, we introduce the Grid Range class of data structure problems over arbitrarily large integer arrays in one or more dimensions. These problems allow range updates (such as filling all points in a range with a constant) and queries (such as finding the sum or maximum of values in a range). In this work, we consider these operations along with updates that replace each point in a range with the minimum, maximum, or sum of its existing value, and a constant. In one dimension, it is known that segment trees can be leveraged to facilitate any n of these operations in Õ(n) time overall. Other than a few specific cases, until now, higher dimensional variants have been largely unexplored. Despite their tightly-knit complexity in one dimension, we show that variants induced by subsets of these operations exhibit polynomial separation in two dimensions. In particular, no truly subquadratic time algorithm can support certain pairs of these updates simultaneously without falsifying several popular conjectures. On the positive side, we show that truly subquadratic algorithms can be obtained for variants induced by other subsets. We provide two general approaches to designing such algorithms that can be generalised to online and higher dimensional settings. First, we give almost-tight Õ(n^{3/2}) time algorithms for single-update variants where the update and query operations meet a set of natural conditions. Second, for other variants, we provide a general framework for reducing to instances with a special geometry. Using this, we show that O(m^{3/2-ε}) time algorithms for counting paths and walks of length 2 and 3 between vertex pairs in sparse graphs imply truly subquadratic data structures for certain variants; to this end, we give an Õ(m^{(4ω-1)/(2ω+1)}) = O(m^1.478) time algorithm for counting simple 3-paths between vertex pairs.

Cite as

Joshua Lau and Angus Ritossa. Algorithms and Hardness for Multidimensional Range Updates and Queries. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lau_et_al:LIPIcs.ITCS.2021.35,
  author =	{Lau, Joshua and Ritossa, Angus},
  title =	{{Algorithms and Hardness for Multidimensional Range Updates and Queries}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.35},
  URN =		{urn:nbn:de:0030-drops-135742},
  doi =		{10.4230/LIPIcs.ITCS.2021.35},
  annote =	{Keywords: Orthogonal range, Range updates, Online and Dynamic Data Structures, Fine-grained complexity, Cycle counting}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.59

Minimizing and Computing the Inverse Geodesic Length on Trees

Authors: Serge Gaspers and Joshua Lau

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

For any fixed measure H that maps graphs to real numbers, the MinH problem is defined as follows: given a graph G, an integer k, and a target tau, is there a set S of k vertices that can be deleted, so that H(G - S) is at most tau? In this paper, we consider the MinH problem on trees. We call H balanced on trees if, whenever G is a tree, there is an optimal choice of S such that the components of G - S have sizes bounded by a polynomial in n / k. We show that MinH on trees is Fixed-Parameter Tractable (FPT) for parameter n / k, and furthermore, can be solved in subexponential time, and polynomial space, whenever H is additive, balanced on trees, and computable in polynomial time. A particular measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the efficiency and connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: IGL(G) = sum_{{u,v} subseteq V} 1/d_G(u,v). While MinIGL is W[1]-hard for parameter treewidth, and cannot be solved in 2^{o(k + n + m)} time, even on bipartite graphs with n vertices and m edges, the complexity status of the problem remains open in the case where G is a tree. We show that IGL is balanced on trees, to give a 2^O((n log n)^(5/6)) time, polynomial space algorithm. The distance distribution of G is the sequence {a_i} describing the number of vertex pairs distance i apart in G: a_i = |{{u, v}: d_G(u, v) = i}|. Given only the distance distribution, one can easily determine graph parameters such as diameter, Wiener index, and particularly, the IGL. We show that the distance distribution of a tree can be computed in O(n log^2 n) time by reduction to polynomial multiplication. We also extend the result to graphs with small treewidth by showing that the first p values of the distance distribution can be computed in 2^(O(tw(G))) n^(1 + epsilon) sqrt(p) time, and the entire distance distribution can be computed in 2^(O(tw(G))) n^{1 + epsilon} time, when the diameter of G is O(n^epsilon') for every epsilon' > 0.

Cite as

Serge Gaspers and Joshua Lau. Minimizing and Computing the Inverse Geodesic Length on Trees. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ISAAC.2019.59,
  author =	{Gaspers, Serge and Lau, Joshua},
  title =	{{Minimizing and Computing the Inverse Geodesic Length on Trees}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{59:1--59:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.59},
  URN =		{urn:nbn:de:0030-drops-115555},
  doi =		{10.4230/LIPIcs.ISAAC.2019.59},
  annote =	{Keywords: Trees, Treewidth, Fixed-Parameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution}
}

Search Results

Documents authored by Lau, Joshua

Algorithms and Hardness for Multidimensional Range Updates and Queries

Abstract

Cite as

Minimizing and Computing the Inverse Geodesic Length on Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message