Authors:Kazuyuki Narisawa; Hideharu Hiratsuka; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda Pages: 291 - 318 Abstract: Abstract This paper considers enumeration of substring equivalence classes introduced by Blumer et al. (J ACM 34(3):578–595, 1987). These equivalence classes were originally proposed to define a text indexing structure called compact directed acyclic word graphs (CDAWGs). These equivalence classes are also useful for text analysis, since they group together redundant substrings with essentially identical occurrences. In this paper, we present how to enumerate these equivalence classes using only suffix arrays and two auxiliary arrays (rank arrays and lcp arrays), in O(n) time for a given string of length n over the integer alphabet. The proposed method overcomes all the existing algorithms which require \(O(n \log \sigma )\) time, where \(\sigma \) is the alphabet size. Our experimental results show that the proposed method is also practically faster and more memory efficient than the existing ones. Furthermore, we propose an O(n)-time algorithm which constructs the CDAWG of an input string over the integer alphabet. This algorithm is based on the above-mentioned algorithm to enumerate equivalence classes. Our experiments show that the proposed method runs faster than the existing algorithm on large alphabets. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0178-z Issue No:Vol. 79, No. 2 (2017)

Authors:Lukáš Folwarczný; Jiří Sgall Pages: 319 - 339 Abstract: Abstract Caching (also known as paging) is a classical problem concerning page replacement policies in two-level memory systems. General caching is the variant with pages of different sizes and fault costs. The strong NP-hardness of its two important cases, the fault model (each page has unit fault cost) and the bit model (each page has the same fault cost as size) has been established, but under the assumption that there are pages as large as half of the cache size. We prove that this already holds when page sizes are bounded by a small constant: The bit and fault models are strongly NP-complete even when page sizes are limited to \(\{1, 2, 3\}\) . Considering only the decision versions of the problems, general caching is equivalent to the unsplittable flow on a path problem and therefore our results also improve the hardness results about this problem. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0185-0 Issue No:Vol. 79, No. 2 (2017)

Authors:Pankaj K. Agarwal; Sariel Har-Peled; Subhash Suri; Hakan Yıldız; Wuzhou Zhang Pages: 340 - 367 Abstract: Abstract We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time–space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of \(\beta \) -hull that may be a useful representation of uncertain hulls. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0195-y Issue No:Vol. 79, No. 2 (2017)

Authors:Amotz Bar-Noy; Ben Baumer; Dror Rawitz Pages: 368 - 386 Abstract: Abstract We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed over a one-dimensional region. Each sensor has a fixed battery that drains in inverse proportion to a radius that can be set just once, but activated at any time. The problem is to find an assignment of radii and activation times that maximizes the length of time during which the entire region is covered. We show that this problem is NP-hard. In addition, we show that RoundRobin, the algorithm in which the sensors take turns covering the entire region, has a tight approximation guarantee of \(\frac{3}{2}\) . This result also applies to the more general Strip Cover problem, in which each radius may be set finitely-many times. Moreover, we show that the more general class of duty cycle algorithms, in which groups of sensors take turns covering the entire region, can do no better. Finally, we give an \(O(n^2 \log {n})\) -time optimization algorithm for the related Set Radius Strip Cover problem, in which sensors must be activated immediately. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0198-8 Issue No:Vol. 79, No. 2 (2017)

Authors:Gregory Kucherov; Yakov Nekrich Pages: 387 - 400 Abstract: Abstract In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in \(O( P +k)\) time, where P is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008). PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0199-7 Issue No:Vol. 79, No. 2 (2017)

Authors:Michael A. Bekos; Sabine Cornelsen; Luca Grilli; Seok-Hee Hong; Michael Kaufmann Pages: 401 - 427 Abstract: Abstract Fan-planar graphs were recently introduced as a generalization of 1-planar graphs. A graph is fan-planar if it can be embedded in the plane, such that each edge that is crossed more than once, is crossed by a bundle of two or more edges incident to a common vertex. A graph is outer-fan-planar if it has a fan-planar embedding in which every vertex is on the outer face. If, in addition, the insertion of an edge destroys its outer-fan-planarity, then it is maximal outer-fan-planar. In this paper, we present a linear-time algorithm to test whether a given graph is maximal outer-fan-planar. The algorithm can also be employed to produce an outer-fan-planar embedding, if one exists. On the negative side, we show that testing fan-planarity of a graph is NP-complete, for the case where the rotation system (i.e., the cyclic order of the edges around each vertex) is given. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0200-5 Issue No:Vol. 79, No. 2 (2017)

Authors:Leszek Gąsieniec; Christos Levcopoulos; Andrzej Lingas; Rasmus Pagh; Takeshi Tokuyama Pages: 428 - 443 Abstract: Abstract We study the problem of efficiently correcting an erroneous product of two \(n\times n\) matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in \({\tilde{O}}(n^2+kn)\) time and a deterministic \({\tilde{O}}(kn^2)\) -time algorithm for this problem (where the notation \({\tilde{O}}\) suppresses polylogarithmic terms in n and k). PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0202-3 Issue No:Vol. 79, No. 2 (2017)

