Search

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an ϵ-spectral sparsifier in sublinear time Õ(√mn/ϵ). This contrasts with the optimal classical complexity Õ(m). We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut. [ABSTRACT FROM AUTHOR]

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for all positive integers a, b and a graph G, if the treedepth of G is at least Cab, then the treewidth of G is at least a or G contains a subcubic (i.e., of maximum degree at most 3) tree of treedepth at least b as a subgraph. As a direct corollary, we obtain that every graph of treedepth Omega (k3) either is of treewidth at least k, contains a subdivision of full binary tree of depth k, or contains a path of length 2k. This improves the bound of Omega (k5 log2 k) of Kawarabayashi and Rossman [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph G of treedepth k and treewidth t, one can in polynomial time compute a treedepth decomposition of G of width scrO (kt log3/2 t). This improves upon a bound of scrO (kt2 log t) stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth d contains a subcubic subtree of treedepth at least d cdot log3((1 + surd 5)/2). [ABSTRACT FROM AUTHOR]

We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length 4 in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm. [ABSTRACT FROM AUTHOR]

In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polyn omials C and show that if p € C and there is a disk D centered at zero in the complex plane such that p(G) does not vanish on D for all bounded degree graphs G, then for each z in the interior of D there exists a deterministic polynomialtime approximation algorithm for evaluating p(G) at z. This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectur es. Our work builds on a recent line of work initiated by Barvinok [Found. Comput. Math., 16 (20 16), pp. 329--342; Theory Comput., 11 (2015), pp. 339--355; Computing the Partition Function of a Polynomial on the Boolean Cube, 2015; Discrete Anal., 2 (2017), 34pp], which provides a new algorithmic approach besides the existing Markov chain Monte Carlo method and the correlation decay method for these types of problems. [ABSTRACT FROM AUTHOR]

We investigate the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, includes planar graphs, and in particular is a subset of the family of graphs that have polynomial expansion. We present efficient (1+ε)-approximation algorithms for polynomial expansion graphs for unweighted Independent Set, Set Cover, and Dominating Set problems, among others, and these results seem to be new. Naturally, PTASs for these problems are known for subclasses of this graph family. These results have immediate applications in the geometric domain. For example, the new algorithms yield the only PTAS known for covering points by fat triangles (that are shallow). We also prove corresponding hardness of approximation for some of these optimization problems, characterizing their intractability with respect to density. For example, we show that there is no PTAS for covering points by fat triangles if they are not shallow, thus matching our PTAS for this problem with respect to depth. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries, and neighbor queries. We show that for any given approximation parameter 0 < ε < 1, the algorithm provides an estimate t such that, with high constant probability, (1 - ε). t < t < (1 + ε). t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is ... poly(log n, 1/ε), where n is the number of vertices in the graph and m is the number of edges. The expected running time of the algorithm is ... poly(log n, 1/ε). We also prove that ... queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to the dependence on poly (log n, 1/ε). [ABSTRACT FROM AUTHOR]

In this note, we prove that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s' < s, are < δ-hyperbolic with δ = O(s²). We also show that the dependency between S and s is linear if s - s' = Ω(s) and G obeys a slightly stronger condition. This solves an open question from the paper [J. Chalopin et al., SIAM J. Discrete Math., 25 (2011), pp. 333-359]. Since any δ-hyperbolic graph is cop-win for s = 2r and s' = r + 2δ for any r > 0, this establishes a new--game-theoretical--characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between δ and s is linear for any s' < s. Using these results, we describe a simple constant-factor approximation of the hyperbolicity δ of a graph on n vertices in O(n²) time when the graph is given by its distance matrix. [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]

We present an approximation algorithm for the shortest descending path problem. Given a source s and a destination t on a terrain, a shortest descending path from s to t is a path of minimum Euclidean length on the terrain subject to the constraint that the height decreases monotonically as we traverse that path from s to t. Given any ε ∈ (0, 1), our algorithm returns in O(n4 log(n/ε)) time a descending path of length at most 1 + ε times the optimum. This is the first algorithm whose running time is polynomial in n and log(1/ε) and independent of the terrain geometry. [ABSTRACT FROM AUTHOR]

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the k parts need to be of equal size, and where they must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k) approximation algorithm. This improves over an O(log² n) approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an O(1) approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph G and the goal is to find a nonempty set S ⊆ V of size |S| ≤ ρn with minimum edge expansion. We give an O(√log n log (1/ρ)) bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of O(1) for graphs that exclude any fixed minor. [ABSTRACT FROM AUTHOR]

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers. [ABSTRACT FROM AUTHOR]

