Quadratic Kernelization for Convex Recoloring of Trees

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) ^k n ⁴). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k ²).     

Convex recolorings of strings and trees: Definitions, hardness results and algorithms

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one, and what are the convex colorings which are “closest” to it. In this paper we study a natural definition of this distance—the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number cost(v,d). Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree.     

A PTAS for Cutting Out Polygons with Lines

We present a simple O(m+n ⁶/ε ¹²) time (1+ε)-approximation algorithm for finding a minimum-cost sequence of lines to cut a convex n-gon out of a convex m-gon.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R ^′ ⊊ R⊆V with |R−R ^′|≥2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ^′. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem.     

Steiner Minimal Trees with One Polygonal Obstacle

In this paper we study the Steiner minimal tree T problem for a point set Z with cardinality n and one polygonal obstacle ω in the Euclidean plane. We assume ω touches only one convex path in T that joins two terminals and that the number of extreme points of the obstacle is k . If all degree 2 vertices are omitted, then the topology of T is called the primitive topology of T . Given a full primitive topology along with ω convex, we prove that T can be determined in O(n ² +nlog ² k) time. Further, if ω is nonconvex, we then show that O(n ² +nklog k) time is required. Received April 16, 1996; revised August 18, 1997.     

Fast Dynamic Transitive Closure with Lookahead

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n ^{ω(1,1,ε)−ε} ) time given a lookahead of n ^ε operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n ^ε matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n ^2−ε ) time, whereas for ε=1 the time is O(n ^ω−1). This is essentially optimal as it implies an O(n ^ω ) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n^\fracw2)O(n^{\frac{\omega}{2}}) time to process n^\frac12n^{\frac{1}{2}} operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.     

A generalized distribution model for random recursive trees

 A random tree T _n of order n is constructed by choosing in a random tree T _n-1 of order n−1 a vertex at random and connecting it to a new vertex labeled n. In the usual constraint we assume that the n−1 vertices of T _n-1 are equally likely to be chosen. We introduce and research a more general case in which a distribution of choosing vertices is defined by a sequence α₁, α₂, …. Received: 14 February 1995/2 January 1996     

Lattice constants matricial equations for conversion matrices

In this paper we proof a theorem concerning lattice constants and hence three matricial equations for conversion matricesR: if H=Δ^RT we have: i)H ³ =I; ii) H^T Σ H= Σ; iii)(DH) ² =I; where Δ,D, and ε are known when we can enumerate all non-isomorphic graphs withn vertices, we know (for Δ and ε) their edge-number and (for ε) the order of their automorphism group.     

Approximating Buy-at-Bulk and Shallow-Light <Emphasis Type="Italic">k</Emphasis>-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ⁺ and a distance cost r:E→ℝ⁺. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ _e∈H b(e)+∑ _t∈T−s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log ³ n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log ² n),O(log ⁴ n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 677–686, 2006). A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006. M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02. M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

Minimum Weight Convex Steiner Partitions

New tight bounds are presented on the minimum length of planar straight line graphs connecting n given points in the plane and having convex faces. Specifically, we show that the minimum length of a convex Steiner partition for n points in the plane is at most O(log n/log log n) times longer than a Euclidean minimum spanning tree (EMST), and this bound is the best possible. Without Steiner points, the corresponding bound is known to be Θ(log n), attained for n vertices of a pseudo-triangle. We also show that the minimum length convex Steiner partition of n points along a pseudo-triangle is at most O(log log n) times longer than an EMST, and this bound is also the best possible. Our methods are constructive and lead to O(nlog n) time algorithms for computing convex Steiner partitions having O(n) Steiner points and weight within the above worst-case bounds in both cases.     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

An $\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of Graphs

We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. 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 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 the weights of the cycles is minimum is called a minimum cycle basis of G. Minimum cycle basis are useful in a number of contexts, e.g. the analysis of electrical networks and structural engineering. The previous best algorithm for computing a minimum cycle basis has running time O(m ^ω n), where ω is the best exponent of matrix multiplication. It is presently known that ω<2.376. We exhibit an O(m ² n+mn ²log n) algorithm. When the edge weights are integers, we have an O(m ² n) algorithm. For unweighted graphs which are reasonably dense, our algorithm runs in O(m ^ω ) time. For any ε>0, we also design an 1+ε approximation algorithm. The running time of this algorithm is O((m ^ω /ε)log (W/ε)) for reasonably dense graphs, where W is the largest edge weight. A preliminary version of this paper appeared in Kavitha et al. (31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 846–857, 2004). T. Kavitha and K.E. Paluch were in Max-Planck-Institut für Informatik, Saarbrücken, Germany, while this work was done.     

Approximating the minmax rooted-tree cover in a tree

Given an edge-weighted rooted tree T and a positive integer p (?n), where n is the number of vertices in T, we cover all vertices in T by a set of p subtrees each of which contains the root r of T. The minmax rooted-tree cover problem asks to find such a set of p subtrees so as to minimize the maximum weight of the subtrees in the set. In this paper, we propose an O(n) time (2+ε)-approximation algorithm to the problem, where ε>0 is a prescribed constant.     

The Bit Complexity of Distributed Sorting

We study the bit complexity of the sorting problem for asynchronous distributed systems. We show that for every network with a tree topology T, every sorting algorithm must send at least bits in the worst case, where is the set of possible initial values, and Δ _T is the sum of distances from all the vertices to a median of the tree. In addition, we present an algorithm that sends at most bits for such trees. These bounds are tight if either L=Ω(N ^1+ε ) or Δ _T =Ω(N ² ). We also present results regarding average distributions. These results suggest that sorting is an inherently nondistributive problem, since it requires an amount of information transfer that is equal to the concentration of all the data in a single processor, which then distributes the final results to the whole network. The importance of bit complexity—as opposed to message complexity—stems also from the fact that, in the lower bound discussion, no assumptions are made as to the nature of the algorithm. Received May 2, 1994; revised December 22, 1995.     

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R ⁺, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k _u . A solution consists of a function x:V→ℕ₀ and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x _u k _u . Our objective is to find a cover that minimizes ∑ _v∈V x _v w _v . This is the first 2-approximation for the problem and also runs in O(nlog n+m) time. Research supported by NSF Awards CCR 0113192 and CCF 0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

On the number of transitive digraphs withn labeled vertices andk arcs

A computer determination of the numberT _n,k of transitive digraphs onn labeled vertices andk arcs is obtained for 2≤n≤6,0 ≤k≤n ²-n. Furthermore some formulae are given for determiningT _n,k, ∇n for extremal values ofk (namely, 0≤k≤6 andn ² -3n+4≤k≤n ²-n). Work carried out at Fondazione Ugo Bordoni under the agreements between Fondazione Ugo Bordoni and the Istituto Superiore P. T.