Originators: Martin Aigner, Eberhard Triesch, and Zsolt Tuza (presented by Oleg Pikhurko - REGS 2010)
Definitions and Background: The following problem was introduced by Aigner, Triesch and Tuza [ATT]. We want to determine an unknown acyclic orientation of the given graph G by querying edges one by one. For example, if we have already established that there is a directed path from x to y, then the orientation of xy is determined (since no directed cycles are allowed) and there is no need to query this edge. Let the c(G) be the minimum number of queries we need in the worst case.
For example, if G=Kn is the complete graph on n vertices, then c(Kn) equals the minimum number of comparisons needed to sort n elements, which was one motivation for studying this function. Let us call a graph G exhaustive if c(G)=e(G), that is, we have to query every edge.
Conjecture 1 (Aigner, Triesch, and Tuza [ATT]): There is a constant C such that c(n)≤n²/4+C, where c(n) is the maximum value of c(G) over all graphs G of order n.
Comments: It is easy to see that every bipartite graph is exhaustive. Thus c(n)≥n²/4. On the other hand, it is shown in [P] that c(n)≤(1/4+o(1))n². Surprisingly, this is achieved by considering a probabilistic strategy where some o(n²) random edges are queries in Stage 1. Then it is argued that, almost surely, the graph H consisting of those pairs whose orientation is still undetermined has o(n³) triangles. By well-known results from extremal graph theory, we have e(H)≤ (1/4+o(1))n². Thus we can just query all edges of H in Stage 2.
In REGS, Bill Kinnersley generalized the observation that every bipartite graph is exhuastive by observing that every cover graph is exhaustive. A cover graph, being the graph of the cover relation in a poset, has an acyclic orientation with no dependent edge. If the adversary gives answers consistent with this orientation, then the player must check every edge (since he cannot be sure that any given edge has not been reversed). This suggests asking whether the converse is also true; are all exhaustive graphs cover graphs? This need not be true for graphs with triangles, but perhaps it is true for triangle-free graphs. Consider first the Grötzsch graph, which is not a cover graph; is it exhaustive?
Conjecture 2 (Alon and Tuza [AT]): Let G be generated from the standard random graph model Gn,p, where each pair forms an edge with probability p. Let n tend to infinity and p=p(n) be an arbitrary function. Then almost surely c(G)=O(n log(n)).
Comments: Alon and Tuza [AT] showed that almost surely c(G)=O(n log³(n)). Also they showed that if we additionally assume that p is a constant, then c(G)=O(n log(n)).
Problem 3 (Tuza (2001)): How hard is it to decide whether G is exhaustive?
Comments: It was shown in [P] that it is NP-hard to approximate c(G) within factor less than 74/73. On the other hand, it is open whether there is a polynomial algorithm that approximates c(G) within some constant factor. If it is true that all exhaustive triangle-free graphs are cover graphs, then checking exhaustiveness is NP-hard, since recognition of cover graphs is NP-hard.
References:
[AT] N.Alon and Z.Tuza, The acyclic orientation game on random
graphs, Random Structures and Algorithms, 6 (1995) 261-268.
[ATT] M.Aigner, E.Triesch and Z.Tuza, Searching for acyclic
orientation of graphs, Discrete Mathematics, 144 (1995) 3-10.
[P] O.Pikhurko, Finding an unknown acyclic orientation of a
given graph, Combinatorics, Probability and Computing, 19
(2010) 121-131.