Edge and Pair Queries -- Random Graphs and Complexity

2022/03/11 by Dereniowski, Dariusz, Gordinowicz, Przemysław, Prałat, Paweł · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2203.06006

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.

Cited by

• Approximating the Average-Case Graph Search Problem with Non-Uniform Costs

Related

• Reconstructing random graphs from distance queries
• A tight bound for the clique query problem in two rounds
• Finding paths in sparse random graphs requires many queries
• Query Complexity of Tournament Solutions
• Finding cliques and dense subgraphs using edge queries