Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.     

Efficiently Testing Sparse <Emphasis Type="Italic">GF</Emphasis>(2) Polynomials

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1} ⁿ →{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε.     

On Space Efficient Two Dimensional Range Minimum Data Structures

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m⋅n, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1≤c≤N. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog ² c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(N⋅min {m,log n}) bits with O(1) query time, assuming m≤n. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.     

Exact Algorithms for the Bottleneck Steiner Tree Problem

Given n points, called terminals, in the plane ℝ² and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ² and a spanning tree on the n+k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ², usually, the Euclidean or the L ₁ metric. This problem is known to be NP-hard. In this paper, we study this problem in the L _p metric for any 1≤p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f(k)⋅nlog ² n time for the L ₁ and the L _∞ metrics, and the first exact algorithm for the L _p metric for any fixed rational p with 1<p<∞ whose time complexity is f(k)⋅(n ^k +nlog n), where f(k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L ₂ metric.     

Incremental Medians via Online Bidding

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work of Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance. An incremental algorithm produces a nested sequence of facility sets F ₁⊆F ₂⊆⋅⋅⋅⊆F _n , where |F _k |=k for each k. Such an algorithm is called c -cost-competitive if the cost of each F _k is at most c times the optimum k-median cost. We give improved incremental algorithms for the metric version of this problem: an 8-cost-competitive deterministic algorithm, a 2e≈5.44-cost-competitive randomized algorithm, a (24+ε)-cost-competitive, polynomial-time deterministic algorithm, and a 6e+ε≈16.31-cost-competitive, polynomial-time randomized algorithm. We also consider the competitive ratio with respect to size. An algorithm is s -size-competitive if the cost of each F _k is at most the minimum cost of any set of k facilities, while the size of F _k is at most sk. We show that the optimal size-competitive ratios for this problem, in the deterministic and randomized cases, are 4 and e. For polynomial-time algorithms, we present the first polynomial-time O(log m)-size-approximation algorithm for the offline problem, as well as a polynomial-time O(log m)-size-competitive algorithm for the incremental problem. Our upper bound proofs reduce the incremental medians problem to the following online bidding problem: faced with some unknown threshold T∈ℝ⁺, an algorithm must submit “bids” b∈ℝ⁺ until it submits a bid b≥T, paying the sum of all its bids. We present folklore algorithms for online bidding and prove that they are optimally competitive. We extend some of the above results for incremental medians to approximately metric distance functions and to incremental fractional medians. Finally, we consider a restricted version of the incremental medians problem where k is restricted to one of two given values, for which we give a deterministic algorithm with a nearly optimal cost-competitive ratio. The conference version of this paper appeared in (Chrobak, M., et al. in Lecture Notes in Computer Science, vol. 3887, pp. 311–322, 2006). Research of M. Chrobak supported by NSF Grant CCR-0208856.     

On Metric Clustering to Minimize the Sum of Radii

Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n ^{O(log n⋅log Δ)} time and returns with high probability the optimal solution. Here, Δ is the ratio between the maximum and minimum interpoint distances in the metric space. We also show that the problem is NP-hard, even in metrics induced by weighted planar graphs and in metrics of constant doubling dimension.     

Chordal Deletion is Fixed-Parameter Tractable

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)⋅n ^α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O(n ^k ) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, 2003).     

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgroups but is NP-complete otherwise. When S is a monoid or a regular semigroup, we obtain similar dichotomies for the restricted version of the problem where no variable occurs on the right-hand side of each equation. We stress connections between these problems and constraint satisfaction problems. In particular, for any finite domain D and any finite set of relations Γ over D, we construct a finite semigroup S_Γ such that CSP(Γ) is polynomial-time equivalent to the satifiability problem for systems of equations over S_Γ.     

Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy

In this paper, we present a theoretical study of several shape approximation problems, called shape rectangularization (SR), which arise in intensity-modulated radiation therapy (IMRT). Given a piecewise linear function f such that f(x)≥0 for any x∈ℝ, the SR problems seek an optimal set of constant window functions to approximate f under a certain error criterion, such that the sum of the resulting constant window functions equals (or well approximates) f. A constant window function W(⋅) is defined on an interval I such that W(x) is a fixed value h>0 for any x∈I and is 0 otherwise. A constant window function can be viewed as a rectangle (or a block) geometrically, or as a vector with the consecutive a’s property combinatorially. The SR problems find applications in setup time and beam-on time minimization and dose simplification of the IMRT treatment planning process. We show that the SR problems are APX-Hard, and thus we aim to develop theoretically efficient and provably good quality approximation SR algorithms. Our main contribution is to present algorithms for a key SR problem that achieve approximation ratios better than 2. For the general case, we give a \frac2413\frac{24}{13}-approximation algorithm. For unimodal input curves, we give a \frac97\frac{9}{7}-approximation algorithm. We also consider other variants for which better approximation ratios are possible. We show that an important SR case that has been studied in medical literature can be formulated as a k-MST(k-minimum-spanning-tree) problem on a certain geometric graph G; based on a set of geometric observations and a non-trivial dynamic programming scheme, we are able to compute an optimal k-MST in G efficiently.     

Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

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

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 2^3k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel.     

<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes

An f-sensitivity distance oracle for a weighted undirected graph G(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn ^1+1/k log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log ² n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F).     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

The Perona–Malik Method as an Edge Pruning Algorithm

The Perona–Malik equation (PM), in the continuum limit, is interpreted as the gradient flow for a functional, corresponding to the reconstruction of an image with edges with non-zero thickness. This result is based on an image model (u,Γ) where Γ is an edge set, and u is a slowly-varying function. PM simplifies the image by reducing the jump across each component of Γ, resulting in an automatic edge pruning procedure. The initial-value problem thus defined is well-posed, but practically stable only for small times: it leads to a semi-group with exponential growth. The rigorous analysis gives a mathematical basis for empirical observations, including edge localization and the need to use a small number of iterations. The variational formulation enables an easy comparison with earlier methods.

A General Approach to L（h,k）-Label Interconnection Networks

Given two non-negative integers h and k, an L（h, k）-labeling of a graph G = （V, E） is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L（h, k）-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Beneg, CCC, Trivalent Cayley networks, are all characterized by a similar structure： they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called （l × n）-multistage graphs, containing the most common interconnection topologies, on which we study the L（h, k）-labeling. A general algorithm for L（h, k）-labeling these graphs is presented, and from this method an efficient L（2, 1）-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.     

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

A Fast Algorithm for the Path 2-Packing Problem

Let G be an undirected graph and $\mathcal{T}=\{T_{1},\ldots,T_{k}\}Let G be an undirected graph and T={T₁,?,T_k}\mathcal{T}=\{T_{1},\ldots,T_{k}\} be a collection of disjoint subsets of nodes. Nodes in T ₁∪⋅⋅⋅∪T _k are called terminals, other nodes are called inner. By a T\mathcal{T} -path we mean a path P such that P connects terminals from distinct sets in T\mathcal{T} and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection ℘ of T\mathcal{T} -paths such that at most two paths in ℘ pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn ²), where n and m denote the numbers of nodes and edges in G, respectively.     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.