A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs

For an edge-weighted graph G with n vertices and m edges, the minimum k-way cut problem is to find a partition of the vertex set into k non-empty subsets so that the weight sum of edges between different subsets is minimized. For this problem with k = 5 and 6, we present a deterministic algorithm that runs in O(n^{k – 1}F(n, m)) = O(mn^k log (n²/m)) time, where F(n, m) denotes the time bound required to solve the maximum flow problem in G. The bounds Õ(mn⁵) for k = 5 and Õ(mn⁶) for k = 6 improve the previous best randomized bounds Õ(n⁸) and Õ(n¹⁰), respectively.     

Restricted domination parameters in graphs

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊂eqV(G) is an m-tuple dominating set if S dominates every vertex of G at least m times, and an m-dominating set if S dominates every vertex of G−S at least m times. The minimum cardinality of a dominating set is γ, of an m-dominating set is γ _m , and of an m-tuple dominating set is mtupledom. For a property π of subsets of V(G), with associated parameter f_π, the k-restricted π-number r _k (G,f_π) is the smallest integer r such that given any subset K of (at most) k vertices of G, there exists a π set containing K of (at most) cardinality r. We show that for 1< k < n where n is the order of G: (a) if G has minimum degree m, then r _k (G,γ _m ) < (mn+k)/(m+1); (b) if G has minimum degree 3, then r _k (G,γ) < (3n+5k)/8; and (c) if G is connected with minimum degree at least 2, then r _k (G,ddom) < 3n/4 + 2k/7. These bounds are sharp. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Two Variations of the Minimum Steiner Problem

Given a set S of starting vertices and a set T of terminating vertices in a graph G = (V,E) with non-negative weights on edges, the minimum Steiner network problem is to find a subgraph of G with the minimum total edge weight. In such a subgraph, we require that for each vertex s S and t T, there is a path from s to a terminating vertex as well as a path from a starting vertex to t. This problem can easily be proven NP-hard. For solving the minimum Steiner network problem, we first present an algorithm that runs in time and space that both are polynomial in n with constant degrees, but exponential in |S|+|T|, where n is the number of vertices in G. Then we present an algorithm that uses space that is quadratic in n and runs in time that is polynomial in n with a degree O(max {max {|S|,|T|}–2,min {|S|,|T|}–1}). In spite of this degree, we prove that the number of Steiner vertices in our solution can be as large as |S|+|T|–2. Our algorithm can enumerate all possible optimal solutions. The input graph G can either be undirected or directed acyclic. We also give a linear time algorithm for the special case when min {|S|,|T|} = 1 and max {|S|,|T|} = 2.The minimum union paths problem is similar to the minimum Steiner network problem except that we are given a set H of hitting vertices in G in addition to the sets of starting and terminating vertices. We want to find a subgraph of G with the minimum total edge weight such that the conditions required by the minimum Steiner network problem are satisfied as well as the condition that every hitting vertex is on a path from a starting vertex to a terminating vertex. Furthermore, G must be directed acyclic. For solving the minimum union paths problem, we also present algorithms that have a time and space tradeoff similar to algorithms for the minimum Steiner network problem. We also give a linear time algorithm for the special case when |S| = 1, |T| = 1 and |H| = 2.An extended abstract of part of this paper appears in Hsu et al. (1996).Supported in part by the National Science Foundation under Grants CCR-9309743 and INT-9207212, and by the Office of Naval Research under Grant No. N00014-93-1-0272.Supported in part by the National Science Council, Taiwan, ROC, under Grant No. NSC-83-0408-E-001-021.     

Minimum Cost Edge Subset Covering Exactly k Vertices of a Graph

Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n ³) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices.     

3-Partitioning Problems for Maximizing the Minimum Load

The optimization versions of the 3-Partitioning and the Kernel 3-Partitioning problems are considered in this paper. For the objective to maximize the minimum load of the m subsets, it is shown that the MODIFIED LPT algorithm has performance ratios (3m – 1)/(4m – 2) and (2m – 1)/(3m – 2), respectively, in the worst case.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

