An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*

Given an undirected multigraph G and a subset of vertices S ⊆ V (G), the STEINER TREE PACKING problem is to find a largest collection of edge-disjoint trees that each connects S. This problem and its generalizations have attracted considerable attention from researchers in different areas because of their wide applicability. This problem was shown to be APX-hard (no polynomial time approximation scheme unless P=NP). In fact, prior to this paper, not even an approximation algorithm with asymptotic ratio o(n) was known despite several attempts. In this work, we present the first polynomial time constant factor approximation algorithm for the STEINER TREE PACKING problem. The main theorem is an approximate min-max relation between the maximum number of edge-disjoint trees that each connects S (S-trees) and the minimum size of an edge-cut that disconnects some pair of vertices in S (S-cut). Specifically, we prove that if every S-cut in G has at least 26k edges, then G has at least k edge-disjoint S-trees; this answers Kriesells conjecture affirmatively up to a constant multiple. * A preliminary version appeared in the Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2004. † The author was supported by an Ontario Graduate Scholarship and a University of Toronto Fellowship.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

A New Lower Bound For A Ramsey-Type Problem

Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the maximum subset of G without a copy of complete graph K_r. Our results substantially improve previous bounds of Krivelevich and Bollobás and Hind. * Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting Microsoft Research.     

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

Given a directed edge-weighted graph and k source-sink pairs, the Minimum Directed Multicut Problem is to find an edge subset with minimal weight, that separates each source-sink pair. Determining the minimum multicut in directed or undirected graphs is NP-hard. The fractional version of the minimum multicut problem is dual to the maximum multicommodity flow problem. The integrality gap for an instance of this problem is the ratio of the minimum weight multicut to the minimum weight fractional multicut; trivially this gap is always at least 1 and it is easy to show that it is at most k. In the analogous problem for undirected graphs this upper bound was improved to O(log k).In this paper, for each k an explicit family of examples is presented each with k source-sink pairs for which the integrality gap can be made arbitrarily close to k. This shows that for directed graphs, the trivial upper bound of k can not be improved.* This work was supported in part by NSF grant CCR-9700239 and by DIMACS. This work was done while a postdoctoral fellow at DIMACS.     

On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

Packing cycles through prescribed vertices under modularity constraints

The well-known theorem of Erd?s–Pósa says that either a graph G has k disjoint cycles or there is a vertex set X   of order at most f(k)$f(k)$ for some function f   such that G?X$G?X$ is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization.     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

Hamiltonian paths with prescribed edges in hypercubes

Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Q_n contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Q_n not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary.     

Expansion And Isoperimetric Constants For Product Graphs

Vertex and edge isoperimetric constants of graphs are studied. Using a functional-analytic approach, the growth properties, under products, of these constants is analyzed.     

Lower Bounds For Concurrent Zero Knowledge*

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.* An abridge version of this work has appeared in [24].     

Cycles throughk vertices in bipartite tournaments

We give a simple proof that everyk-connected bipartite tournament has a cycle through every set ofk vertices. This was conjectured in [4].This research was done while the first author was visiting Laboratoire de Recherche en Informatique, universite Paris-Sud whose hospitality and financial support is gratefully acknowledged     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

An upper bound on the size of the snake-in-the-box

A snake in a graph is a simple cycle without chords. We give an upper bound on the size of a snake S in then-dimensional cube of the form |S|2 ^n–1(1–n ^1/2/89+O(1/n)).     

Projective plane and Möbius band obstructions

LetS be a compact surface with possibly non-empty boundary S and letG be a graph. LetK be a subgraph ofG embedded inS such that SK. Anembedding extension ofK toG is an embedding ofG inS which coincides onK with the given embedding ofK. Minimal obstructions for the existence of embedding extensions are classified in cases whenS is the projective plane or the Möbius band (for several canonical choices ofK). Linear time algorithms are presented that either find an embedding extension, or return a nice obstruction for the existence of extensions.Supported in part by the Ministry of Science and Technology of Slovenia, Research Project P1-0210-101-94.     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

Dense sets and embedding binary trees into hypercubes

The purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.     

A parallel algorithm for the maximal path problem

In this paper we present anO (log⁵ n) time parallel algorithm for constructing a Maximal Path in an undirected graph. We also give anO (log^1/2+ε) time parallel algorithm for constructing a depth first search tree in an undirected graph. This work was supported in part by an IBM Faculty Development Award, an NSF Graduate Fellowship, and NSF grant DCR-8351757.