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

Finding multiple induced disjoint paths in general graphs

In an undirected graph, paths P₁,P₂,…,Pk are induced disjoint if each one of them is chordless (i.e., is an induced path) and any two of them have neither common nodes nor adjacent nodes. This paper investigates the Maximum Induced Disjoint Paths (MIDP) problem: in an undirected graph G=(V,E), given k node pairs {s₁,t₁},…,{sk,tk}, connect maximum number of these node pairs via induced disjoint paths. Till now, the only things known about MIDP are: i) it is NP-hard; ii) it is NP-hard even when k=2; iii) it can be solved in polynomial time when k is a fixed constant and the given graph is a directed planar graph (Kobayashi, 2009 [9]). This paper proves that for general k and any ?>0, it is NP-hard to approximate MIDP within m1/2−?, where m=|E|. Two algorithms for MIDP are given by this paper: a greedy algorithm whose approximation ratio is and an on-line algorithm which has a good lower bound.     

Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing

An instance of the k -Steiner forest problem consists of an undirected graph G=(V,E), the edges of which are associated with non-negative costs, and a collection $\mathcal{D}=\{(s_{1},t_{1}),\ldots,(s_{d},t_{d})\}An instance of the k -Steiner forest problem consists of an undirected graph G=(V,E), the edges of which are associated with non-negative costs, and a collection D={(s₁,t₁),?,(s_d,t_d)}\mathcal{D}=\{(s_{1},t_{1}),\ldots,(s_{d},t_{d})\} of distinct pairs of vertices, interchangeably referred to as demands. We say that a forest ℱ⊆G connects a demand (s _i ,t _i ) when it contains an s _i -t _i path. Given a profit k _i for each demand (s _i ,t _i ) and a requirement parameter k, the goal is to find a minimum cost forest that connects a subset of demands whose combined profit is at least k. This problem has recently been studied by Hajiaghayi and Jain (SODA ’06), whose main contribution in this context was to relate the inapproximability of k-Steiner forest to that of the dense k -subgraph problem. However, Hajiaghayi and Jain did not provide any algorithmic result for the respective settings, and posed this objective as an important direction for future research. In this paper, we present the first non-trivial approximation algorithm for the k-Steiner forest problem, which is based on a novel extension of the Lagrangian relaxation technique. Specifically, our algorithm constructs a feasible forest whose cost is within a factor of O(min{n^2/3,?d}·logd)O(\min \{n^{2/3},\sqrt{d}\}\cdot \log d) of optimal, where n is the number of vertices in the input graph and d is the number of demands. We believe that the approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.     

Minimum Cost Source Location Problems with Flow Requirements

In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity requirements λ and two kinds of vertex-connectivity requirements κ and ), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ₊ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d ⁻(v) (resp., d ⁺(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard, which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio of cln D for some constant c, unless every problem in NP has an O(N ^{log log N} )-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions. By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑ _v∈V (d ⁺(v)+d ⁻(v)))-approximable. An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006).     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

On Bounded Leg Shortest Paths Problems

Let V be a set of points in a d-dimensional l _p -metric space. Let s,t∈V and let L be a real number. An L-bounded leg path from s to t is an ordered set of points which connects s to t such that the leg between any two consecutive points in the set has length of at most L. The minimal path among all these paths is the L-bounded leg shortest path from s to t. In the s–t Bounded Leg Shortest Path (stBLSP) problem we are given two points s and t and a real number L, and are required to compute an L-bounded leg shortest path from s to t. In the All-Pairs Bounded Leg Shortest Path (apBLSP) problem we are required to build a data structure that, given any two query points from V and a real number L, outputs the length of the L-bounded leg shortest path (a distance query) or the path itself (a path query). In this paper we obtain the following results:     

Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

Given an undirected multigraph G=(V,E), a family $\mathcal{W}Given an undirected multigraph G=(V,E), a family W\mathcal{W} of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W ? WW\in \mathcal{W} . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k ³+n ²)(p+kn+nlog n)log k+pkn ³log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and p=|W|p=|\mathcal{W}| .     

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.     

Network Design with Edge-Connectivity and Degree Constraints

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.     

Tensor and border rank of certain classes of matrices and the fast evaluation of determinant inverse matrix and eigenvalues

