We prove a $\Omega \left(\sqrt{n}\right)$ lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds. Full article

In the context of combinatorial sampling, the so-called “unranking method” can be seen as a link between a total order over the objects and an effective way to construct an object of given rank. The most classical order used in this context is the lexicographic order, which corresponds to the familiar word ordering in the dictionary. In this article, we propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations, including three algorithms that were introduced decades ago. We start the paper with the introduction of our new algorithm using a new strategy of computations based on the classical factorial numeral system (or factoradics). Then, we present, in a high level, the three other algorithms. For each case, we analyze its time complexity on average, within a uniform framework, and describe its strengths and weaknesses. For about 20 years, such algorithms have been implemented using big integer arithmetic rather than bounded integer arithmetic which makes the cost of computing some coefficients higher than previously stated. We propose improvements for all implementations, which take this fact into account, and we give a detailed complexity analysis, which is validated by an experimental analysis. Finally, we show that, even if the algorithms are based on different strategies, all are doing very similar computations. Lastly, we extend our approach to the unranking of other classical combinatorial objects such as families counted by multinomial coefficients and k-permutations. Full article

We study the algorithmic complexity of solving subtraction games in a fixed dimension with a finite difference set. We prove that there exists a game in this class such that solving the game is EXP-complete and requires time $2^{\Omega \left(n\right)}$, where n is the input size. This bound is optimal up to a polynomial speed-up. The results are based on a construction introduced by Larsson and Wästlund. It relates subtraction games and cellular automata. Full article

We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions ($\mathit{NREs}$) from the usual XPath benchmark to nested word automata ($\mathit{NWAs}$). The determinization of these $\mathit{NWAs}$, however, fails to produce reasonably small automata. In the best case, huge deterministic $\mathit{NWAs}$ are produced after few hours, even for relatively small $\mathit{NREs}$ of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata ($\mathit{SHA}$s) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize $\mathit{SHA}$s, yielding reasonably small deterministic automata for the $\mathit{NREs}$ from the XPath benchmark. The size of deterministic $\mathit{SHA}$s automata can be reduced further by a novel minimization algorithm for a subclass of $\mathit{SHA}$s. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between $\mathit{NWAs}$ and $\mathit{SHA}$s further. Clearly, deterministic $\mathit{SHA}$s can be compiled to deterministic $\mathit{NWAs}$ in linear time, and conversely $\mathit{NWAs}$ can be compiled to nondeterministic $\mathit{SHA}$s in polynomial time. Therefore, we can use $\mathit{SHA}$s as intermediates for determinizing $\mathit{NWAs}$, while avoiding the huge size increase with the usual determinization algorithm for $\mathit{NWAs}$. Notably, the $\mathit{NWAs}$ obtained from the $\mathit{SHA}$s perform bottom-up and left-to-right computations only, but no top-down computations. This $\mathit{NWA}$ behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between $\mathit{SHA}$s and single-entry $\mathit{NWAs}$. In particular, it turns out that the usual determinization algorithm for $\mathit{NWAs}$ behaves well for single-entry $\mathit{NWAs}$, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry $\mathit{NWAs}$ enjoys unique minimization. The subclass of deterministic $\mathit{SHA}$s to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed $\mathit{SHA}$s, we propose schema-based cleaning and symbolic representations based on apply-else rules that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark. Full article

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of $G^{\prime }$ from the cycles of G, where $G^{\prime }$ is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with $n-1$ vertices and $m-2$ edges, $n-1$ vertices and $m-3$ edges, and $n-2$ vertices and $m-3$ edges. Full article