On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines (Q1122982)

This important paper gives an equivalence between the fast simulation of two-tape nondeterministic Turing machines by one-tape nondeterministic Turing machines and the existence of small separators for certain graphs. There are already some known examples where upper bounds on graph properties imply upper bounds on computation time or space, and in restricted settings similarly for lower bounds but this is the first example where the connection is an equivalence. Let \(S: \mathbb N\to\mathbb N\) be a monotone increasing function. An \(n\)-vertex graph \(G=(V,E)\) (directed or undirected) has an \(S\)-separator \(C\) if there is a partition \(V=A\cup B\cup C\), \(| A|,| B| \geq n/3\), \(| C| \leq S(n)\) and \(E\cap (A\times B)=\emptyset.\) A family of graphs is \(S\)-separable if every graph in the family has an \(S\)-separator. A family is separable if it is \(S\)-separable for some \(S(n)=o(n)\). Thus, e.g., the well-known planar separator theorem of Lipton and Tarjan means that the family of planar graphs is \(O(\sqrt{n})\)-separable. A \(k\)-page graph is known to be a graph which consists of \(k\) outerplanar graphs sharing the same spine whose edges are on \(k\) different pages and do not cross there. Obviously 2-page graphs are planar and a result of \textit{M. Yannakakis} [``Four pages are necessary and sufficient for planar graphs'', in: STOC '86, Proc. eighteenth annual ACM symposium on theory of computing. ACM New York, NY, USA, 104--108 (1986), \url{doi:10.1145/12130.12141}] says that page-number 4 is necessary and sufficient for planar graphs. A \(k\)-page graph is a \(k\)-pushdown graph if every vertex has at most one incident edge in each page of the graph (assuming that all edges are oriented from smaller to larger vertices with respect to the ordering of the vertices on the spine). The \(k\)-pushdown graphs were introduced by Pippenger, and, in [\textit{W. J. Paul}, \textit{N. Pippenger}, \textit{E. Szemeredi} and \textit{W. T. Trotter}, ``On determinism versus non-determinism and related problems'', in: Proc. 24th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 429--438 (1983), \url{doi:10.1109/SFCS.1983.39}], it was shown that for multitape Turing machines, nondeterministic linear time is more powerful than deterministic linear time because \(k\)-pushdown graphs have nontrivial segregators (a weakening of the notion of separator). The following problems are open: (1) Is the family of 3-pushdown graphs separable? \((1^*)\) Is the family of k-page separable for any \(k\geq 3\)? These problems are related to a problem from computational complexity: It is well-known that real-time nondeterministic Turing machines with two working tapes and a separate input tape can be simulated by an on-line one-tape nondeterministic Turing machine in time \(O(n^ 2)\) (the simulation). The following problem is open: (2) Can the simulation be done in subquadratic time \(O(n^ 2)?\) The main result of the paper is the equivalence of statements (1), \((1^*)\) and (2). This is used to generalize results of Li and Maass by the quantitative connection between small separators and simulation time. Using the equivalence, almost linear lower bounds for the size of separators of 3-pushdown graphs and an almost quadratic lower bound for simulating two-tape nondeterministic Turing machines by one-tape machines are shown.