Authors:Michael A. Bekos; Till Bruckdorfer; Michael Kaufmann; Chrysanthi N. Raftopoulou Pages: 444 - 465 Abstract: Abstract In a book embedding, the vertices of a graph are placed on the “spine” of a book and the edges are assigned to “pages”, so that edges on the same page do not cross. In this paper, we prove that every 1-planar graph (that is, a graph that can be drawn on the plane such that no edge is crossed more than once) admits an embedding in a book with constant number of pages. To the best of our knowledge, the best non-trivial previous upper-bound is \(O(\sqrt{n})\) , where n is the number of vertices of the graph. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0203-2 Issue No:Vol. 79, No. 2 (2017)

Authors:Surender Baswana; Shahbaz Khan Pages: 466 - 483 Abstract: Abstract Depth First Search (DFS) tree is a fundamental data structure for graphs used in solving various algorithmic problems. However, very few results are known for maintaining DFS tree in a dynamic environment—insertion or deletion of edges. We present the first algorithm for maintaining a DFS tree for an undirected graph under insertion of edges. For processing any arbitrary online sequence of edge insertions, this algorithm takes total \(O(n^2)\) time. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0204-1 Issue No:Vol. 79, No. 2 (2017)

Authors:Karl Bringmann; Konstantinos Panagiotou Pages: 484 - 508 Abstract: Abstract We study the fundamental problem of the exact and efficient generation of random values from a finite and discrete probability distribution. Suppose that we are given n distinct events with associated probabilities \(p_1, \dots , p_n\) . First, we consider the problem of sampling from the distribution where the i-th event has probability proportional to \(p_i\) . Second, we study the problem of sampling a subset which includes the i-th event independently with probability \(p_i\) . For both problems we present on two different classes of inputs—sorted and general probabilities—efficient data structures consisting of a preprocessing and a query algorithm. Varying the allotted preprocessing time yields a trade-off between preprocessing and query time, which we prove to be asymptotically optimal everywhere. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0205-0 Issue No:Vol. 79, No. 2 (2017)

Authors:Stacey Jeffery; Frederic Magniez; Ronald de Wolf Pages: 509 - 529 Abstract: Abstract We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically \(\Theta ((n/p)^{2/3})\) p-parallel queries for element distinctness and \(\Theta ((n/p)^{k/(k+1)})\) for \(k\) -sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel query complexity are polynomially related for all total functions f when p is small compared to f’s block sensitivity. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0206-z Issue No:Vol. 79, No. 2 (2017)

Authors:Jean-Daniel Boissonnat; Karthik C. S.; Sébastien Tavenas Pages: 530 - 567 Abstract: The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the ST while retaining its functionalities. In addition, we propose two new data structures called the Maximal Simplex Tree and the Simplex Array List. We analyze the compressed ST, the Maximal Simplex Tree, and the Simplex Array List under various settings. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0207-y Issue No:Vol. 79, No. 2 (2017)

Authors:Antonios Antoniadis; Neal Barcelo; Mario Consuegra; Peter Kling; Michael Nugent; Kirk Pruhs; Michele Scquizzato Pages: 568 - 597 Abstract: Abstract We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal–dual formulation of the problem. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0208-x Issue No:Vol. 79, No. 2 (2017)

Authors:Susanne Albers; Matthias Hellwig Pages: 598 - 623 Abstract: Abstract Makespan minimization on identical parallel machines is a classical scheduling problem. We consider the online scenario where a sequence of n jobs has to be scheduled non-preemptively on m machines so as to minimize the maximum completion time of any job. The best competitive ratio that can be achieved by deterministic online algorithms is in the range [1.88, 1.9201]. Currently no randomized online algorithm with a smaller competitiveness is known, for general m. In this paper we explore the power of job migration, i.e. an online scheduler is allowed to perform a limited number of job reassignments. Migration is a common technique used in theory and practice to balance load in parallel processing environments. As our main result we settle the performance that can be achieved by deterministic online algorithms. We develop an algorithm that is \(\alpha _m\) -competitive, for any \(m\ge 2\) , where \(\alpha _m\) is the solution of a certain equation. For \(m=2\) , \(\alpha _2 = 4/3\) and \(\lim _{m\rightarrow \infty } \alpha _m = W_{-1}(-1/e^2)/(1+ W_{-1}(-1/e^2)) \approx 1.4659\) . Here \(W_{-1}\) is the lower branch of the Lambert W function. For \(m\ge 11\) , the algorithm uses at most 7m migration operations. For smaller m, 8m to 10m operations may be performed. We complement this result by a matching lower bound: No online algorithm that uses o(n) job migrations can achieve a competitive ratio smaller than \(\alpha _m\) . We finally trade performance for migrations. We give a family of algorithms that is c-competitive, for any \(5/3\le c \le 2\) . For \(c= 5/3\) , the strategy uses at most 4m job migrations. For \(c=1.75\) , at most 2.5m migrations are used. PubDate: 2017-10-01 DOI: 10.1007/s00453-016-0209-9 Issue No:Vol. 79, No. 2 (2017)

