Search

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R , we define G ∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R ∈ R , the graph G ∩ R is a t-spanner for K (P) ∩ R , where K (P) is the complete geometric graph on P. For any set P of n points and any constant ε > 0 , we prove that P admits local (1 + ε) -spanners of sizes O (n log 6 n) and O (n log n) w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local (1 + ε) -spanners with O(n) edges and O (n log 2 n) edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The vertices in the subset T are called terminals and the other vertices are called Steiner vertices. Recently, Pilipczuk et al. (55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, 2014) gave a polynomial kernel for Steiner Tree in planar graphs and graphs of bounded genus, when parameterized by $$|T|+k$$ , the total number of vertices in the constructed subgraph. In this paper we present several polynomial time applicable reduction rules for Steiner Tree in graphs of bounded genus. In an instance reduced with respect to the presented reduction rules, the number of terminals | T| is at most cubic in the number of other vertices k in the subgraph. Hence, using and improving the result of Pilipczuk et al., we give a polynomial kernel for Steiner Tree in graphs of bounded genus for the parameterization by the number k of Steiner vertices in the solution. We give better bounds for Steiner Tree in planar graphs. [ABSTRACT FROM AUTHOR]

We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant $$l$$ , outputs a directed Steiner tree of cost no larger than $$2(l-1)(\ln n+1)$$ times the cost of any $$l$$ -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most $$l$$ arcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of $$O(\log n)$$ , and (2) the tree cover problem on directed graphs can also be approximated within a factor of $$O(\log n)$$ . [ABSTRACT FROM AUTHOR]

We study the problem of finding small s- t separators that induce graphs having certain properties. It is known that finding a minimum clique s- t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, ), while for example the problems of finding a minimum s- t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, ). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: In order to prove (1), we show that the natural c-connected generalization of the well-known Steiner Tree problem is FPT for c=2 and W[1]-hard for any c≥3. [ABSTRACT FROM AUTHOR]

We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An element means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is APX-hard when there are only three terminal nodes, thus answering an open question. Our main focus is on the special case when the graph is planar. We show that the problem of finding two element-disjoint Steiner trees in a planar graph is NP-hard. Similarly, the problem of finding two edge-disjoint Steiner trees in a planar graph is NP-hard. We design an algorithm for planar graphs that achieves an approximation guarantee close to 2. In fact, given a planar graph that is k element-connected on the terminals ( k is an upper bound on the number of element-disjoint Steiner trees), the algorithm returns $\lfloor\frac{k}{2} \rfloor-1$ element-disjoint Steiner trees. Using this algorithm, we get an approximation algorithm for the edge-disjoint version of the problem on planar graphs that improves on the previous approximation guarantees. We also show that the natural LP relaxation of the planar problem has an integrality ratio approaching 2. [ABSTRACT FROM AUTHOR]

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log nlog k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ ε. [ABSTRACT FROM AUTHOR]

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 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 metric for any fixed rational p with 1< p<∞ whose time complexity is f( k)⋅( n+ 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract  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 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 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. [ABSTRACT FROM AUTHOR]

Abstract   Every rectilinear Steiner tree problem admits an optimal tree T * which is composed of tree stars. Moreover, the currently fastest algorithms for the rectilinear Steiner tree problem proceed by composing an optimum tree T * from tree star components in the cheapest way. The efficiency of such algorithms depends heavily on the number of tree stars (candidate components). F��meier and Kaufmann (Algorithmica 26, 68–99, 2000) showed that any problem instance with k terminals has a number of tree stars in between 1.32 k and 1.38 k (modulo polynomial factors) in the worst case. We determine the exact bound O *(ρ k ) where ρ≈1.357 and mention some consequences of this result. [ABSTRACT FROM AUTHOR]

The aim of this note is to clear some background information and references to readers interested in understanding the current status of the Gilbert-Pollak Conjecture, in particular, to show that A.O. Ivanov and A.A. Tuzhilin were the first who understood the nature of the real gaps in Du-Hwang proof, what has reflected in their publications starting from 2002. [ABSTRACT FROM AUTHOR]