Abstract: Abstract Bubbles are pairs of internally vertex-disjoint (s, t)-paths in a directed graph, which have many applications in the processing of DNA and RNA data. Listing and analysing all bubbles in a given graph is usually unfeasible in practice, due to the exponential number of bubbles present in real data graphs. In this paper, we propose a notion of bubble generator set, i.e., a polynomial-sized subset of bubbles from which all the other bubbles can be obtained through a suitable application of a specific symmetric difference operator. This set provides a compact representation of the bubble space of a graph. A bubble generator can be useful in practice, since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. We provide a polynomial-time algorithm to decompose any bubble of a graph into the bubbles of such a generator in a tree-like fashion. Finally, we present two applications of the bubble generator on a real RNA-seq dataset. PubDate: 2020-04-01

Abstract: Abstract We study the parameterized and classical complexity of two problems that are concerned with induced paths on three vertices, called \(P_3\)s, in undirected graphs \(G=(V,E)\). In Strong Triadic Closure we aim to label the edges in E as strong and weak such that at most k edges are weak and G contains no induced \(P_3\) with two strong edges. In Cluster Deletion we aim to destroy all induced \(P_3\)s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by \(\ell := E -k\) and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to \(\ell \). Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order at most four. PubDate: 2020-04-01

Abstract: Abstract The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is \(\varOmega (n+m\log m)\), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve \(O( (n+m) \log (n+m) )\) and \(O(n+m\log m\log ^2n)\) time, which are optimal for \(m=\varOmega (n)\) and \(m=O(\frac{n}{\log ^3n})\), respectively. In this paper, we give a construction algorithm with \(O( n + m ( \log m+ \log ^2 n ) )\) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in \(O(\log n)\) time, then the construction time will become the optimal \(O(n+m\log m)\). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in \(O(\log n)\) time. PubDate: 2020-04-01

Abstract: Abstract The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple and fast algorithm is presented that, on a directed or undirected input graph \(G=(V,E)\) with n vertices and m edges, carries out a DFS in \(O(n+m)\) time with \(n+\sum _{v\in V_{\ge 3}}\lceil \log _2(d_v-1)\rceil +O(\log n)\le n+m+O(\log n)\) bits of working memory, where \(d_v\) is the (total) degree of v, for each \(v\in V\), and \(V_{\ge 3}=\{v\in V\mid d_v\ge 3\}\). A slightly more complicated variant of the algorithm works in the same time with at most \(n+({4/5})m+O(\log n)\) bits. It is also shown that a DFS can be carried out in a graph with n vertices and m edges in \(O(n+m+\min \{n,m\}\log ^*\!n)\) time with O(n) bits or in \(O(n+m)\) time with either \(O(n\log \log (4+{m/n}))\) bits or, for arbitrary integer \(k\ge 1\), \(O(n\log ^{(k)}\! n)\) bits. These results among them subsume or improve most earlier results on space-efficient DFS. Some of the new time and space bounds are shown to extend to applications of DFS such as the computation of cut vertices, bridges, biconnected components and 2-edge-connected components in undirected graphs. PubDate: 2020-04-01

Abstract: Abstract Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most \((1+\epsilon )n\) edges (where n is the number of vertices and \(\epsilon \) is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be \(\Omega (\sqrt{n})\). This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is \(\mathrm{poly}(1/\epsilon , h)\) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences. PubDate: 2020-04-01

Abstract: Abstract We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of \(O(n^{5/4})\) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS’14]. For sparse graphs with \(m\ge n^{5/4}\) edges, we get a query complexity of \(O(n^{11/12}m^{1/6}\sqrt{\log n})\), which is better than the one obtained by Le Gall and Nakajima [ISAAC’15] when \(m \ge n^{3/2}\). We also obtain an algorithm with query complexity \({O}(n^{5/6}(m\log n)^{1/6}+d_2\sqrt{n})\) where \(d_2\) is the quadratic mean of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall et al. based on the MNRS quantum walk framework [SICOMP’11]. PubDate: 2020-04-01

Abstract: Abstract The assortment problem in revenue management is the problem of deciding which subset of products to offer to consumers in order to maximise revenue. A simple and natural strategy is to select the best assortment out of all those that are constructed by fixing a threshold revenue \(\pi \) and then choosing all products with revenue at least \(\pi \). This is known as the revenue-ordered assortments strategy. In this paper we study the approximation guarantees provided by revenue-ordered assortments when customers are rational in the following sense: the probability of selecting a specific product from the set being offered cannot increase if the set is enlarged. This rationality assumption, known as regularity, is satisfied by almost all discrete choice models considered in the revenue management and choice theory literature, and in particular by random utility models. The bounds we obtain are tight and improve on recent results in that direction, such as for the Mixed Multinomial Logit model by Rusmevichientong et al. (Prod Oper Manag 23(11):2023–2039, 2014). An appealing feature of our analysis is its simplicity, as it relies only on the regularity condition. We also draw a connection between assortment optimisation and two pricing problems called unit demand envy-free pricing and Stackelberg minimum spanning tree: these problems can be restated as assortment problems under discrete choice models satisfying the regularity condition, and moreover revenue-ordered assortments correspond then to the well-studied uniform pricing heuristic. When specialised to that setting, the general bounds we establish for revenue-ordered assortments match and unify the best known results on uniform pricing. PubDate: 2020-04-01

