In simple form:Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?DetailsOf 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.BackgroundA 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.
2FA state complexity of k-Clique?
cc.complexity theory;ds.algorithms;graph algorithms;clique
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:In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its stateIn 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)$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$.