Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

Efficient parallel recognition of cographs

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P₄. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P₄) whenever our algorithms decide that the input graphs are not cographs.     

Routing of single-source and multiple-source queries in static sensor networks

In this paper, we introduce new geometric ad-hoc routing algorithms to route queries in static sensor networks. For single-source-queries routing, we utilise a centralised mechanism to accomplish a query using an asymptotically optimal number of transmissions O(c), where c is the length of the shortest path between the source and the destination. For multiple-source-queries routing, the number of transmissions for each query is bounded by O(clogn), where n is the number of nodes in the network. For both single-source and multiple-source queries, the routing stage is preceded by preprocessing stages requiring O(nD) and O(n²D) transmissions, respectively, where D is the diameter of the network. Our algorithm improves the complexity of the currently best known algorithms in terms of the number of transmissions for each query. The preprocessing is worthwhile if it is followed by frequent queries. We could also imagine that there is an extra initial power (say, batteries) available during the preprocessing stage or alternatively the positions of the sensors are known in advance and the preprocessing can be done before the sensors are deployed in the field. It is also worth mentioning that a lower bound of Ω(c²) transmissions has been proved if preprocessing is not allowed [F. Kuhn, R. Wattenhofer, A. Zollinger, Asymptotically optimal geometric mobile ad-hoc routing, in: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, GA, September 2002, pp. 24–33].     

Two-Sided Closed Ideals of Certain Algebras of Unbounded Operators

This paper investigates the two-sided uniformly closed ideals of the maximal Op*-algebra L⁺(D) of (bounded or unbounded) operators on a dense domain D in a HILBERT space. It is assumed that D is a FRECHET space with respect to the graph topology. The set of all non-trivial two-sided closed ideals of L⁺(D) is well-ordered by inclusion and the α-th closed ideal ??_α is generated by the orthogonal projections onto HILBERTian subspaces of D of dimension less then ??_α. An element A in L⁺(D) belongs to the minimal closed ideal ??₀ if and only if the following two equivalent conditions are satisfied: a) A maps bounded subsets of D into relatively compact sets. b) A maps weakly convergent sequences in D into convergent sequences.     

Complexity of approximating the oriented diameter of chordal graphs

The oriented diameter of a bridgeless connected undirected (bcu) graph G is the smallest diameter among all the diameters of strongly connected orientations of G. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐time approximation algorithm that, for a given chordal bcu graph G, finds a strongly connected orientation of G with diameter at most one plus twice the oriented diameter of G; (b) prove that, for every k ≥ 2 and k # 3, to decide whether a chordal (split for k = 2) bcu graph G admits an orientation of diameter k is NP‐complete; (c) show that, unless P = NP, there is neither a polynomial‐time absolute approximation algorithm nor an α‐approximation algorithm that computes the oriented diameter of a bcu chordal graph for α < . © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 255–269, 2004     

Bounds for algebraic gossip on graphs

We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading: Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of for bounded degree graphs and an upper bound of O(n²) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of . Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 185–217, 2014     

Separation index of a graph

The concepts of separation index of a graph and of a surface are introduced. We prove that the separation index of the sphere is 3. Also the separation index of any graph faithfully embedded in a surface of genus g is bounded by a funtion of g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 53–61, 2002     

Diameter vulnerability of graphs

Let f(t, D) denote the maximum possible diameter of a graph obtained from a (t+1)-edge-connected graph of diameter D by deleting t edges. F.R.K. Chung and M.R. Garey have shown that for D≥4,(t+1)(D?2)≤ f(t, D)≤(t+1)D+t. Here we consider the cases D=2 and D=3 and show that f(t,2)=4 and $\text{3}\text{2t}\text{?3≤f(t,3)≤3}\text{2t}\text{+4}$ if t is large enough. We solve also the problem for the directed case (answering a question of F.R.K. Chung and M.R. Garey) by showing that if D ≥ 3 the diameter of a diagraph obtained from a (t + 1)-arc-connected digraph of order n by deleting t arcs is at most n?2t+1. In the case D=.....2, the maximum possible diameter of the resulting digraph is (like in the undirected case) 4. We also consider the same problem for vertices.     

Distances in random graphs with finite variance degrees

In this paper we study a random graph with N nodes, where node j has degree D_j and {D_j} are i.i.d. with ?(D_j ≤ x) = F(x). We assume that 1 ? F(x) ≤ cx^?τ+1 for some τ > 3 and some constant c > 0. This graph model is a variant of the so‐called configuration model, and includes heavy tail degrees with finite variance. The minimal number of edges between two arbitrary connected nodes, also known as the graph distance or the hopcount, is investigated when N → ∞. We prove that the graph distance grows like log_ν N, when the base of the logarithm equals ν = ??[D_j(D_j ? 1)]/??[D_j] > 1. This confirms the heuristic argument of Newman, Strogatz, and Watts [Phys Rev E 64 (2002), 026118, 1–17]. In addition, the random fluctuations around this asymptotic mean log_ν N are characterized and shown to be uniformly bounded. In particular, we show convergence in distribution of the centered graph distance along exponentially growing subsequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Augmenting forests to meet odd diameter requirements