Given a directed graph G = (V, E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were implicitly studied in the context of circuit complexity, data structures, property testing, and access control, and properties of these spanners have been rediscovered over the span of 20 years. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners. We initiate the study of approximability of the size of the sparsest k-TC-spanner of a given directed graph. We completely resolve the approximability of 2-TC-spanners, showing that it is Θ(log n) unless P = NP. For k > 2, we present a polynomial time algorithm that finds a k-TC-spanner with size within O((n log n)1-1/k) of the optimum. Our techniques also yield algorithms with the first nontrivial approximation ratio for well-studied problems on directed spanners when k > 3: DIRECTED k-SPANNER, CLIENT/SERVER DIRECTED k-SPANNER, and k-DIAMETER SPANNING SUBGRAPH. For constant k ≥ 3, we show that the size of the sparsest k-TC-spanner is hard to approximate within a factor of 2log1-∈ n for any ε ∈ (0, 1) unless NP ⊆ DTIME(npolylog n). Finally, we study the size of the sparsest k-TC-spanners for H-minor-free graph families. Combining our constructions with our insight that 2-TC-spanners can be used for designing property testers, we obtain a monotonicity tester with O(log² n/ε) queries for any poset whose transitive reduction, when viewed as an undirected graph, is free of a fixed minor. Previously, the best upper bound on the query complexity for such graphs was O(√n/ε). [ABSTRACT FROM AUTHOR]

Consider the edge-connectivity survivable network design problem (SNDP): given a graph G = (V, E) with edge-costs, and edge-connectivity requirements rij ∈ Z≥0 for every pair of vertices i, j ∈ V, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting. In this paper, we give a randomized Õ(rmax log³ n)-competitive online algorithm for this edge-connectivity network design problem that runs in time O(mrmax ), where rmax = maxij rij. Our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected subgraphs) as an intermediate step to get algorithms for higher connectivity. As a consequence of using these random embeddings, our algorithms are competitive only against oblivious adversaries. Our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rent-or-buy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. If we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., the triangle inequality is satisfied), we improve on our results to give an O(log n)-competitive deterministic online algorithm for the rooted version of the problem, and constant-factor approximation algorithms for the rent-or-buy and stochastic variants of SNDP. [ABSTRACT FROM AUTHOR]

We present an O(log² k)-approximation algorithm for the problem of finding a k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in an input graph, and k is a connectivity requirement. Our algorithm is the first that achieves a polylog-arithmic approximation ratio for all values of k and n, and it works for both directed and undirected graphs. As in previous works, we use the Frank-Tardos algorithm for finding k-outconnected subgraphs as a subroutine. However, with our structural lemmas, we are able to show that we need only partial solutions returned by the Frank-Tardos algorithm; thus, we can avoid paying the whole cost of an optimal solution every time the algorithm is applied. [ABSTRACT FROM AUTHOR]

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either k vertex-disjoint directed circuits or a set of at most f(k) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer k and a vertex subset S, whose size may not depend on k, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of k) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately k in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer k. [ABSTRACT FROM AUTHOR]

We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products P based on a set of customer samples C. We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor O (logepsilon|C|) for some constant ∈ > 0, unless NP ⊆DTIME(nO(log log n)), thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove in approximability within O(l∈), being an upper bound on the number of nonzero values per customer, and O(|P|∈) under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within O(|P|∈) assuming NP ⊈ ∩δ>0 BPTIME Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.. These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model. [ABSTRACT FROM AUTHOR]

Submodular maximization generalizes many important problems including Max Cut in directed and undirected graphs and hypergraphs, certain constraint satisfaction problems, and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard. In this paper, we design the first constant-factor approximation algorithms for maximizing nonnegative (non-monotone) submodular functions. In particular, we give a deterministic local-search 1/3-approximation and a randomized 2/5-approximation algorithm for maximizing nonnegative submodular functions. We also show that a uniformly random set gives a ¼-approximation. For symmetric submodular functions, we show that a random set gives a ½-approximation, which can also be achieved by deterministic local search. These algorithms work in the value oracle model, where the submodular function is accessible through a black box returning f(S) for a given set S. We show that in this model, a (½ + ε)-approximation for symmetric submodular functions would require an exponential number of queries for any fixed ε > 0. In the model where f is given explicitly (as a sum of nonnegative submodular functions, each depending only on a constant number of elements), we prove NP-hardness of (5/6 + ε)-approximation in the symmetric case and NP-hardness of (¾ + ε)-approximation in the general case. [ABSTRACT FROM AUTHOR]

