Leírás
A graph property is said to be elusive (or evasive) if every algorithm testing this property by asking questions of the form " is there an edge between vertices x and y?" requires, in the worst case, to ask about all pairs of vertices.
The unsettled Aanderaa-Karp-Rosenberg conjecture is that every non-trivial monotone graph property is elusive for any finite vertex set.
We show that the situation is completely different for infinite vertex sets: the monotone graph properties "every vertex has degree at least n" and "every connected component has size at least m", where n ≥ 1 and m ≥ 2 are natural numbers, are not elusive for infinite vertex sets, but the monotone graph
property " the graph contains a cycle" is elusive for arbitrary vertex set.
On the other hand, we also prove that every algorithm testing some natural monotone graph properties should check "lots of edges", e.g, all the edges of an infnite complete subgraph.
Zoom link: https://us06web.zoom.us/j/4012456659