Search

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [J. Algorithms, 10 (1989), pp. 568{576; J. Combin. Theory, Ser. B, 57 (1993), pp. 196{206], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O( p n)-approximation [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317{322] is known even in bounded-degree graphs. In this paper we give a polynomial-time algorithm which, given a boundeddegree graph of Euler genus g, computes a drawing in a surface of Euler genus gO(1) · logO(1) n. Combined with the upper bound from [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317{322], our result also implies a O(n1/2-α)-approximation for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a uniform fashion, algorithms with approximation ratios of the form OPTO(1) · logO(1) n for several related problems on bounded-degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion. Our algorithm and proof of correctness for the crossing number problem are simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [Proceedings of the ACM Symposium on Theory of Computing, 2011, pp. 303{312], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form poly(OPT; log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown. [ABSTRACT FROM AUTHOR]

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space, where n denotes the length of the text. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. It was open whether these indices can be constructed in both o(n log n) time and o(n log n)- bit working space. This paper breaks the above time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array, which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n logϵ n) time and O(n)-bit working space for any 0 < ϵ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as compressed suffix tree, compressed suffix arrays, and FM-index. We also study the general case where the size of the alphabet Σ is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log ∣Σ∣)-bit working space while running in O(n log log ∣Σ∣) time and O(n(logϵ n + log ∣Σ∣)) time, respectively. These are the first algorithms that achieve o(n log n) time with optimal working space. Moreover, for the special case where log ∣Σ∣ = O((log log n)1-ϵ), we can speed up our suffix array construction algorithm to the optimal O(n). [ABSTRACT FROM AUTHOR]

Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. Recent experiments in self-assembly demonstrate its potential for the parallel creation of a large number of nanostructures, including possibly computers. A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific "glue," and two adjacent tiles will stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional "structures" such as squares and rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called a ribbon: a non-self-crossing rectilinear sequence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. While the problem can be proved undecidable using existing techniques if the ribbon is required to start with a given "seed" tile, our result settles the "unseeded" case, an open problem formerly known as the "unlimited infinite snake problem." The proof is based on a construction, due to R. Robinson, of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the "strong plane-filling property"—a variation of the "plane-filling property" previously defined by J. Kari. A construction of "sandwich" tiles is then used in conjunction with this special tile set, to reduce the well-known undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A "motif" construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. An immediate consequence of our result is the undecidability of the existence of arbitrarily large structures self-assembled using tiles from a given tile set. [ABSTRACT FROM AUTHOR]

In this paper, an optimal linear-time algorithm is presented to solve the haplotype inference problem for pedigree data when there are no recombinations and the pedigree has no mating loops. The approach is based on the use of graphs to capture SNP, Mendelian, and parity constraints of the given pedigree. This representation allows us to capture the constraints as the edges in a graph, rather than as a system of linear equations as in previous approaches. Graph traversals are then used to resolve the parity of these edges, resulting in an optimal running time. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field F, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most d. We obtain the following results: 1. Multilinear case. When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability 1 - o(1), all the depth-3 circuits with two multiplication gates computing the polynomial. The running time of the algorithm is poly(n, ∣F∣). 2. General case. When the circuit is not multilinear we give a quasi-polynomial (in n, d, ∣F∣) time algorithm that outputs, with probability 1-o(1), a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. (greatest common divisor) of the two multiplication gates, the remaining linear functions span a not too small linear space), then we output the depth-3 circuit itself. In the case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. ... Prior to our work there have been several interpolation algorithms for restricted models. However, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates. Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with two queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates. [ABSTRACT FROM AUTHOR]

This paper uses periodic matrix multiplication to improve the time complexities for a number of graph problems. The time for finding an asteroidal triple is reduced from O(nm) to O(n2.82), and the time for finding a star cutset, a two-pair, and a dominating pair is reduced from O(nm) to O(n2.79). It is also shown that each of these problems is at least as hard as one of three basic graph problems for which the best known algorithms run in times O(nm) and O(nα). We note that the fast matrix multiplication algorithms do not seem to be practical because of the enormous constants needed to achieve the asymptotic time bounds. These results are important theoretically for breaking the n³ barrier rather than giving efficient algorithms for a user. [ABSTRACT FROM AUTHOR]

We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(215.13√k + n³). [ABSTRACT FROM AUTHOR]

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. For example, given any "dataflow" type of algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay O(1). This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay. In the case when the network has average link delay dave, our simulation runs in O(√daveT) steps using n/√dave processors, thereby preserving efficiency. We also show how to efficiently simulate an n × n array with unit link delays using slowdown Õ (d&frac23ave) on a two-dimensional array with average link delay dave. Last, we present results for the case in which large local databases are involved in the computation. [ABSTRACT FROM AUTHOR]

Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies. [ABSTRACT FROM AUTHOR]