We study the partial capacitated vertex cover problem (PCVC) in which the input consists of a graph G and a covering requirement L. Each edge e in G is associated with a demand (or load) l(e), and each vertex v is associated with a (soft) capacity c(v) and a weight w(v). A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least L. The weight of a solution is ∑V α(v)w(v), where α(v) is the number of copies of v required to cover the demand of the edges that are assigned to v. The goal is to find a solution of minimum weight. We consider three variants of PCVC. In PCVC with separable demands the only requirement is that the total demand of edges assigned to v is at most α(v)c(v). In PCVC with inseparable demands there is an additional requirement that if an edge is assigned to v, then it must be assigned to one of its copies. The third variant is the unit demands version. We present 3-approximation algorithms for both PCVC with separable demands and PCVC with inseparable demands. We also present a 2-approximation algorithm for PCVC with unit demands. We show that similar results can be obtained for PCVC in hypergraphs and for the prize collecting version of capacitated vertex cover. Our algorithms are based on a unified approach for designing and analyzing approximation algorithms for capacitated covering problems. This approach yields simple algorithms whose analyses rely on the local ratio technique and sophisticated charging schemes. [ABSTRACT FROM AUTHOR]

Only recently Goyal, Olver, and Shepherd [PToc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists all optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms. 24 (1997), pp. 287-309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPn, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry. [ABSTRACT FROM AUTHOR]

The Nemhauser-Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser-Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a (2-2/d)-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a (2 - lg lg n/2 lg n)-approximation algorithm for general graphs, and a 2k kernel for the parameterized Generalized Vertex Cover problem. [ABSTRACT FROM AUTHOR]

We study approximation algorithms, integrality gaps, and hardness of approximation of two problems related to cycles of "small" length k in a given (undirected) graph. The instance for these problems consists of a graph G = (V,E) and an integer k. The k-Cycle Transversal problem is to find a minimum edge subset of E that intersects every k-cycle. The k-Cycle-Free Subgraph problem is to find a maximum edge subset of E without k-cycles. Our main result is for the k-Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an Ω(n-1/r + 1/r(2r-1)-ϵ )-approximation scheme with running time (1/ϵ)O(1/ϵ)poly(n), where n = ∣V∣ is the number of vertices in the graph. This improves upon the ratio 9 (n-1/r) that can be deduced from extremal graph theory. In particular, for k = 4 the improvement is from Ω(n-1/2) to Ω(n-1/3-ϵ). Our additional result is for odd k. The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Math., 142 (1995), pp. 281-286], who presented an LP-based 2-approximation algorithm. We show that k-Cycle Transversal admits a (k - 1)-approximation algorithm, which extends to any odd k the result that Krivelevich proved for k = 3. Based on this, for odd k we give an algorithm for k-Cycle-Free Subgraph with ratio k-1/2k-3 = 1/2 + 1/4k-6 ; this improves upon the trivial ratio of 1/2. For k = 3, the integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if k-Cycle Transversal admits a (2 - ϵ)-approximation algorithm, then so does the Vertex-Cover problem; thus improving the ratio 2 is unlikely. Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k (i.e., with girth > k). [ABSTRACT FROM AUTHOR]

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph G = (V,E) with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds {av, bv}vϵV on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive O(1)-approximation guarantee for degree-bounded intersecting/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph G, edge-subsets {Ei}k i=1, and nonnegative integers {bi}k i=1, find a minimum-cost spanning tree (if it exists) in G that contains at most bi edges from each set Ei. We obtain a +(r - 1) additive approximation for this problem, when each edge lies in at most r sets. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent +1 approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661-670]. [ABSTRACT FROM AUTHOR]

Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any nonnegative submodular function subject to multiple matroid or knapsack constraints. We emphasize that our results are for nonmonotone submodular functions. In particular, for any constant k, we present a ((These equations cannot be represented into ASCII text))-approximation for the submodular maximization problem under k matroid constraints, and a (1/5 - ∈)-approximation algorithm for this problem subject to k knapsack constraints (∈ > 0 is any constant). We improve the approximation guarantee of our algorithm to (These equations cannot be represented into ASCII text) for k ≥ 2 partition matroid constraints. This idea also gives a (1/k+∈)-approximation for maximizing a monotone submodular function subject to k ≥ 2 partition matroids, which is an improvement over the previously best known guarantee of 1/k+1. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when d = ϴ(n), where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., "What is the ith neighbor of vertex v?"), vertex-pair queries (i.e., "Is there an edge between vertices v and u?"), and degree queries (i.e., "What is the degree of vertex v?"). Our main finding is a lower bound of Ω(n½) on the necessary number of queries that holds for every d < n1- (n), where ?(n) = o(1). Since when d = ϴ(n) the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. This lower bound holds for testing H-freeness of every nonbipartite subgraph H. Additionally, we provide sublinear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds. Finally, in the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the "correct" edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets. [ABSTRACT FROM AUTHOR]

