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.     

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.     

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 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.     

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.     

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.     

Real Hypercomputation and Continuity

By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hypercomputation allow for the effective evaluation of also discontinuous . More precisely the present work considers the following three super-Turing notions of real function computability: - relativized computation; specifically given oracle access to the Halting Problem or its jump ; - encoding input and/or output y = f(x) in weaker ways also related to the Arithmetic Hierarchy; - nondeterministic computation. It turns out that any computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides the required power to evaluate for instance the discontinuous Heaviside function.     

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      

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.     

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.     

The Complexity of Finding Top-Toda-Equivalence-Class Members

We identify two properties that for P-selective sets are effectively computable. Namely, we show that, for any P-selective set, finding a string that is in a given length's top Toda equivalence class (very informally put, a string from that the set's P-selector function declares to be most likely to belong to the set) is computable, and we show that each P-selective set contains a weakly- -rankable subset.     

An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.     

Morpion Solitaire

We study a popular pencil-and-paper game called morpion solitaire. We present upper and lower bounds for the maximum score attainable for many versions of the game. We also show that, in its most general form, the game is NP-hard and the high score is inapproximable within for any unless P = NP.     

On the Power of Unambiguity in Alternating Machines

Unambiguity in alternating Turing machines has received considerable attention in the context of analyzing globally unique games by Aida et al. [ACRW] and in the design of efficient protocols involving globally unique games by Crasmaru et al. [CGRS]. This paper explores the power of unambiguity in alternating Turing machines in the following settings: 1. We show that unambiguity-based hierarchies-AUPH, UPH, and UPH-are infinite in some relativized world. For each , we construct another relativized world where the unambiguity-based hierarchies collapse so that they have exactly k distinct levels and their k-th levels coincide with PSPACE. These results shed light on the relativized power of the unambiguity-based hierarchies, and parallel the results known for the case of the polynomial hierarchy. 2. For every , we define the bounded-level unambiguous alternating solution class UAS(k) as the class of all sets L for which there exists a polynomial-time alternating Turing machine N, which need not be unambiguous on every input, with at most k alternations such that if and only if x is accepted unambiguously by N. We construct a relativized world where, for all and . 3. Finally, we show that robustly k-level unambiguous alternating polynomial-time Turing machines, i.e., polynomial-time alternating Turing machines that for every oracle have k alternating levels and are unambiguous, accept languages that are computable in , for every oracle A. This generalizes a result of Hartmanis and Hemachandra [HH].     

Element distinctness on one-tape Turing machines: a complete solution

We give a complete characterization of the complexity of the element distinctness problem for n elements of bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time for deterministic machines and nondeterministic solutions that are of time complexity . For elements of logarithmic size , on nondeterministic machines, these results close the gap between the known lower bound and the previous upper bound . Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina, grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung.     

The Hardness of Approximating Spanner Problems

This paper examines a number of variants of the sparse k-spanner problem and presents hardness results concerning their approximability. Previously, it was known that most k-spanner problems are weakly inapproximable (namely, they are NP-hard to approximate with ratio O(log n), for every k ≥ 2) and that the unit-length k-spanner problem for constant stretch requirement k ≥ 5 is strongly inapproximable (namely, it is NP-hard to approximate with ratio ). The results of this paper significantly expand the ranges of hardness for k-spanner problems. In general, strong hardness is shown for a number of k-spanner problems, for certain ranges of the stretch requirement k depending on the particular variant at hand. The problems studied differ by the types of edge weights and lengths used, and they include directed, augmentation and client-server variants. The paper also considers k-spanner problems in which the stretch requirement k is relaxed (e.g., . For these cases, no inapproximability results were known (even for a constant approximation ratio) for any spanner problem. Moreover, some versions of the k-spanner problem are known to enjoy the ratio-degradation property; namely, their complexity decreases exponentially with the inverse of the stretch requirement. So far, no hardness result existed precluding any k-spanner problem from enjoying this property. This paper establishes strong inapproximability results for the case of relaxed stretch requirement (up to , for any ), for a large variety of k-spanner problems. It is also shown that these problems do not enjoy the ratio-degradation property.     

A Note on MODp - MODm Circuits

We give a new proof of recent results of Grolmusz and Tardos on the computing power of constant-depth circuits consisting of a single layer of gates followed by a fixed number of layers of -gates, where p is prime.     

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.