Given a graph G=(V,E) and an integer D≥1, we consider the problem of augmenting G by the smallest number of new edges so that the diameter becomes at most D. It is known that no constant approximation algorithms to this problem with an arbitrary graph G can be obtained unless P=NP. For a forest G and an odd D≥3, it was open whether the problem is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with a forest G and an odd D; our algorithm delivers an 8-approximate solution in O(|V|³) time. We also show that a 4-approximate solution to the problem with a forest G and an odd D can be obtained in linear time if the augmented graph is additionally required to be biconnected.     

Optimal Orientations of Graphs and Digraphs: A Survey

 For a graph or digraph G, let be the family of strong orientations of G; and for any , we denote by d(D) the diameter of D. Define . In this paper, we survey the results obtained and state some problems and conjectures for the parameter . Received: October, 2001 Final version received: September 23, 2002     

Approximating average parameters of graphs

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Diameter increase caused by edge deletion

We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D ? k for even D and of (k + 1)D ? 2k + 2 for odd D ? 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D ? 1 and 4D ? 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ? 4 and k = 6, and k = 5 and k ? 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ? 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete.     

Finding cycles and trees in sublinear time

We present sublinear‐time (randomized) algorithms for finding simple cycles of length at least and tree‐minors in bounded‐degree graphs. The complexity of these algorithms is related to the distance of the graph from being C_k‐minor free (resp., free from having the corresponding tree‐minor). In particular, if the graph is ‐far from being cycle‐free (i.e., a constant fraction of the edges must be deleted to make the graph cycle‐free), then the algorithm finds a cycle of polylogarithmic length in time , where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of one‐sided error property testing algorithms in the bounded‐degree graphs model. For example, we show that cycle‐freeness of N‐vertex graphs can be tested with one‐sided error within time complexity , where ? denotes the proximity parameter. This matches the known query lower bound for one‐sided error cycle‐freeness testing, and contrasts with the fact that any minor‐free property admits a two‐sided error tester of query complexity that only depends on ?. We show that the same upper bound holds for testing whether the input graph has a simple cycle of length at least k, for any . On the other hand, for any fixed tree T, we show that T‐minor freeness has a one‐sided error tester of query complexity that only depends on the proximity parameter ?. Our algorithm for finding cycles in bounded‐degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree‐minors in complexity. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 139–184, 2014     

Domination-balanced graphs

A set D of vertices in a graph is said to be a dominating set if every vertex not in D is adjacent to some vertex in D. The domination number β(G) of a graph G is the size of a smallest dominating set. G is called domination balanced if its vertex set can be partitioned into β(G) subsets so that each subset is a smallest dominating set of the complement G of G. The purpose of this paper is to characterize these graphs.     

Diameter bounds for altered graphs

The main question addressed in this article is the following: If t edges are removed from a (t + 1) edge-connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n-vertex path P_n, then the diameter of the resulting graph is at least (n/(t + 1)) - 1. Using a similar proof, we also show that if t edges are added to an n-vertex cycle C_n, then the least possible diameter of the resulting graph is (for large n) essentially n/(t + 2) when t is even and n/(t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time-delay or signal degradation is directly related to the diameter of the network.     

Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems

The paper concerns a new variant of the hierarchical facility location problem on metric powers (HFL_β[h]), which is a multi-level uncapacitated facility location problem defined as follows. The input consists of a set F of locations that may open a facility, subsets D₁,D₂,…,D_h−1 of locations that may open an intermediate transmission station and a set D_h of locations of clients. Each client in D_h must be serviced by an open transmission station in D_h−1 and every open transmission station in D_l must be serviced by an open transmission station on the next lower level, D_l−1. An open transmission station on the first level, D₁ must be serviced by an open facility. The cost of assigning a station j on level l1 to a station i on level l−1 is c_ij. For iF, the cost of opening a facility at location i is f_i0. It is required to find a feasible assignment that minimizes the total cost. A constant ratio approximation algorithm is established for this problem. This algorithm is then used to develop constant ratio approximation algorithms for the bounded depth Steiner tree problem and the bounded hop strong-connectivity range assignment problem.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

On the number of maximal bipartite subgraphs of a graph

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 ≈ 1.5926ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

A list version of Dirac's theorem on the number of edges in colour‐critical graphs

One of the basic results in graph colouring is Brooks' theorem [R. L. Brooks, Proc Cambridge Phil Soc 37 ( 4 ) 194–197], which asserts that the chromatic number of every connected graph, that is not a complete graph or an odd cycle, does not exceed its maximum degree. As an extension of this result, Dirac [G. A. Dirac, Proc London Math Soc 7(3) ( 7 ) 161–195] proved that every k‐colour‐critical graph (k ≥ 4) on n ≥ k + 2 vertices has at least ½((k ? 1) n + k ? 3) edges. The aim of this paper is to prove a list version of Dirac's result and to extend it to hypergraphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 165–177, 2002; DOI 10.1002/jgt.998