Examples of graph problems that are $\Omega(n^2)$ when using adjacency matrix representation.

Question

I recently learned about this very nice way to prove that given a simple undirected graph $G = (V, E)$, given as an adjacency matrix $A$, any algorithm deciding if $G$ is Hamiltonian is $\Omega(n^2)$.

The framework for this kind of proof is roughly:

1. Pick an arbitrary algorithm, ALG, for deciding if $G$ is Hamiltonian.
2. Suppose for contradiction that ALG requires $< n^2$ steps.
3. Thus ALG makes $L < n^2$ accesses to $A$, thus some entries are not accessed by ALG.
4. Construct $G_1$ to run ALG on, where $G_1$ is not Hamiltonian.
5. Construct $G_2$ by modifying some entries in $A$, such that $G_1$ and $G_2$ are indistinguishable by ALG and where $G_2$ is Hamiltonian.
6. ALG will say $G_2$ is not Hamiltonian, when in fact it is.
7. So ALG is not a valid algorithm for deciding if $G$ is Hamiltonian, a contradiction.
8. Any valid ALG must therefore make $L \geq n^2$ accesses to $A$, so must be $\Omega(n^2)$.

For this particular problem I constructed the following $G_1$ and $G_2$:

For these $G_1$ and $G_2$, ALG would need to check all $\left(\frac{n}{2}\right)^2$ possible edges $\{i, j\}$ to be sure $G_2$ is not Hamiltonian, so we can apply this framework (by adjusting $L < \left(\frac{n}{2}\right)^2$).

What other graph problems could be proven to be $\Omega(n^2)$ if $G$ is in adjacency matrix form using this framework? I know that deciding if a graph is biconnected or bipartite are other examples, but I was wondering how many other problems this technique can be applied to.

Answer 1

The technical term for what you're asking about is the query complexity of a graph property. Query complexity is exactly the number of entries of the adjacency matrix we must look at to determine if the graph has the property we want or not. The worst possible query complexity is $\binom n2 = \frac{n(n-1)}{2}$: the number of pairs of vertices to ask a query about.

(Even though the adjacency matrix is $n \times n$, it's symmetric, and we never need to look at the diagonal - so the number is cut in slightly more than half.)

So how many properties have high query complexity? It turns out that it's harder to find properties that don't have it. Originally, it was conjectured that all graph properties need $\Omega(n^2)$ tests, but then a not-very-natural example of testing if a graph is a "scorpion graph" was shown to only need $O(n)$. A scorpion graph can be obtained from any $n-3$-vertex graph by adding a vertex $x$ adjacent to everything, then a vertex $y$ adjacent only to $x$, then a vertex $z$ adjacent only to $y$.

It has been shown that all non-trivial monotone graph properties need $\Omega(n^2)$ tests. "Non-trivial" just means "not always true, and not always false" (otherwise it would be easy). "Monotone" means that adding edges to a graph with the property will not destroy it. Many interesting properties are monotone. Being Hamiltonian is one: adding edges will not destroy a Hamiltonian cycle. Other interesting properties (like being planar) are the negation of monotone properties, so the same result applies to them.

The evasiveness conjecture says that actually, all non-trivial monotone properties require all $\binom n2$ entries to be considered. You can see this for simple examples like the property "has at least one edge". Imagine that no matter which $\binom n2 - 1$ vertex pairs you check first, I tell you "there is no edge between those". You still have to keep going and check the last edge! The evasiveness conjecture says that examples like this exist for all non-trivial monotone properties.