Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs

• URL: http://arxiv.org/abs/2502.20148v1
• Date: Thu, 27 Feb 2025 14:39:32 GMT
• Title: Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
• Authors: Adam Wesołowski, Jinge Bao,
• Abstract summary: We propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model.<n>For the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $widetildeO(sqrtmn3/4)$ time.<n>We also establish quantum query lower bounds of $Omega(sqrtnm)$ for all the aforementioned problems through a reduction from the minima finding problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problems of computing eccentricity, radius, and diameter are fundamental to graph theory. These parameters are intrinsically defined based on the distance metric of the graph. In this work, we propose quantum algorithms for the diameter and radius of undirected, weighted graphs in the adjacency list model. The algorithms output diameter and radius with the corresponding paths in $\widetilde{O}(n\sqrt{m})$ time. Additionally, for the diameter, we present a quantum algorithm that approximates the diameter within a $2/3$ ratio in $\widetilde{O}(\sqrt{m}n^{3/4})$ time. We also establish quantum query lower bounds of $\Omega(\sqrt{nm})$ for all the aforementioned problems through a reduction from the minima finding problem.

Related papers

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  We give the first efficient algorithms for the $k$-center problem on dynamic graphs undergoing edge updates. We show a reduction that leads to a fully dynamic $(2+epsilon)$-approximation algorithm for the $k$-center problem.
  arXiv  Detail & Related papers  (2023-07-28T13:50:57Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
  We present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs) We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps.
  arXiv  Detail & Related papers  (2022-12-29T19:07:39Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [6.236743421605786]
  This paper studies the complexity of computing the weighted diameter and radius of a graph in the quantum CONGEST model. We present a quantum algorithm that $widetilde Oleft(minleftn9/10D3/10,nrightright)$, where $D$ denotes the unweighted diameter.
  arXiv  Detail & Related papers  (2022-06-06T17:43:27Z)
• Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model [5.279257531335345]
  This paper investigates he dtistance parameters in the quantum CONGEST models and establishes almost linear lower bounds on eccentricities and APSP. Our results imply that there is not quantum speedup for these two problems.
  arXiv  Detail & Related papers  (2022-06-06T17:42:37Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  We study the problem of robustly estimating the parameter $p$ of an ErdHos-R'enyi random graph on $n$ nodes. We give an inefficient algorithm with similar accuracy for all $gamma 1/2$, the information-theoretic limit.
  arXiv  Detail & Related papers  (2021-11-09T18:43:25Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions. By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic. We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
  arXiv  Detail & Related papers  (2021-02-05T04:25:28Z)
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
  The computation of the diameter is one of the most central problems in distributed computation. We show a $tilde O(sqrtnD)$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model.
  arXiv  Detail & Related papers  (2018-04-09T11:24:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.