Edge and Pair Queries-Random Graphs and Complexity
Dariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat · The Electronic Journal of Combinatorics · 2023
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.