15
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ I really like this questions! Thank you for sharing it! :) $\endgroup$
    – Michael Wehar
    Nov 12, 2015 at 16:33

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ I don't see how this is $O(n^2)$? Three vertices $i,j,m$ are being tracked. $\endgroup$
    – András Salamon
    Nov 22, 2015 at 15:16
  • $\begingroup$ 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. $\endgroup$
    – Thomas S
    Nov 22, 2015 at 15:36
  • $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Nov 22, 2015 at 18:19
  • 1
    $\begingroup$ I think you are right. If the input is given in a nice format this works. :) $\endgroup$
    – Michael Wehar
    Nov 22, 2015 at 20:04
  • 1
    $\begingroup$ @Marzio: no, it says (no, it says deterministic or nondeterministic) $\endgroup$
    – Thomas S
    Nov 23, 2015 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.