Edge and pair queries-random graphs and complexity

DOI10.37236/11159MaRDI QIDQ6162142zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat

Publication date 15 June 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bounded degree graphsbinomial random graphsquery games

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.

Recommendations

• Searching for an edge in a graph
• Learning Theory
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Approximate Discovery of Random Graphs
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties

Cites work

• scientific article; zbMATH DE number 2086235 (Why is no real title available?)
• scientific article; zbMATH DE number 5764837 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• A note on the localization number of random graphs: diameter two case
• An efficient noisy binary search in graphs via Median approximation
• Approximation strategies for generalized binary search in weighted trees
• Bounds on the localization number
• Centroidal bases in graphs
• Centroidal localization game
• Computing with Noisy Information
• Deterministic and probabilistic binary search in graphs
• Edge ranking of weighted trees
• Introduction to Random Graphs
• LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
• Localization game for random geometric graphs
• Localization game for random graphs
• Localization game on geometric and planar graphs
• Locating a backtracking robber on a tree
• Locating a robber on a graph via distance queries
• Metric dimension for random graphs
• Noisy binary search and its applications
• On binary searching with nonuniform costs
• On minimum edge ranking spanning trees
• On the limiting distribution of the metric dimension for random forests
• On the tree search problem with non-uniform costs
• Optimal Search in Trees
• Random graphs.
• The Diameter of Random Graphs
• The Role of Elimination Trees in Sparse Factorization
• The binary identification problem for weighted trees
• The localization capture time of a graph
• Tree-depth, subgraph coloring and homomorphism bounds
• Twenty (simple) questions

Cited in

(2)

• Approximate Discovery of Random Graphs
• A probabilistic upper bound for the edge identification complexity of graphs

This page was built for publication: Edge and pair queries-random graphs and complexity

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