Domination and total domination in complementary prisms

Let G be a graph and be the complement of G. The complementary prism of G is the graph formed from the disjoint union of G and by adding the edges of a perfect matching between the corresponding vertices of G and . For example, if G is a 5-cycle, then is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, and , where γ(G) and γ _t (G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A ₁,A ₂,…, A _m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P ₁ , P ₂, …,P _k } of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P _i | ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m ^g . Work supported by a DIMACS postdoctoral fellowship.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Given d>2 and a set of n grid points Q in ℜ ^d , we design a randomized algorithm that finds a w-wide separator, which is determined by a hyper-plane, in sublinear time such that Q has at most points on either side of the hyper-plane, and at most points within distance to the hyper-plane, where c _d is a constant for fixed d. In particular, c ₃=1.209. To our best knowledge, this is the first sublinear time algorithm for finding geometric separators. Our 3D separator is applied to derive an algorithm for the protein side-chain packing problem, which improves and simplifies the previous algorithm of Xu (Research in computational molecular biology, 9th annual international conference, pp. 408–422, 2005). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. The part of this research was done while Bin Fu was associated with the Department of Computer Science, University of New Orleans, LA 70148, USA and the Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, USA.     

A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a \(O(k^\varepsilon )\)-approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy\(_\text {FLAC}\) running in \(O(m \log (n)k + \min (m, nk)nk^2)\) and a \(O(\sqrt{k})\)-approximation called Greedy\(_\text {FLAC}^\triangleright \) running in \(O(nm + n^2 \log (n)k +n^2 k^3)\). We provide computational results to show that, Greedy\(_\text {FLAC}\) rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.     

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

Patterned self-assembly tile set synthesis (pats) aims at minimizing the number of distinct DNA tile types used to self-assemble a given rectangular color pattern. For an integer k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient Open image in new window verifier, and based on that, we establish a manually-checkable proof for the NP-hardness of 11-pats; the best previous manually-checkable proof is for 29-pats.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

Partitioning a weighted partial order

The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight w _i is given for each element i in the partial order such that w _i ≤w _j if i ≺ j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight of a chain equals the weight of the heaviest element in the chain. We prove that this problem is -hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem instances.     

Group testing in graphs

This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log ₂ e(G)⌉≤t(G)≤⌈log ₂ e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤2⁴ or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤2⁵ or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

On a hyperplane arrangement problem and tighter analysis of an error-tolerant pooling design

In this paper, we formulate and investigate the following problem: given integers d,k and r where k>r≥1,d≥2, and a prime power q, arrange d hyperplanes on to maximize the number of r-dimensional subspaces of each of which belongs to at least one of the hyperplanes. The problem is motivated by the need to give tighter bounds for an error-tolerant pooling design based on finite vector spaces. This work is partially supported by NSF CAREER Award CCF-0347565.     

Approximability and exact resolution of the multidimensional binary vector assignment problem

In this paper we consider the multidimensional binary vector assignment problem. An input of this problem is defined by m disjoint multisets \(V^1, V^2, \ldots , V^m\), each composed of n binary vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking one vector from each multiset \(V^i\). To each m-tuple we associate a p dimensional vector by applying the bit-wise AND operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors. We denote this problem by Open image in new window , and the restriction of this problem where every vector has at most c zeros by Open image in new window . Open image in new window was only known to be Open image in new window -hard, even for Open image in new window . We show that, assuming the unique games conjecture, it is Open image in new window -hard to Open image in new window -approximate Open image in new window for any fixed Open image in new window and Open image in new window . This result is tight as any solution is a Open image in new window -approximation. We also prove without assuming UGC that Open image in new window is Open image in new window -hard even for Open image in new window . Finally, we show that Open image in new window is polynomial-time solvable for fixed Open image in new window (which cannot be extended to Open image in new window ).     

A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J _j , its processing time and delivery time are denoted by p _j and q _j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J _j , q _j ≤p _j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J _i and J _j , p _i >p _j implies q _i ≥q _j . We provide an on-line algorithm with competitive ratio for both problems, and the results are the best possible. Project supported by NSFC (10671183).     

On the total {k}-domination number of Cartesian products of graphs

Let γ _t ^{k}(G) denote the total {k}-domination number of graph G, and let denote the Cartesian product of graphs G and H. In this paper, we show that for any graphs G and H without isolated vertices, . As a corollary of this result, we have for all graphs G and H without isolated vertices, which is given by Pak Tung Ho (Util. Math., 2008, to appear) and first appeared as a conjecture proposed by Henning and Rall (Graph. Comb. 21:63–69, 2005). The work was supported by NNSF of China (No. 10701068 and No. 10671191).     

The subdivision-constrained routing requests problem

We are given a digraph D=(V,A;w), a length (delay) function w:A→R ⁺, a positive integer d and a set $\mathcal{P}=\{(s_{i},t_{i};B_{i}) | i=1,2,\ldots,k\}$ of k requests, where s _i ∈V is called as the ith source node, t _i ∈V is called the ith sink node and B _i is called as the ith length constraint. For a given positive integer d, the subdivision-constrained routing requests problem (SCRR, for short) is to find a directed subgraph D′=(V′,A′) of D, satisfying the two constraints: (1) Each request (s _i ,t _i ;B _i ) has a path P _i from s _i to t _i in D′ with length $w(P_{i})=\sum_{e\in P_{i}} w(e)$ no more than B _i ; (2) Insert some nodes uniformly on each arc e∈A′ to ensure that each new arc has length no more than d. The objective is to minimize the total number of the nodes inserted on the arcs in A′. We obtain the following three main results: (1) The SCRR problem is at least as hard as the set cover problem even if each request has the same source s, i.e., s _i =s for each i=1,2,…,k; (2) For each request (s,t;B), we design a dynamic programming algorithm to find a path from s to t with length no more than B such that the number of the nodes inserted on such a path is minimized, and as a corollary, we present a k-approximation algorithm to solve the SCRR problem for any k requests; (3) We finally present an optimal algorithm for the case where $\mathcal{P}$ contains all possible requests (s _i ,t _i ) in V×V and B _i is equal to the length of the shortest path in D from s _i to t _i . To the best of our knowledge, this is the first time that the dynamic programming algorithm within polynomial time in (2) is designed for a weighted optimization problem while previous optimal algorithms run in pseudo-polynomial time.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .     

Improved algorithms for largest cardinality 2-interval pattern problem

The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n ²log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n ²) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n ²□n) upper bound. A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.     

Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

Packing 5-cycles into balanced complete m-partite graphs for odd m

Let be a complete m-partite graph with partite sets of sizes n ₁,n ₂,…,n _m . A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K _m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K _m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research of M.-H.W. was supported by NSC 93-2115-M-264-001.     

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.