Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u⁴n) and the p-partition problem can be solved in time O(p²u⁴n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.     

Approximating k-cuts using network strength as a Lagrangean relaxation

Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points are in different components.     

Minimally (k,k)‐edge‐connected graphs

For an integer l > 1, the l‐edge‐connectivity of a connected graph with at least l vertices is the smallest number of edges whose removal results in a graph with l components. A connected graph G is (k, l)‐edge‐connected if the l‐edge‐connectivity of G is at least k. In this paper, we present a structural characterization of minimally (k, k)‐edge‐connected graphs. As a result, former characterizations of minimally (2, 2)‐edge‐connected graphs in [J of Graph Theory 3 (1979), 15–22] are extended. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 116–131, 2003     

Approximation Algorithms for Min–Max Tree Partition

We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P = NP. We present anO(n²) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p − 1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2^{(p + x)p}n²) time, and its error ratio is at most (2 − x/(x + p − 1))p.     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A computational study of graph partitioning

LetG = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node setN intok disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.Corresponding author.     

Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph

Given a hypergraph, a partition of its vertex set, and a nonnegative integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k‐edge‐connected. This problem is a common generalization of the following two problems: edge‐connectivity augmentation of graphs with partition constraints (J. Bang‐Jensen, H. Gabow, T. Jordán, Z. Szigeti, SIAM J Discrete Math 12(2) (1999), 160–207) and edge‐connectivity augmentation of hypergraphs by adding graph edges (J. Bang‐Jensen, B. Jackson, Math Program 84(3) (1999), 467–481). We give a min–max theorem for this problem, which implies the corresponding results on the above‐mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges.     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

A linear systolic algorithm for the connected component problem

A linear systolic algorithm is proposed for the connected component problem. Given an undirected graph withn vertices,m edges, andp connected components, the proposed algorithm uses (n –p + 1) cells pipelined together to figure out, in (m + 3(n –p) + 2) systolic cycles, which component each vertex belongs to.This research was supported by the National Science Council of the Republic of China under the Contract NSC77-0408-E007-01.     

A spectral heuristic for bisecting random graphs

The minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. Computing a minimum bisection is NP‐hard in the worst case. In this paper we study a spectral heuristic for bisecting random graphs G_n(p,p′) with a planted bisection obtained as follows: partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p′ and edges crossing the partition with probability p independently. If , where c₀ is a suitable constant, then with probability 1 ? o(1) the heuristic finds a minimum bisection of G_n(p,p′) along with a certificate of optimality. Furthermore, we show that the structure of the set of all minimum bisections of G_n(p,p′) undergoes a phase transition as . The spectral heuristic solves instances in the subcritical, the critical, and the supercritical phases of the phase transition optimally with probability 1 ? o(1). These results extend previous work of Boppana 5 . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Random maximal H‐free graphs*

Given a graph H, a random maximal H‐free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p=0 start with the empty graph and increase p gradually. Each time a new edge is born, it is included in the graph if this does not create a copy of H. The question is then how many edges such a graph will have when p=1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2‐balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than 𝓁 and chromatic number n*y1/(𝓁‐1)+o(1), which improves on previous bounds for 𝓁>3. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 61–82, 2001     

Infinite paths in randomly oriented lattices

The square lattice is used to generate an oriented graph in which a rightward or upward arrow is present on each edge with probability a, and a leftward or downward arrow with probability b. Independence between different edges of the square lattice is assumed, but nothing is assumed concerning the dependence between the two possible orientations at any given edge. A property of self‐duality is exploited to show that, when a+b=1, the process is, in a sense to be made precise, either critical or supercritical, but not subcritical. This observation enables progress with the percolation problem in which each horizontal edge is oriented rightward with probability p and otherwise leftward, and each vertical edge is oriented upward with probability p and otherwise downward. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 257–266, 2001     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

Two-Connected Augmentation Problems in Planar Graphs

Given a weighted undirected graph G and a subgraph S of G, we consider the problem of adding a minimum-weight set of edges of G to S so that the resulting subgraph satisfies specified (edge or vertex) connectivity requirements between pairs of nodes of S. This has important applications in upgrading telecommunication networks to be invulnerable to link or node failures. We give a polynomial algorithm for this problem when S is connected, nodes are required to be at most 2-connected, and G is planar. Applications to network design and multicommodity cut problems are also discussed.     

Counting connected graphs asymptotically

We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left.     

Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999     

Local connectivity of a random graph

A graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +?_n) log n/n)^1/2 where ?_n = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(-exp(-x)).     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010