# 2FA state complexity of k-Clique?

In simple form:

Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?

## Details

Of interest here are $v$-vertex graphs encoded using a sequence of edges, each edge being a pair of distinct vertices from $\{0,1,\dots,v-1\}$.

Suppose $(M_v)$ is a sequence of two-way finite automata (deterministic or nondeterministic), such that $M_v$ recognizes $k$-Clique on $v$-vertex input graphs and has $s(v)$ states. A general form of the question is then: Is $s(v) = \Omega(v^k)$?

If $k = k(v) = \omega(1)$ and $s(v) \ge v^{k(v)}$ for infinitely many $v$, then NL ≠ NP. Less ambitiously, I am therefore stipulating that $k$ is fixed, and the $k=3$ case is the first nontrivial one.

## Background

A two-way finite automaton (2FA) is a Turing machine which has no workspace, only a fixed number of internal states, but can move its read-only input head back and forth. In contrast, the usual kind of finite automaton (1FA) moves its read-only input head in one direction only. Finite automata can be deterministic (DFA) or nondeterministic (NFA), as well as having one-way or two-way access to their input.

A graph property $Q$ is a subset of graphs. Let $Q_v$ denote the $v$-vertex graphs with property $Q$. For every graph property $Q$, the language $Q_v$ can be recognized by a 1DFA with at most $2^{v(v-1)/2}$ states, by using a state for every possible graph and labelling them according to $Q$, and transitions between states labelled by edges. $Q_v$ is therefore a regular language for any property $Q$. By the Myhill-Nerode theorem there is then a unique up to isomorphism smallest 1DFA that recognizes $Q_v$. If this has $2^{s(v)}$ states, then standard blowup bounds yield that a 2FA recognizing $Q_v$ has at least $s(v)^{\Omega(1)}$ states. So this approach via standard blowup bounds only yields at most a quadratic in $v$ lower bound on the number of states in a 2FA for any $Q_v$ (even when $Q$ is hard or undecidable).

$k$-Clique is the graph property of containing a complete $k$-vertex subgraph. Recognizing $k$-Clique$_v$ can be done by a 1NFA that first nondeterministically chooses one of $\binom{v}{k}$ different potential $k$-cliques to look for, and then scans the input once, looking for each of the required edges to confirm the clique, and keeping track of these edges using $2^{k(k-1)/2}$ states for each of the different potential cliques. Such a 1NFA has $\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$ states, where $1 \le c_v \le e$. When $k$ is fixed, this is $\Theta(v^k)$ states. Allowing two-way access to the input potentially allows an improvement over this one-way bound. The question is then asking for $k=3$ whether a 2FA can do better than this 1FA upper bound.

Addendum (2017-04-16): see also a related question for deterministic time and a nice answer covering the best known algorithms. My question focuses on nonuniform nondeterministic space. In this context the reduction to matrix multiplication used by the time-efficient algorithms is worse than the brute-force approach.

• I really like this questions! Thank you for sharing it! :) – Michael Wehar Nov 12 '15 at 16:33

It seems to me that triangles can be done by a 2FA $A$ with $O(n^2)$ state (n being the number of vertices).

For $k=3$ the idea is as follows:

1. In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its state
2. In phase 2 it moves to some edge of the form $(i,m)$ or $(m,i)$ and assumes a state of the form $(phase 2,j,m)$
3. In phase 3, it checks that there is some edge $(j,m)$ or $(m,j)$ and assume an accepting state if it finds one.

This can actually almost be done in a left to right fashion (then $A$ might nondeterministically decide to go first for $(j,m)$ or $(m,j)$ in phase 2). However, if the 2nd edge comes in the form $(m,i)$, $A$ needs to first read $i$ and then $m$, i.e., a single left-step is needed here.

This should result in automata with $O(n^{k-1})$ states for $k$-Clique for $k>3$ by first guessing a set $S$ of size $k-3$ and testing, that he nodes of $S$ are pairwise connected by edges and, for each of i,j,m in the above, checking that they have edges to all nodes in $S$.

• I don't see how this is $O(n^2)$? Three vertices $i,j,m$ are being tracked. – András Salamon Nov 22 '15 at 15:16
• Only two at a time. Reading $(i,m)$ in phase 2 is done in two transitions. On reading $i$, $A$ basically goes from (phase 1,i,j) to (phase 1a,i,j) (indicating, it has just seen $i$) and in the next step into (phase 2,j,m). At this point it is done with $i$, as it already saw $(i,j)$ and $(i,m)$ and only $(j,m)$ needs to be checked. – Thomas S Nov 22 '15 at 15:36
• If the number of edges and vertices is roughly the same, then I think this works fine, but the interesting case is when $e = \Omega(v^2)$. In other words, I think your approach uses at least $v \cdot e$ states. – Michael Wehar Nov 22 '15 at 18:19
• I think you are right. If the input is given in a nice format this works. :) – Michael Wehar Nov 22 '15 at 20:04
• @Marzio: no, it says (no, it says deterministic or nondeterministic) – Thomas S Nov 23 '15 at 12:01