Abstract For n-vertex graphs with treewidth $$k = O(n^{1/2-\epsilon })$$ k = O ( n 1 / 2 - ϵ ) and an arbitrary $$\epsilon >0$$ ϵ > 0 , we present a word-RAM algorithm to compute vertex separators using only O(n) bits of working memory. As an application of our algorithm, we give an O(1)-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in $$c^k n (\log \log n) \log ^* n$$ c k n ( log log n ) log ∗ n time using O(n) bits for some constant $$c > 0$$ c > 0 . Together with the result of Banerjee et al. (Proceedings of 21st international conference on computing and combinatorics (COCOON 2015). LNCS, vol 9198, Springer, pp 349–360, 2015. https://doi.org/10.1007/978-3-319-21398-9_28 ) we are able to compute a solution for all monadic-second-order problems (MSO) with $$O(n + \tau (k) \cdot p (\log _{p} n) \log n)$$ O ( n + τ ( k ) · p ( log p n ) log n ) bits in $$O(\tau (k) \cdot n^{2 + (2/\log p)})$$ O ( τ ( k ) · n 2 + ( 2 / log p ) ) time where k is the treewidth of the given graph, p is some arbitrary parameter with $$2 \le p \le n$$ 2 ≤ p ≤ n and $$\tau $$ τ is some function depending on the MSO formula. We finally use the tree decomposition obtained by our algorithm to solve Vertex Cover, Independent Set, Dominating Set, MaxCut and q-Coloring by using polynomial time and O(n) bits as long as the treewidth of the graph is smaller than $$c' \log n$$ c ′ log n for some problem dependent constant $$0< c' < 1$$ 0 < c ′ < 1 .

A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.

A c-color choice dictionary of size n in N is a fundamental data structure in the development of space-efficient algorithms that stores the colors of n elements and that supports operations to get and change the color of an element as well as an operation choice that returns an arbitrary element of that color. For an integer f>0 and a constant c=2^f, we present a word-RAM algorithm for a c-color choice dictionary of size n that supports all operations above in constant time and uses only nf+1 bits, which is optimal if all operations have to run in o(n/w) time where w is the word size. In addition, we extend our choice dictionary by an operation union without using more space.

Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data structure is not initialized, i.e., there is plenty of unused space allocated for the data structure. We present a general framework to store temporarily extra buffers between the real data so that the data can be processed immediately, stored first in the buffers, and then moved into the real data structure after finishing the tables. As an application, we apply our framework to Dodis, Patrascu, and Thorup's data structure (STOC 2010) that emulates c-ary memory and to Farzan and Munro's succinct encoding of arbitrary graphs (TCS 2013). We also use our framework to present an in-place dynamical initializable array.