Search

Abstract Let R be a finite set of terminals in a convex metric space (M , d). We give approximation algorithms for problems of finding a minimum size set S ⊆ M of additional points such that the unit-disc graph G [ R ∪ S ] of R ∪ S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + ln ⁡ (Δ − 1) + ϵ , which in R 2 reduces to 1 + ln ⁡ 4 + ϵ < 2.3863 + ϵ ; this improves the ratios ⌊ (Δ + 1) / 2 ⌋ + 1 + ϵ of [19] and 2.5 + ϵ of [7] , respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2 (Δ − 1) of [21]. We also simplify the Δ-approximation of [4] , when G [ R ∪ S ] should be 2-connected. Highlights • We consider connectivity problems on unit-disc graphs in a convex metric space. • Let Δ be the maximum number of independent points in a unit ball. • For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ + 1) / 2 to 1 + ln ⁡ (Δ − 1). • For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2 (Δ − 1) to Δ. [ABSTRACT FROM AUTHOR]

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from π 2 6 − 1 36 + ϵ ≈ 1.617 to 11 7 ≈ 1.571 . Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

Among the vast literature concerning graph drawing and graph theory, linear layouts of graphs have been the subject of intense research over the years, both from a combinatorial and from an algorithmic perspective. In particular, upward book embeddings of directed acyclic graphs (DAGs) form a popular class of linear layouts with notable applications, and the upward book thickness of a DAG is the minimum number of pages required by any of its upward book embeddings. A long-standing conjecture by Heath, Pemmaraju, and Trenk (1999) states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are s t -outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP -hard for any fixed k ≥ 3. We show that the problem, for any k ≥ 5 , remains NP -hard for graphs whose domination number is O (k) , but it is fixed-parameter tractable (FPT) in the vertex cover number. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a unit disk graph corresponding to a given set P of n points in R 2 . We propose a distributed approximation algorithm to find a minimum connected dominating set of G . The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size ( 104 o p t + 52 ) , where o p t is the size of a minimum connected dominating set. The time and message complexities of our algorithm are O ( Δ ) and O ( n ) respectively, where Δ and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities. We also propose a scheduling scheme that obtains O ( Δ ) conflict-free time slots to deal with interference. [ABSTRACT FROM AUTHOR]

The network verification problem is that of establishing the accuracy of a high-level description of its physical topology, by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes to be queried so as to univocally identify the graph. This problem has been studied with respect to different query models, assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman (Leicht and Newman, 2008 [25]) and has subsequently been extremely popular in practice (e.g., see Agarwal and Kempe, 2008 [1], Guimer‘a et al., 2007 [20], Newman, 2006 [28], Newman and Girvan, 2004 [30], Ravasz et al., 2002 [32]). Various heuristic methods are currently employed for finding the optimal solution. However, as observed in Agarwal and Kempe (2008) [1], the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a -inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the NP-hardness results in Brandes et al. (2007) [10]. [Copyright &y& Elsevier]

Abstract: We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph with edge costs, a collection of ordered node pairs, and an integer , find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs . When , we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. (1999) , and for DSF by Chekuri et al. (2008) . Our main result is achieving the first sub-linear in terms of approximation ratio for DSF. Specifically, we give an -approximation scheme for DSF. For k-DSF we give a simple greedy -approximation algorithm. This improves upon the best known ratio by Charikar et al. (1999) , and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 ). This algorithm uses a new structure called start-junction tree which may be of independent interest. [Copyright &y& Elsevier]

Abstract: We consider the problem of computing the permanent of a n by n matrix. For a class of matrices corresponding to constant degree expanders we construct a deterministic polynomial time approximation algorithm to within a multiplicative factor , for arbitrary . This is an improvement over the best known approximation factor obtained in Linial, Samorodnitsky and Wigderson (2000) , though the latter result was established for arbitrary non-negative matrices. Our results use a recently developed deterministic approximation algorithm for counting partial matchings of a graph (Bayati, Gamarnik, Katz, Nair and Tetali (2007) ) and Jerrum–Vazirani method (Jerrum and Vazirani (1996) ) of approximating permanent by near perfect matchings. [ABSTRACT FROM AUTHOR]

Abstract: This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires time and space, where is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires time and space, and the presented approximation scheme requires time and space, where ϵ is the given approximation parameter and M is the length of the longest path in an optimal solution. [ABSTRACT FROM AUTHOR]

Abstract: For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs. [Copyright &y& Elsevier]

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {si,ti} of G, find a minimum set of edges of G whose removal disconnects each si from the corresponding ti. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ∊>0, we present a polynomial-time (1+∊)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut. [Copyright &y& Elsevier]

The main result of this paper is a (2 + &epsiv;)-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n2) time 8-approximation algorithm for this problem and then extend it to an O(n3 + 6/&epsiv;n⌈+ 1⌉m) time (2 + &epsiv;)-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + &epsiv;)-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs. [Copyright &y& Elsevier]