The tensor rankA of the linear spaceA generated by the set of linearly independent matricesA ₁, A₂, …, A_p, is the least integert for wich there existt diadsu ^(r) v ^(r)τ, τ=1,2,...,t, such that . IfA=n+k,k≪n then some computational problems concerning matricesA∈A can be solyed fast. For example the parallel inversion of almost any nonsingular matrixA∈A costs 3 logn+0(log² k) steps with max(n ²+p (n+k), k² n+nk) processors, the evaluation of the determinant ofA can be performed by a parallel algorithm in logp+logn+0 (log² k) parallel steps and by a sequential algorithm inn(1+k ²)+p (n+k)+0 (k ³) multiplications. Analogous results hold to accomplish one step of bisection method, Newton's iterations method and shifted inverse power method applied toA−λB in order to compute the (generalized) eigenvalues provided thatA, B∈A. The same results hold if tensor rank is replaced by border rank. Applications to the case of banded Toeplitz matrices are shown. Dedicated to Professor S. Faedo on his 70th birthday Part of the results of this paper has been presented at the Oberwolfach Conference on Komplexitatstheorie, November 1983     

Computing Bounds for the Star Discrepancy

We observe that the time required to compute the star discrepancy of a sequence of points in a multidimensional unit cube is prohibitive and that the best known upper bounds for the star discrepancy of (t,s)-sequences and (t,m,s)-nets are useful only for sample sizes that grow exponentially with the dimension s. Then, an algorithm to compute upper bounds for the star discrepancy of an arbitrary set of n points in the s-dimensional unit cube is proposed. For an integer k≥1, this algorithm computes in O(nslogk+2 ^s k ^s ) time and O(k ^s ) space a bound that is no better than a function depending on s and k. As an application, we give improved upper bounds for the star discrepancy of some Faure (0,m,s)-nets for s∈{7,…,20}. Received April 20, 1999; revised April 26, 2000     

Finding Edge-Disjoint Paths in Partial k -Trees

For a given graph G and p pairs (s _i ,t _i ) , , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P _i , , connecting s _i and t _i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if . Received January 21, 1977; revised September 19, 1997.     

Parallel Algorithm for Shortest Pairs of Edge-Disjoint Paths

LetG= (V,E) be a directed graph having a nonnegative cost associated with each edge. LetsVbe a special vertex called the source andWVbe a set of other vertices called sinks inG. In this paper, a parallel algorithm is proposed for finding a pair of edge-disjoint paths fromsto each possible sinktWsuch that the sum of the costs of the two paths is minimized. This algorithm has processor and time complexities same as those needed to find shortest paths fromsto all sinkstW, i.e.,n³/lognprocessors andO(log²n) time.     

An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem

Let G=(VG,AG) be a digraph and let S ⊔ T be a bipartition of VG. A bibranching is a subset B⊆AG such that for each node s∈S there exists a directed s–T path in B and, vice versa, for each node t∈T there exists a directed S–t path in B.     

Distributed construction of low-interference spanners

We propose a new low-interference topology for wireless ad hoc networks modeled by Quasi Unit Disk Graphs. Our topology combines two existing structures, the relaxed Greedy structure developed by Damian, Pandit and Pemmaraju, and the low-interference structure developed by Burkhart, von Rickenbach, Wattenhofer and Zollinger. Our main contribution is showing that, when applied on a QUDG G = (V, E), this new structure inherits most properties of the two underlying structures: (i) it is a t(1 + ε) spanner of G, for any t > 1 and ε > 0, (ii) it has optimal interference among all t-spanners for G, (iii) it has O(1) maximum degree, (iv) its total weight is within a factor of O(log Δ) of the weight of a minimum spanning tree for V, where Δ is the aspect ratio of G, and (v) it can be implemented efficiently in O(log Δ + log^* n) rounds of communication. This work was supported by NSF grant CCF-0728909. A preliminary version of this paper, titled “Distributed construction of bounded-degree low-interference spanners of low weight”, appeared in MobiHoc’08.     

Max-Stretch Reduction for Tree Spanners

A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance between any two vertices in T is at most t times their distance in G. If G has a tree t-spanner but not a tree (t−1)-spanner, then G is said to have max-stretch of t. In this paper, we study the Max-Stretch Reduction Problem: for an unweighted graph G=(V,E), find a set of edges not in E originally whose insertion into G can decrease the max-stretch of G. Our results are as follows: (i) For a ring graph, we give a linear-time algorithm which inserts k edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is -hard to decide, for a given graph G and its spanning tree of max-stretch t, whether or not one-edge insertion can decrease the max-stretch to t−1. (iv) Finally, we show that the max-stretch of an arbitrary graph on n vertices can be reduced to s′≥2 by inserting O(n/s′) edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant.     

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 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.