Authors:Bart M. P. Jansen; Astrid Pieterse Pages: 3 - 28 Abstract: Abstract We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomial-time algorithm that reduces any n-vertex input to an equivalent instance, of an arbitrary problem, with bitsize \(O(n^{2-\varepsilon })\) for \(\varepsilon > 0\) , unless \(\mathsf {NP \subseteq coNP/poly}\) and the polynomial-time hierarchy collapses. These results imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have \(O(k^{2-\varepsilon })\) edges, unless \(\mathsf {NP \subseteq coNP/poly}\) . We also present a positive result and exhibit a non-trivial sparsification algorithm for d-Not-All-Equal-SAT. We give an algorithm that reduces an n-variable input with clauses of size at most d to an equivalent input with \(O(n^{d-1})\) clauses, for any fixed d. Our algorithm is based on a linear-algebraic proof of Lovász that bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex hypergraphs by \(\left( {\begin{array}{c}n\\ d-1\end{array}}\right) \) . We show that our kernel is tight under the assumption that \(\mathsf {NP} \nsubseteq \mathsf {coNP}/\mathsf {poly}\) . PubDate: 2017-09-01 DOI: 10.1007/s00453-016-0189-9 Issue No:Vol. 79, No. 1 (2017)

Authors:Stefan Kratsch; Manuel Sorge Pages: 96 - 138 Abstract: In the Vector Connectivity problem we are given an undirected graph \(G=(V,E)\) , a demand function \(\lambda :V\rightarrow \{0,\ldots ,d\}\) , and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex \(v\in V{\setminus } S\) has at least \(\lambda (v)\) vertex-disjoint paths to S; this abstractly captures questions about placing servers or warehouses relative to demands. The problem is \(\mathsf {NP}\) -hard already for instances with \(d=4\) (Cicalese et al., Theoretical Computer Science ’15), admits a log-factor approximation (Boros et al., Networks ’14), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished ’14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a fixed constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, that is, an efficient reduction to an equivalent instance with \(f(d)k=O(k)\) vertices. For Vector Connectivity we have a factor \(\mathsf {opt} \) -approximation and we can show that it has no kernelization to size polynomial in k or even \(k+d\) unless \(\mathsf {NP} \subseteq \mathsf {coNP}/\mathsf {poly}\) , which shows that \(f(d){\text {poly}}(k)\) is optimal for Vector d-Connectivity. Finally, we give a simple randomized fixed-parameter algorithm for Vector Connectivity with respect to k based on matroid intersection. PubDate: 2017-09-01 DOI: 10.1007/s00453-016-0231-y Issue No:Vol. 79, No. 1 (2017)

Authors:Marthe Bonamy; Łukasz Kowalik; Michał Pilipczuk; Arkadiusz Socała Pages: 159 - 188 Abstract: Abstract In the \(k\) -Leaf Out-Branching and \(k\) -Internal Out-Branching problems we are given a directed graph D with a designated root r and a nonnegative integer k. The question is whether there exists an outbranching rooted at r that has at least k leaves, or at least k internal vertices, respectively. Both these problems have been studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with \(O(k^2)\) vertices are known on general graphs. In this work we show that \(k\) -Leaf Out-Branching admits a kernel with O(k) vertices on \({{\mathcal {H}}}\) -minor-free graphs, for any fixed family of graphs \({{\mathcal {H}}}\) , whereas \(k\) -Internal Out-Branching admits a kernel with O(k) vertices on any graph class of bounded expansion. PubDate: 2017-09-01 DOI: 10.1007/s00453-016-0244-6 Issue No:Vol. 79, No. 1 (2017)

Authors:Ondřej Suchý Pages: 189 - 210 Abstract: Abstract In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by \( T +k\) , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals T is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs. PubDate: 2017-09-01 DOI: 10.1007/s00453-016-0249-1 Issue No:Vol. 79, No. 1 (2017)

Authors:Holger Dell; Eun Jung Kim; Michael Lampis; Valia Mitsou; Tobias Mömke Pages: 230 - 250 Abstract: Abstract We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable–constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types \({\text {AND}}\) , \({\text {OR}}\) , \({\text {PARITY}}\) , and \({\text {MAJORITY}}\) , and with various parameters k, and we attempt to fully classify them into the following three cases: The exact optimum can be computed in \(\textsf {FPT}\) time. It is -hard to compute the exact optimum, but there is a randomized \(\textsf {FPT}\) approximation scheme ( \(\textsf {FPT\text {-}AS}\) ), which computes a \((1{-}\epsilon )\) -approximation in time \(f(k,\epsilon ) \cdot {\text {poly}}(n)\) . There is no \(\textsf {FPT\text {-}AS}\) unless . For the corresponding standard CSPs, we establish \(\textsf {FPT}\) versus -hardness results. PubDate: 2017-09-01 DOI: 10.1007/s00453-017-0310-8 Issue No:Vol. 79, No. 1 (2017)