On perfectly two-edge connected graphs

This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

On partitioning the edges of graphs into connected subgraphs

For any positive integer s, an s-partition of a graph G = (V, E) is a partition of E into E₁ ∪ E₂ ∪…? ∪ E_k, where ∣E_i∣ = s for 1 ≤ i ≤ k ? 1 and 1 ≤ ∣E_k∣ ≤ s and each E_i induces a connected subgraph of G. We prove

• (i) If G is connected, then there exists a 2-partition, but not necessarily a 3-partition;
• (ii) If G is 2-edge connected, then there exists a 3-partition, but not necessarily a 4-partition;
• (iii) If G is 3-edge connected, then there exists a 4-partition;
• (iv) If G is 4-edge connected, then there exists an s-partition for all s.

     

Polyhedral study of the connected subgraph problem

In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees.     

Polyhedral results for the bipartite induced subgraph problem

Given a graph G=(V,E) with node weights, the Bipartite Induced Subgraph Problem (BISP) is to find a maximum weight subset of nodes V^′ of G such that the subgraph induced by V^′ is bipartite. In this paper we study the facial structure of the polytope associated with that problem. We describe two classes of valid inequalities for this polytope and give necessary and sufficient conditions for these inequalities to be facet defining. For one of these classes, induced by the so-called wheels of order q, we give a polynomial time separation algorithm. We also describe some lifting procedures and discuss separation heuristics. We finally describe a Branch-and-Cut algorithm based on these results and present some computational results.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

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.     

An optimal algorithm for finding depth-first spanning tree on permutation graphs

LetG be a connected graph ofn vertices. The problem of finding a depth-first spanning tree ofG is to find a connected subgraph ofG with then vertices andn − 1 edges by depth-first-search. In this paper, we propose anO(n) time algorithm to solve this problem on permutation graphs.     

Restricted 2-factor polytopes

The optimal k-restricted 2-factor problem consists of finding, in a complete undirected graph K _n , a minimum cost 2-factor (subgraph having degree 2 at every node) with all components having more than k nodes. The problem is a relaxation of the well-known symmetric travelling salesman problem, and is equivalent to it when ≤k≤n−1. We study the k-restricted 2-factor polytope. We present a large class of valid inequalities, called bipartition inequalities, and describe some of their properties; some of these results are new even for the travelling salesman polytope. For the case k=3, the triangle-free 2-factor polytope, we derive a necessary and sufficient condition for such inequalities to be facet inducing. Received March 4, 1997 / Revised version received September 7, 1998?Published online November 9, 1999     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Maximum information stored in a labeled connected network with minimum edges

Given a set X, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1, . . . , m, the subgraph G _i induced from pattern i is a label connected graph with minimum edges. In the paper, we show that the problem is NP hard and develop a heuristic algorithm to get a fewer number of edges to store patterns.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

Every 3-connected,locally connected,claw-free graph is Hamilton-connected

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of order p ≥ 4, containing no induced subgraph isomorphic to K_1,3, is Hamilton-connected if and only if G is 3-connected. © 1996 John Wiley & Sons, Inc.     

The γ-connected assignment problem

Given a graph and costs of assigning to each vertex one of k different colors, we want to find a minimum cost assignment such that no color q induces a subgraph with more than a given number (γ_q) of connected components. This problem arose in the context of contiguity-constrained clustering, but also has a number of other possible applications. We show the problem to be NP-hard. Nevertheless, we derive a dynamic programming algorithm that proves the case where the underlying graph is a tree to be solvable in polynomial time. Next, we propose mixed-integer programming formulations for this problem that lead to branch-and-cut and branch-and-price algorithms. Finally, we introduce a new class of valid inequalities to obtain an enhanced branch-and-cut. Extensive computational experiments are reported.     

Wheel inequalities for stable set polytopes

We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytopeP _G of a graphG. Each “wheel configuration” gives rise to two such inequalities. The simplest wheel configuration is an “odd” subdivisionW of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing forP _W . Generalizations arise by allowing subdivision paths to intersect, and by replacing the “hub” of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time. Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. Research partially supported by scholarships from the Ontario Ministry of Colleges and Universities.     

Finding 2-edge connected spanning subgraphs

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|−|V|)/(r−1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximation guarantees of and , respectively.     

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.     

Pancyclicity and extendability in strong products

In this paper, we first prove that for any connected graph G with at least two vertices, there is an integer m for which the strong product X⌅G^m has pancyclic ordering from each vertex. After characterizing the graphs G for which GX⌅K₂ is Hamiltonian, we determine a criterion for extendability of cycles. We also prove that if G is a connected, K_1.3-free graph with δ ≥ 2, then GX⌅XK₂ is fully cycle extendable as well as 1-edge Hamiltonian. © 1996 John Wiley & Sons, Inc.     

Greatest common subgraphs with specified properties

A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG ₁ andG ₂ of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG ₁ andG ₂. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.