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

<p>For $k=3$ the idea is as follows:</p>

<ol>
<li>In phase 1, $A$ chooses some edge $(i,j)$ and stores $(phase 1,i,j)$ in its state</li>
<li>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)$</li>
<li>In phase 3, it checks that there is some edge $(j,m)$ or $(m,j)$ and assume an accepting state if it finds one.</li>
</ol>

<p>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. </p>

<p>This should result in automata with $O(n^{k-1})$ states for $k$-Clique for $k&gt;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$.</p>

CC BY-SA 3.0
2015-11-22T15:16:12.717Z
I don't see how this is $O(n^2)$?  Three vertices $i,j,m$ are being tracked.
András Salamon
CC BY-SA 3.0
2015-11-22T15:36:50.953Z
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
CC BY-SA 3.0
2015-11-22T18:19:36.667Z
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
CC BY-SA 3.0
2015-11-22T18:31:18.717Z
Why? My understanding is that the graph comes as a string over the set of vertices, in which every edge is represented by two successive symbols. The above automaton remembers at most two vertices at any time, plus some additional information about the current phase. That is $O(\nu^2)$ states altogether.
Thomas S
CC BY-SA 3.0
2015-11-22T20:04:58.110Z
I think you are right.  If the input is given in a nice format this works.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-23T07:58:42.007Z
Is it a 2NFA? I thought a bit about the question, too; but I assumed that the OP wanted a 2FA (deterministic)
Marzio De Biasi
CC BY-SA 3.0
2015-11-23T11:59:58.433Z
@András: you seem unconvinced. Where are your doubts? Correctness of the construction? Or size?
Thomas S
CC BY-SA 3.0
2015-11-23T12:01:18.350Z
@Marzio: no, it says (no, it says deterministic or nondeterministic)
Thomas S
CC BY-SA 3.0
2015-11-23T13:24:21.510Z
@ThomasS: your comment showing how to ensure $m$ differs from both $i$ and $j$ via transitions rather than states was the key step to convince me.  I just needed to _unconvince_ myself that this general approach requires a multiplicative increase.
András Salamon
CC BY-SA 3.0
2017-04-17T14:24:46.927Z
Using the Nešetřil and Poljak approach of building an auxiliary graph representing the $O(n^{k/3})$ possible cliques with $k/3$ vertices, it actually seems possible to use this technique to achieve $O(n^{(2/3)k})$ states for fixed $k$ divisible by 3.
András Salamon
CC BY-SA 3.0
2015-11-22T08:21:31.913Z
2015-11-22T15:37:21.353Z
2015-11-22T15:37:21.353Z
Thomas S
<p>In simple form:</p>

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

<h2>Details</h2>

<p>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\}$.</p>

<p>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)$?</p>

<p>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.</p>

<h2>Background</h2>

<p>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.</p>

<p>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).</p>

<p>$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.</p>

<p><em>Addendum (2017-04-16):</em> see also a <a href="https://cs.stackexchange.com/q/18330/5323">related question for deterministic time</a> and a nice <a href="https://cs.stackexchange.com/a/18331/5323">answer covering the best known algorithms</a>.
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.</p>

CC BY-SA 3.0
2015-11-12T16:33:24.267Z
I really like this questions!  Thank you for sharing it!  :)
Michael Wehar
<cc.complexity-theory><ds.algorithms><graph-algorithms><clique>
2FA state complexity of k-Clique?
András Salamon
# 2FA state complexity of k-Clique?

(Asked by: username_0 on 2015-11-12)

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](https://cs.stackexchange.com/q/18330/5323) and a nice [answer covering the best known algorithms](https://cs.stackexchange.com/a/18331/5323).
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.

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, clique
> **Comments:**
> **username_1**: I really like this questions!  Thank you for sharing it!  :)  

---

## 1 answers

### Answer by username_2 on 2015-11-22. Score: 7 | Accepted answer

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$.

> **Comments:**
> **username_0**: I don't see how this is $O(n^2)$?  Three vertices $i,j,m$ are being tracked.  
> **username_2**: 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.  
> **username_1**: 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.  
> **username_2**: Why? My understanding is that the graph comes as a string over the set of vertices, in which every edge is represented by two successive symbols. The above automaton remembers at most two vertices at any time, plus some additional information about the current phase. That is $O(\nu^2)$ states altogether.  
> **username_1**: I think you are right.  If the input is given in a nice format this works.  :)  
> **username_3**: Is it a 2NFA? I thought a bit about the question, too; but I assumed that the OP wanted a 2FA (deterministic)  
> **username_2**: @András: you seem unconvinced. Where are your doubts? Correctness of the construction? Or size?  
> **username_2**: @Marzio: no, it says (no, it says deterministic or nondeterministic)  
> **username_0**: @ThomasS: your comment showing how to ensure $m$ differs from both $i$ and $j$ via transitions rather than states was the key step to convince me.  I just needed to _unconvince_ myself that this general approach requires a multiplicative increase.  
> **username_0**: Using the Nešetřil and Poljak approach of building an auxiliary graph representing the $O(n^{k/3})$ possible cliques with $k/3$ vertices, it actually seems possible to use this technique to achieve $O(n^{(2/3)k})$ states for fixed $k$ divisible by 3.  

---

