Edge and pair queries-random graphs and complexity

DOI10.37236/11159zbMATH Open1516.05143arXiv2203.06006OpenAlexW4379231163MaRDI QIDQ6162142FDOQ6162142

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)

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.

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

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

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)

Cites Work

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

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)