Random Geometric Graph Diameter in the Unit Ball

The unit ball random geometric graph has as its vertices n points distributed independently and uniformly in the unit ball in , with two vertices adjacent if and only if their ℓ_p-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper and lower bounds for the graph diameter of G. Specifically, almost always, , where is the ℓ_p-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.     

Convex Drawings of 3-Connected Plane Graphs

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size The parameter depends on the Schnyder wood used for the drawing. This parameter is in the range The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to For a random 3-connected plane graph, tests show that the expected size of the drawing is      

The Expected Size of the Rule k Dominating Set

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an square. We show that if and then for both versions of Rule k, the expected size of the Rule k dominating set is as It follows that, for in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.     

Motorcycle Graphs and Straight Skeletons

We present a new algorithm to compute motorcycle graphs. It runs in time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon. For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton computation to a motorcycle graph computation in expected time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n vertices, among which r are reflex vertices, in expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in expected time.     

Algorithms for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph which has a homogeneous set. In 2001 Tang et al. published an all-fast algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at the former determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at We give as well two even faster randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.     

Approximation Algorithms for the Unsplittable Flow Problem

We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an approximation ratio for UFP, where n is the number of vertices, is the maximum degree, and is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an approximation. For certain strong constant-degree expanders considered by we obtain an approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem

For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered isomorphic variants of MAST. Our algorithms run in time , , , and , respectively, where n is the number of leaf labels and k is the number of input trees.     

GCD of Random Linear Combinations

We show that for arbitrary positive integers with probability the gcd of two linear combinations of these integers with rather small random integer coefficients coincides with This naturally leads to a probabilistic algorithm for computing the gcd of several integers, with probability via just one gcd of two numbers with about the same size as the initial data (namely the above linear combinations). This algorithm can be repeated to achieve any desired confidence level.     

The Effect of Faults on Network Expansion

We study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain and still contain a large (i.e., linear-sized) connected component with approximately the same expansion as the original fault-free network. We use a pruning technique that culls away those parts of the faulty network that have poor expansion. The faults may occur at random or be caused by an adversary. Our techniques apply in either case. In the adversarial setting we prove that for every network with expansion a large connected component with basically the same expansion as the original network exists for up to a constant times faults. We show this result is tight in the sense that every graph G of size n and uniform expansion can be broken into components of size o(n) with faults. Unlike the adversarial case, the expansion of a graph gives a very weak bound on its resilience to random faults. While it is the case, as before, that there are networks of uniform expansion that are not resilient against a fault probability of a constant times it is also observed that there are networks of uniform expansion that are resilient against a constant fault probability. Thus, we introduce a different parameter, called the span of a graph, which gives us a more precise handle on the maximum fault probability. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.     

Exact Algorithms for Graph Homomorphisms

Graph homomorphism, also called H-coloring, is a natural generalization of graph coloring: There is a homomorphism from a graph G to a complete graph on k vertices if and only if G is k-colorable. During recent years the topic of exact (exponential-time) algorithms for NP-hard problems in general, and for graph coloring in particular, has led to extensive research. Consequently, it is natural to ask how the techniques developed for exact graph coloring algorithms can be extended to graph homomorphisms. By the celebrated result of Hell and Nesetril, for each fixed simple graph H, deciding whether a given simple graph G has a homomorphism to H is polynomial-time solvable if H is a bipartite graph, and NP-complete otherwise. The case where H is the cycle of length 5, is the first NP-hard case different from graph coloring. We show that for an odd integer , whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time . We extend the results obtained for cycles, which are graphs of treewidth two, to graphs of bounded treewidth as follows: if H is of treewidth at most t, then whether input graph G with n vertices is homomorphic to H can be decided in time .     

Algorithms to Compute Minimum Cycle Basis in Directed Graphs

We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. This paper presents an algorithm, which is the first polynomial-time algorithm for computing a minimum cycle basis in G. We then improve it to an algorithm. The problem of computing a minimum cycle basis in an undirected graph has been well studied. In this problem a {0,1} incidence vector is associated with each cycle and the vector space over generated by these vectors is the cycle space of the graph. There are directed graphs in which the minimum cycle basis has lower weight than any cycle basis of the underlying undirected graph. Hence algorithms for computing a minimum cycle basis in an undirected graph cannot be used as black boxes to solve the problem in directed graphs.     

Quantum Complexity of Testing Group Commutativity

We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in . The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of , we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.     

Faster Deterministic Communication in Radio Networks

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log ³ n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log ² n) time broadcasting schedule by Kowalski and Pelc. A preliminary version of this paper appeared in the proceedings of ISAAC’06. F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported by the Research Council of Norway through the SPECTRUM project.     

A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths

We present an -time algorithm for the All Pairs Shortest Paths (APSP) problem for directed graphs with real edge lengths. This slightly improves previous algorithms for the problem obtained by Fredman, Dobosiewicz, Han, and Takaoka.     

Finding Pathway Structures in Protein Interaction Networks

The increased availability of data describing biological interactions provides important clues on how complex chains of genes and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find an optimal path structure in time and space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure. Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures, we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity by applying it to protein interaction networks in the DIP database.     

Improved Approximate String Matching Using Compressed Suffix Data Structures

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an -bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog ² n) bits. The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log  ^ε n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| ^k m ^k (k+log log n)+occ) and O(log  ^ε n(|A| ^k m ^k (k+log log n)+occ)) time using an -bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by for the -bit space data structure.     

Fast 3-coloring Triangle-Free Planar Graphs

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(nlogn)\mathcal{O}(n\log n) .     

On the Crossing Number of Complete Graphs

Let (G) denote the rectilinear crossing number of a graph G. We determine (K₁₁)=102 and (K₁₂)=153. Despite the remarkable hunt for crossing numbers of the complete graph K_n – initiated by R. Guy in the 1960s – these quantities have been unknown forn>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11. Based on these findings, we establish a new upper bound on (K_n) for general n. The bound stems from a novel construction of drawings of K_n with few crossings.     

Algorithms for Graphs Embeddable with Few Crossings per Edge

We consider graphs that can be embedded on a surface of bounded genus such that each edge has a bounded number of crossings. We prove that many optimization problems, including maximum independent set, minimum vertex cover, minimum dominating set and many others, admit polynomial time approximation schemes when restricted to such graphs. This extends previous results by Baker and Eppstein to a much broader class of graphs. We also prove that for the considered class of graphs, there are balanced separators of size where n is a number of vertices in the graph. On the negative side, we prove that it is intractable to recognize the graphs embeddable in the plane with at most one crossing per edge.