On m-restricted edge connectivity of undirected generalized De Bruijn graphs

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S.     

A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem

Abstract. This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n ⁴ ) and O(n ⁶ ) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n ³ ) and O(n ⁴ ) maximum flow computations, respectively.     

Maximum concurrent flows and minimum cuts

In many applications, we need to find a minimum cost partition of a network separating a given pair of nodes. A classical example is the Max-Flow Min-Cut Theorem, where the cost of the partition is defined to be the sum of capacities of arcs connecting the two parts. Other similar concepts such as minimum weighted sparsest cut and flux cut have also been introduced. There is always a cost associated with a cut, and we always seek the min-cost cut separating a given pair of nodes. A natural generalization from the separation of a given pair is to find all minimum cost cuts separating all pairs of nodes, with arbitrary costs associated with all 2^n–1 — 1 cuts. In the present paper, we show thatn — 1 minimum cost cuts are always sufficient to separate all pairs of nodes.A further generalization is to considerk-way partitions rather than two-way partitions. An interesting relationship exists betweenk-way partitions, the multicommodity flow problem, and the minimum weighted sparsest cut. Namely, if the staturated arcs in a multicommodity flow problem form ak-way partition (k 4), then thek-way partition contains a two-way partition. This two-way partition is the minimum weight sparsest cut.This work is supported in part by the NSF under Grant MIP-8700767 and micro program under Grants 506205 and 506215, Intergraph, and Data General.     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (ρ_ST + 2) where ρ_ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to ρ_ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

The Stackelberg Minimum Spanning Tree Game

We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor??s prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player??s best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min?{k,1+ln?b,1+ln?W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm.     

A Divide-and-Conquer Approach to the Minimum k -Way Cut Problem

This paper presents algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of an undirected weighted graph G . Let G=(V, E) be an undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k -way cut problem with fixed k , that requires O(n ⁴ ) and O(n ⁶ ) maximum flow computations, respectively, to compute a minimum 3 -way cut and a minimum 4 -way cut of G . In this paper we first show some properties on minimum 3 -way cuts and minimum 4 -way cuts, which indicate a recursive structure of the minimum k -way cut problem when k = 3 and 4 . Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3 -way cut and a minimum 4 -way cut of G , which require O(n ³ ) and O(n ⁴ ) maximum flow computations, respectively.     

Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction

We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner’s Conjecture about the structure of minor-closed graph properties. First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely, K _3,k -minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set, R-dominating set, connected dominating set, connected edge dominating set, connected R-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner’s Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory.     

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems

We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree-constrained node-weighted Steiner tree problem: We are given an undirected graph G(V,E) , with a nonnegative integral function d that specifies an upper bound d(v) on the degree of each vertex v ∈ V in the Steiner tree to be constructed, nonnegative costs on the nodes, and a subset of k nodes called terminals. The goal is to construct a Steiner tree T containing all the terminals such that the degree of any node v in T is at most the specified upper bound d(v) and the total cost of the nodes in T is minimum. Our main result is a bicriteria approximation algorithm whose output is approximate in terms of both the degree and cost criteria—the degree of any node v ∈ V in the output Steiner tree is O(d(v) log k) and the cost of the tree is O(log k) times that of a minimum-cost Steiner tree that obeys the degree bound d(v) for each node v . Our result extends to the more general problem of constructing one-connected networks such as generalized Steiner forests. We also consider the special case in which the edge costs obey the triangle inequality and present simple approximation algorithms with better performance guarantees. Received December 21, 1998; revised September 24, 1999.     

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.     

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum <Emphasis Type="Italic">k</Emphasis>-Way Cut Problem

For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter.     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

Lower bounds for the majority communication complexity of various graph accessibility problems

We investigate the probabilistic communication complexity (more exactly, the majority communication complexity), of the graph accessibility problem (GAP) and its counting versions MOD _k -GAP,k ≥ 2. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition of the input variables, GAP and MOD _m -GAP have majority communication complexity Ω,(n), wheren denotes the number of nodes of the graph under consideration.     

On Edge Irregular Reflexive Labeling of Categorical Product of Two Paths

Among the huge diversity of ideas that show up while studying graph theory, one that has obtained a lot of popularity is the concept of labelings of graphs. Graph labelings give valuable mathematical models for a wide scope of applications in high technologies (cryptography, astronomy, data security, various coding theory problems, communication networks, etc.). A labeling or a valuation of a graph is any mapping that sends a certain set of graph elements to a certain set of numbers subject to certain conditions. Graph labeling is a mapping of elements of the graph, i.e., vertex and/or edges to a set of numbers (usually positive integers), called labels. If the domain is the vertex-set or the edge-set, the labelings are called vertex labelings or edge labelings respectively. Similarly, if the domain is V (G)[E(G), then the labeling is called total labeling. A reflexive edge irregular k-labeling of graph introduced by Tanna et al.: A total labeling of graph such that for any two different edges ab and a'b' of the graph their weights has ωt_χ(ab) = χ(a) + χ(ab) + χ(b) and ωt_χ(a'b') = χ(a') + χ(a'b') + χ(b') are distinct. The smallest value of k for which such labeling exist is called the reflexive edge strength of the graph and is denoted by res(G). In this paper we have found the exact value of the reflexive edge irregularity strength of the categorical product of two paths P_a × P_b for any choice of a ≥ 3 and b ≥ 3.     

On the adjacent vertex distinguishing edge colourings of graphs

A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ′_a(G), is the minimum number of colours needed in an avd-colouring of G. It is proved that for any connected 3-colourable Hamiltonian graph G, we have χ′_a(G)≤Δ+3.     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

Approximation Algorithms for a Capacitated Network Design Problem

We study a capacitated network design problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges to support the flow at minimum cost. Capacity can be purchased only in multiples of a fixed quantity. All the flow from a source must be routed in a single path to the sink. This NP-hard problem generalizes the Steiner tree problem and also more effectively models the applications traditionally formulated as capacitated tree problems. We present an approximation algorithm with performance ratio (_ST + 2) where _ST is the performance ratio of any approximation algorithm for the minimum Steiner tree problem. When all sources have unit demand, the ratio improves to _ST + 1) and, in particular, to 2 when all nodes in the graph are sources.     

A Fixed-Parameter Approach to 2-Layer Planarization

A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k · 6^k + |G|) time and the 1-Layer Planarization problem in O(3^k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.