Abstract: Abstract In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS’17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. PubDate: 2020-04-01

Abstract: Abstract Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online algorithm based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and a strict competitive ratio at most 22.641. We also show that no deterministic algorithm can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is \(n-\omega (1)\), where n is the number of vertices in the graph. PubDate: 2020-04-01

Abstract: Abstract The problem of making a given directed graph strongly connected was well-investigated by Eswaran and Tarjan (SIAM J Comput 5:653–665, 1976). In contrast, the problem of making a given bidirected graph strongly connected has not yet been formulated. In this paper, we consider two related problems: making a given bidirected graph strongly connected with either the minimum cardinality of additional signs or the minimum cardinality of additional arcs. For the former problem, we show a closed formula of the minimum number of additional signs and give a linear-time algorithm for finding an optimal solution. For the latter problem, we give a linear-time algorithm for finding a feasible solution whose size is either equal to or more than the obvious lower bound by one. PubDate: 2020-04-01

Abstract: Abstract In this paper, we consider a class of constrained clustering problems of points in \(\mathbb {R}^{d}\), where d could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called Peeling-and-Enclosing, to iteratively solve two variants of the constrained clustering problems, constrained k-means clustering (k-CMeans) and constrained k-median clustering (k-CMedian). Our framework generalizes Kumar et al.’s (J ACM 57(2):5, 2010) elegant k-means clustering approach from unconstrained data to constrained data, and is based on two standalone geometric techniques, called Simplex Lemma and Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. If k and \(\frac{1}{\epsilon }\) are fixed numbers, our framework generates, in nearly linear time (i.e., \(O(n(\log n)^{k+1}d)\)), \(O((\log n)^{k})\)k-tuple candidates for the k mean or median points, and one of them induces a \((1+\epsilon )\)-approximation for k-CMeans or k-CMedian, where n is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best k-tuple candidate), we obtain a \((1+\epsilon )\)-approximation for each of the constrained clustering problems. Our framework improves considerably the best known results for these problems. We expect that our technique will be applicable to other variants of k-means and k-median clustering problems without locality. PubDate: 2020-04-01

Abstract: Abstract In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a \((0.363-\varepsilon )\)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a \((0.4-\varepsilon )\)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and \(\varepsilon \). PubDate: 2020-04-01

Abstract: Abstract Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. Each sensor can monitor a circular area of specific diameter around its position, called the sensor diameter. Sensors are required to move to final locations so that they can there detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by any sensor (MinMax). We give an \(O(n^{3/2})\) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast the problem is shown to be NP-complete even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in \(O(n \log n)\) time for the Manhattan metric and sensors of identical diameter (homogeneous sensors) in arbitrary initial positions, while it is NP-complete for heterogeneous sensors. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-complete. PubDate: 2020-04-01

Abstract: Abstract We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of \((2+\varepsilon )\) and an amortized update time of \(O(\log n/\varepsilon ^2)\). Our result can be generalized to give a fully dynamic \(O(f^3)\)-approximate algorithm with \(O(f^2)\) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices. PubDate: 2020-04-01

Abstract: Abstract We present an \(O(n\sqrt{\log n})\) time and linear space algorithm for sorting real numbers. This breaks the \(O(n\log n)\) time bound for sorting real numbers which was thought by some researchers to be the lower bound. PubDate: 2020-04-01

Abstract: Abstract We consider a random permutation drawn from the set of permutations of length n that avoid some given set of patterns of length 3. We show that the number of occurrences of another pattern \(\sigma \) has a limit distribution, after suitable scaling. In several cases, the number is asymptotically normal; this contrasts to the cases of permutations avoiding a single pattern of length 3 studied in earlier papers. PubDate: 2020-03-01

Abstract: Abstract In this article, q-regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a linear representation of the sequence; only the eigenvalues of absolute value larger than the joint spectral radius of the matrices contribute terms which grow faster than the error term. The paper has a particular focus on the Fourier coefficients of the periodic fluctuations: they are expressed as residues of the corresponding Dirichlet generating function. This makes it possible to compute them in an efficient way. The asymptotic analysis deals with Mellin–Perron summations and uses two arguments to overcome convergence issues, namely Hölder regularity of the fluctuations together with a pseudo-Tauberian argument. Apart from the very general result, three examples are discussed in more detail:sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input;the amount of esthetic numbers in the first N natural numbers; andthe number of odd entries in the rows of Pascal’s rhombus. For these examples, very precise asymptotic formulæ are presented. In the latter two examples, prior to this analysis only rough estimates were known. PubDate: 2020-03-01

Abstract: Abstract QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort, Insertionsort and Mergesort. Its major advantage is that QuickXsort can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of QuickXsort in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of QuickXsort and X differ only by o(n)-terms. For median-of-k pivot selection for some constant k, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three QuickMergesort uses at most \(n \lg n - 0.8358n + {\mathcal {O}}(\log n)\) comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to \(n \lg n - 1.4112n + o(n)\) for a remaining gap of only 0.0315n comparisons to the known lower bound (while using only \({\mathcal {O}}(\log n)\) additional space and \({\mathcal {O}}(n\log n)\) time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s Introsort. PubDate: 2020-03-01