On the distance paired domination of generalized Petersen graphs <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,1) and <Emphasis Type="Italic">P</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,2)

Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k -distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k -distance paired domination number, denoted by γ _p ^k (G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1.     

The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers

Let k 5 be a fixed integer and let m = (k – 1)/2. It is shown that the independence number of a C _k-free graph is at least c ₁[ d(v)^{1/(m – 1)}]^{(m – 1)/m} and that, for odd k, the Ramsey number r(C _k, K _n) is at most c ₂(n ^{m + 1}/log n)^1/m , where c ₁ = c ₁(m) > 0 and c ₂ = c ₂(m) > 0.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

Tree edge decomposition with an application to minimum ultrametric tree approximation

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.     

Finding an anti-risk path between two nodes in undirected graphs

Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent site of the blocked edge. Let ℘={P _G (s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper will propose the Anti-risk Path Problem of finding a path P _G (s,t) in ℘ such that it has minimum risk. We will show that this problem can be solved in O(mn+n ²log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively. This research is supported by NSF of China under Grants 70525004, 60736027, 70121001 and Postdoctoral Science Foundation of China under Grant 20060401003.     

Incrementing Bipartite Digraph Edge-Connectivity

This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O(km log n) for unweighted digraphs and O(nm log (n ²/m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Penta-Extensions of Hereditary Classes of Graphs

Penta is the configuration shown in figure 1(a), where continuous lines represent edges and dotted lines represent non-edges. The vertex u in figure 1(a) is called the center of Penta. A graph G is called a pentagraph if every induced subgraph H of G has a vertex v which is not a center of induced Penta in H. The class of pentagraphs is a common generalization of chordal [triangulated] graphs and Mahadev graphs. We construct a polynomial-time algorithm that either find a maximum stable set of G or concludes that G is not a pentagraph. We propose a method for extending α-polynomial hereditary classes based on induced Pentas.     

Hardness of <Emphasis Type="Italic">k</Emphasis>-Vertex-Connected Subgraph Augmentation Problem

Given a k-connected graph G=(V,E) and V ^′⊂V, k-Vertex-Connected Subgraph Augmentation Problem (k-VCSAP) is to find S⊂V∖V ^′ with minimum cardinality such that the subgraph induced by V ^′∪S is k-connected. In this paper, we study the hardness of k-VCSAP in undirect graphs. We first prove k-VCSAP is APX-hard. Then, we improve the lower bound in two ways by relying on different assumptions. That is, we prove no algorithm for k-VCSAP has a PR better than O(log (log n)) unless P=NP and O(log n) unless NP⊆DTIME(n ^{O(log log n)}), where n is the size of an input graph.     

Power Assignment for <Emphasis Type="Italic">k</Emphasis>-Connectivity in Wireless Ad Hoc Networks

The problem Min-Power k-Connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k, a (k + 12H (k)) -approximation algorithm for k(2k–1) n where n is the network size, a (k+2(k + 1)/2) -approximation algorithm for 2 k7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.This work is supported in part by Hong Kong Research Grant Council under grant No. CityU 1149/04E.This work is partially supported by NSF CCR-0311174.     

The Polymatroid Steiner Problems

The Steiner tree problem asks for a minimum cost tree spanning a given set of terminals S⊂eqV in a weighted graph G = (V,E,c), c:E→ R⁺. In this paper we consider a generalization of the Steiner tree problem, so called Polymatroid Steiner Problem, in which a polymatroid P = P(V) is defined on V and the Steiner tree is required to span at least one base of P (in particular, there may be a single base S⊂eqV). This formulation is motivated by the following application in sensor networks – given a set of sensors S = {s₁,…,s_k}, each sensor s_i can choose to monitor only a single target from a subset of targets X_i, find minimum cost tree spanning a set of sensors capable of monitoring the set of all targets X = X₁ ∪ … ∪ X_k. The Polymatroid Steiner Problem generalizes many known Steiner tree problem formulations including the group and covering Steiner tree problems. We show that this problem can be solved with the polylogarithmic approximation ratio by a generalization of the combinatorial algorithm of Chekuri et al. (2002).We also define the Polymatroid directed Steiner problem which asks for a minimum cost arborescence connecting a given root to a base of a polymatroid P defined on the terminal set S. We show that this problem can be approximately solved by algorithms generalizing methods of Chekuri et al. (2002).A preliminary version of this paper appeared in ISAAC 2004     

Packing <Emphasis Type="Bold">[1, Δ]</Emphasis>-factors in graphs of small degree

Given an undirected, connected graph G with maximum degree Δ, we introduce the concept of a [1, Δ]-factor k-packing in G, defined as a set of k edge-disjoint subgraphs of G such that every vertex of G has an incident edge in at least one subgraph. The problem of deciding whether a graph admits a [1,Δ]-factor k-packing is shown to be solvable in linear time for k = 2, but NP-complete for all k≥ 3. For k = 2, the optimisation problem of minimising the total number of edges of the subgraphs of the packing is NP-hard even when restricted to subcubic planar graphs, but can in general be approximated within a factor of by reduction to the Maximum 2-Edge-Colorable Subgraph problem. Finally, we discuss implications of the obtained results for the problem of fault-tolerant guarding of a grid, which provides the main motivation for research.     

A dynamic programming approach of finding an optimal broadcast schedule in minimizing total flow time

We study the problem of (off-line) broadcast scheduling in minimizing total flow time and propose a dynamic programming approach to compute an optimal broadcast schedule. Suppose the broadcast server has k pages and the last page request arrives at time n. The optimal schedule can be computed in O(k³(n+k)^k−1) time for the case that the server has a single broadcast channel. For m channels case, i.e., the server can broadcast m different pages at a time where m < k, the optimal schedule can be computed in O(n^k−m) time when k and m are constants. Note that this broadcast scheduling problem is NP-hard when k is a variable and will take O(n^k−m+1) time when k is fixed and m ≥ 1 with the straightforward implementation of the dynamic programming approach. The preliminary version of this paper appeared in Proceedings of the 11th Annual International Computing and Combinatorics Conference as “Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling”.