Ehrenfeucht-Fraisse Game and Subgraph Isomorphism (2010)

Originators: Gregory Puleo (presented by Gregory Puleo - REGS 2010)

Definitions: An ordered graph is a graph equipped with a linear order ≤ on the vertex set. (In some other problems, an ordered graph is a graph with a linear order on the edge set.) For any two ordered graphs G and H, the r-round Ehrenfeucht-Fraïssé Game on G and H, denoted (G,H;r), is played by two players named Spoiler and Duplicator. In each round, a vertex a_i is chosen from V(G) and a vertex b_i is chosen from V(H).

Spoiler chooses first and may choose from V(G) (obtaining a_i) or from H (obtaining b_i).
Duplicator then chooses from the other graph, picking a vertex that becomes b_i or a_i, respectively.

After r rounds, we have a₁,…,a_r in V(G) and b₁,…,b_r in V(H). Duplicator wins if the map taking each a_i to b_i is an isomorphism and preserves the linear order inherited by the chosen vertices from the given orderings of V(G) and V(H). Otherwise, Spoiler wins. Given finite graphs, (G,H;r) is a finite-length game of perfect information with no draws, so one player or the other has a winning strategy. When Duplicator has a winning strategy, we say that G and H are r-equivalent and write G ~_r H.

When P is an ordered graph, the quantifier depth of P is the least r such that whenever P is a sub-ordered graph of G and is not a sub-ordered graph of H, Spoiler wins (G,H;r) (i.e., G and H are not r-equivalent). We write qd(P) for the quantifier depth of P. We extend the definition of quantifier depth to unordered graphs as follows: if P is an unordered graph, then qd(P) is the maximum quantifier depth among all orderings of the vertices of P. These games and the notion of quantifier depth are motivated by applications in logic and computability theory, which we describe later.

Example: The ordered graph consisting of a 3-vertex path P with the three vertices numbered in order along the path has quantifier depth 2. All claims of this form require two separate arguments: one argument to prove qd(P) > 1 by demonstrating that Duplicator can win the 1-round game on some pair of graphs such that P is a sub-ordered graph of one but not the other, and another argument to show that qd(P) ≤ 2 by presenting a Spoiler strategy for the 2-round game. In fact, Duplicator wins the 1-round game on any pair of graphs: in response to Spoiler's move, Duplicator picks any vertex in the other graph (all 2-vertex graphs are isomorphic).
Consider any G and H with P appearing in G and not H. To specify a 2-round Spoiler strategy, we use 1,2,3 to denote the vertices of the copy of P contained in G.

On the first round, Spoiler picks a₁ = 2.
Duplicator responds with some b₁ in V(H). Since H does not contain P, it cannot have both a higher neighbor and a lower neighbor of b₁. In the first case, Spoiler picks a₂ = 3; in the second case, Spoiler picks a₂ = 1.

Duplicator now cannot choose b₂ to preserve both the order and the adjacencies.

Problem 1: Determine the quantifier depth for interesting classes of graphs. In particular, what is the quantifier depth of the cycle C_n?

Question 2: How is quantifier depth be related to other graph invariants?

Comments: If an ordered graph P has n vertices, then always qd(P) ≤ n: if P appears in G but not H, then in the n-round game Spoiler simply chooses all of one copy of P in G. Duplicator cannot mimic this, since P does not appear in H. A slightly more involved argument gives qd(P) ≤ 1+n(1-1/(Δ(P)+3)). Known results about the ~_r classes of linear orders (Theorem 2.3.20 in [GKL]) imply qd(P) > lg n.

Conjecture 3: If P is an ordered graph with quantifier depth r such that P appears in G but not H, then Spoiler wins the asymmetric r-round G→H game, which differs from (G,H;r) only in that Spoiler must pick vertices only in G.

Comments: Conjecture 3 would make it substantially easier to prove lower bounds for quantifier depth: one can add gadgets to H to make life easier for Duplicator without worrying about helping Spoiler, since Spoiler is not allowed to choose vertices there.

Background: Ehrenfeucht-Fraïssé games are a central tool in finite model theory, often used to prove inexpressibility results. For example, one can use them to prove that there is no first-order formula defining connectedness of a graph. While very few interesting properties of graphs are first-order definable, it is easy for any particular graph P to write a formula expressing “P is a sub-ordered graph” of H. In some sense, we are trying to measure the complexity of P by asking how complex such a formula must be.

There is also an algorithmic motivation for studying these formulas: it takes O(n^r) time to check whether a formula of quantifier depth r holds on a graph of order n, so if P is a graph of quantifier depth r, then there is a O(n^r) algorithm for testing whether P occurs in H (we pick an arbitrary ordering of the big graph and test the presence of all orderings of P, using the corresponding formula to check for them. Each formula takes O(n^r) time to test.

Comments: At first glance, the ordering seems like an extraneous complication: why not talk about quantifier depth for ordinary graphs? The answer is that the question is trivial in that case. Since Duplicator wins the (n-1)-round K_n, K_n-1 game, the “unordered quantifier depth” of any unordered n-vertex graph P is exactly n. Introducing the ordering gives enough extra structure to make the question nontrivial (in particular, it gives some global structure).

References:
[GKL] E. Grädel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema, S. Weinstein; Finite Model Theory and its Applications, Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, 2007. xiv+437 pp.