The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

Low diameter graph decompositions

Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for . Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log² n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second.A preliminary version of this paper appeared as Decomposing Graphs into Regions of Small Diameter in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (1991) 321-330.This work was supported in part by NSF grant DMS87-03541 and by a grant from the Israel Academy of Science.This work was supported in part by NSF grant DMS87-03541 and CCR89-11388.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

The complexity of detecting crossingfree configurations in the plane

The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

On the power of white pebbles

We construct a family (G _p |p) of directed acyclic graphs such that any black pebble strategy forG _p requiresp ² pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.Supported by the National Science Foundation under contract no. DCR-8407256 and by the office of Naval Research under contract no. N0014-80-0517.     

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.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

A simulation tool for the performance evaluation of parallel branch and bound algorithms

Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm.     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

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.     

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.     

Upward planarity testing

Acyclic digraphs, such as the covering digraphs of ordered sets, are usually drawn upward, i.e., with the edges monotonically increasing in the vertical direction. A digraph is upward planar if it admits an upward planar drawing. In this survey paper, we overview the literature on the problem of upward planarity testing. We present several characterizations of upward planarity and describe upward planarity testing algorithms for special classes of digraphs, such as embedded digraphs and single-source digraphs. We also sketch the proof of NP-completeness of upward planarity testing.Research supported in part by the National Science Foundation under grant CCR-9423847.     

On rank vs. communication complexity

This paper concerns the open problem of Lovász and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems.A preliminary version of this paper appeared in [10].This work was supported by USA-Israel BSF grant 92-00043 and by a Wolfeson research award administered by the Israeli Academy of Sciences.This work was supported by USA-Israel BSF grant 92-00106 and by a Wolfeson research award administered by the Israeli Academy of Sciences.     

On the recognition complexity of some graph properties

By applying a topological approach due to Kahn, Saks and Sturtevant, we prove that all decreasing graph properties consisting of bipartite graphs only are elusive. This is an analogue to a well-known result of Yao.     

An Optimal Edge-Robust Identifying Code in the Triangular Lattice

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v)={u C: d(u,v) 1 }, v V, are non-empty and no two of them are the same set. A 1-identifying code C is called 1-edge-robust 1-identifying if it is 1-identifying in every graph G¹ obtained from G by deleting or adding one edge. It is shown that the optimal density of a 1-edge-robust 1-identifying code in the infinite triangular lattice is 3/7.     

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.     

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.     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Topological sweep of the complete graph

We present a novel, simple and easily implementable algorithm to report all intersections in an embedding of a complete graph. For graphs with N vertices and complexity K measured as the number of segments of the embedding, the running time of the algorithm is Θ(K+NM), where M is the maximum number of edges cut by any vertical line. Our algorithm handles degeneracies, such as vertical edges or multiply intersecting edges, without requiring numerical perturbations to achieve general position.The algorithm is based on the sweep line technique, one of the most fundamental techniques in computational geometry, where an imaginary line passes through a given set of geometric objects, usually from left to right. The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method [H. Edelsbrunner, L.J. Guibas, Topologically sweeping an arrangement, J. Comput. Syst. Sci. 38 (1989) 165-194; J. Comput. Syst. Sci. 42 (1991) 249-251 (corrigendum)].The novelty in our approach is to control the topological line through the use of the moving wall that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges-that have not yet been registered in the sweep process-behind the wall.Our method has applications to graph drawing and for depth-based statistical analysis, for computing the simplicial depth median for a set of N data points [G. Aloupis, S. Langerman, M. Soss, G. Toussaint, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comp. Geom. Theory Appl. 26 (1) (2003) 69-79].We present the algorithm, its analysis, experimental results and extension of the method to general graphs.