Given a Euclidean graph G in Rd with n vertices and m edges, we consider the problem of adding an edge to G such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in O(nm+n² log n) time, resulting in a trivial O(n³m+n4 log n)-time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in O(n4) time using O(n²) space. To reduce the running time we consider several approximation algorithms. [ABSTRACT FROM AUTHOR]

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that, for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L. [ABSTRACT FROM AUTHOR]

We consider a game-theoretical variant of the Steiner forest problem in which each player j, out of a set of k players, strives to connect his terminal pair (sj, tj ) of vertices in an undirected, edge-weighted graph G. In this paper we show that a natural adaptation of the primal-dual Steiner forest algorithm of Agrawal, Klein, and Ravi [SIAM J. Comput., 24 (1995), pp. 445-456] yields a 2-budget balanced and cross-monotonic cost sharing method for this game. We also present a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree game. This shows that our result is tight. Our algorithm gives rise to a new linear programming relaxation for the Steiner forest problem which we term the lifted-cut relaxation. We show that this new relaxation is stronger than the standard undirected cut relaxation for the Steiner forest problem. [ABSTRACT FROM AUTHOR]

The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic that achieves a best-known approximation ratio of $1 + \frac{\ln 3}{2} \approx 1.55$ for general graphs and best-known approximation ratios of $\approx 1.28$ for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound ($1.5 \cdot$ OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs. [ABSTRACT FROM AUTHOR]

Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected multigraph. They prove the KR algorithm has an approximation ratio < 1.85. We improve this bound to $\le 1+\sqrt{1/e}<1.61$ (for odd k we modify the base case of the KR algorithm). This is the best-known performance bound for a combinatorial approximation algorithm for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known combinatorial performance bound for any fixed value of $k\ge 3$, e.g., for even k the approximation ratio is $\le 1+(1-{1\over k})^{k/2}$. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on multigraphs, running in the time for O (nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies), respectively. This complements the implementation of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] which uses time O ((kn) 2) and is efficient for small k. [ABSTRACT FROM AUTHOR]

We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set{1,..., w}, and given a parameter $0G with a relative error of at most $\eps$. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of $\Omega( dw \varepsilon^{-2} )$ on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time $O(d\eps^{-2}\log \frac{d}\varepsilon)$ the number of connected components of an unweighted graph to within an additive error of $\varepsilon n$. (This becomes $O(\eps^{-2}\log \frac{1}\varepsilon)$ for $d=O(1)$.) The time bound is shown to be tight up to within the $\log \frac{d}\varepsilon$ factor. Our connected-components algorithm picks $O(1/\varepsilon^2)$ vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST. [ABSTRACT FROM AUTHOR]

This paper gives a 3/2 approximation algorithm for the smallest 3-edge connected spanning subgraph of an undirected multigraph. The previous best algorithm of Khuller and Raghavachari [J. Algorithms, 21 (1996), Pr). 434-450] has approximation ratio 5/3. The algorithm of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560] achieves ratio 3/2 for simple graphs. Our approach, based on the close relationship between an ear decomposition of a 2-edge connected graph and 3-edge connected components, enables us to achieve running time O(mα(m, n)). [ABSTRACT FROM AUTHOR]

The maximum asymmetric traveling salesperson problem, also known as the taxicab rip-off problem, is the problem of finding a maximally weighted tour in a complete asymmetric graph with nonnegative weights. We propose a polynomial time approximation algorithm for the problem with a 5/8 approximation guarantee. This (1) improves upon the approximation factors of previous results and (2) presents a simpler solution to the previously fairly involved algorithms. Our solution uses a simple linear programming formulation. Previous solutions were combinatorial. We make use of the linear programming in a novel manner and strengthen the path-coloring method originally proposed in [S. R. Kosaraju, J. K. Park, and C. Stein, Long tours and short superstrings, in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 166-177]. [ABSTRACT FROM AUTHOR]

Let vc(G) denote the minimum size of a vertex cover of a graph G = (V, E). It is well known that one can approximate vc(G) to within a factor of 2 in polynomial time; and despite considerable investigation, no (2-ε)-approximation algorithm has been found for any ε > 0. Because of the many connections between the independence number α(G) and the Lovász theta function υ(G), and because vc(G) = V - α(G), it is natural to ask how well V - υ(G) approximates vc(G). It is not difficult to show that these quantities are within a factor of 2 of each other (V - υ(G) is never less than the value of the canonical linear programming relaxation of vc(G)); our main result is that vc(G) can be more than (2 - ε) times V - υ(c) for any ε > 0. We also investigate a stronger lower bound than V - υ(G) for vc(G). [ABSTRACT FROM AUTHOR]