Near-linear query complexity for graph inference

DOI10.1007/978-3-662-47672-7_63MaRDI QIDQ3448836zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Claire Mathieu, Hang Zhou

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.4037

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let $G=(V,E)$ be an unweighted, connected graph of bounded degree. The edge set $E$ is initially unknown, and the graph can be accessed using a emph{distance oracle}, which receives a pair of vertices $(u,v)$ and returns the distance between $u$ and $v$. In the emph{verification} problem, we are given a hypothetical graph $hatG=(V,hatE)$ and want to check whether $G$ is equal to $hatG$. We analyze a natural greedy algorithm and prove that it uses $n^{1+o(1)}$ distance queries. In the more difficult emph{reconstruction} problem, $hatG$ is not given, and the goal is to find the graph $G$. If the graph can be accessed using a emph{shortest path oracle}, which returns not just the distance but an actual shortest path between $u$ and $v$, we show that extending the idea of greedy gives a reconstruction algorithm that uses $n^{1+o(1)}$ shortest path queries. When the graph has bounded treewidth, we further bound the query complexity of the greedy algorithms for both problems by $ildeO(n)$. When the graph is chordal, we provide a randomized algorithm for reconstruction using $ildeO(n)$ distance queries.

Recommendations

• Graph reconstruction and verification
• Graph reconstruction via distance oracles
• Reconstruction and verification of chordal graphs with a distance oracle
• Graph reconstruction with a betweenness oracle
• Network Discovery and Verification with Distance Queries

Cites work

• An optimal algorithm to reconstruct trees from additive distance data
• Approximation algorithms for combinatorial problems
• Distance realization problems with applications to internet tomography
• Exploring networks with traceroute-like probes: Theory and simulations
• Graph reconstruction via distance oracles
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• Network Discovery and Verification with Distance Queries
• Network tomography: recent developments
• On the bias of traceroute sampling
• On the longest path algorithm for reconstructing trees from distance matrices

Cited in

(8)

• A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries
• Graph reconstruction with a betweenness oracle
• Graph reconstruction and verification
• Graph verification with a betweenness oracle
• Graph reconstruction via distance oracles
• Learning hypertrees from shortest path queries
• Quasi-linear distance query reconstruction for graphs of bounded treelength
• Learning a hidden graph using \(O(\log n)\)queries per edge

This page was built for publication: Near-linear query complexity for graph inference

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448836)