Node-weighted Steiner tree approximation in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n ^O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Alignments with non-overlapping moves,inversions and tandem duplications in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) time

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n ³) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n ⁵) for general scoring schemes, O(n ⁴log n) for concave scoring schemes and O(n ⁴) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164.     

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.     

Broadcast Routing with Minimum Wavelength Conversion in WDM Optical Networks

We consider dynamic routing of broadcast connections in WDM optical networks. Given the current network state, we want to find a minimum set of network nodes S such that a broadcast routing using only the nodes in S as wavelength conversion nodes can be found. This ensures that the average conversion delay from the source to all destinations is minimized. We refer to the problem as Broadcast Conversion Node Selection (BCNS) problem. We prove that BCNS has no polynomial-time approximation with performance ratio ln n for < 1 unless NPDTIME(n^{O(log log n)}) where n is the number of vertices in the input graph. We present a greedy approximation algorithm for BCNS that achieves approximation ratio 2+ln n. Simulation results show that the algorithm performs very well in practice, obtaining optimal solutions in most of the cases.     

Optimal tree structure with loyal users and batch updates

We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n⋅K+K ⁴) time where K=min {4(log (1−p)⁻¹)⁻¹,n} and n is the number of normal users.     

A polynomial-time perfect sampler for the <Emphasis Type="Italic">Q</Emphasis>-Ising with a vertex-independent noise

We present a polynomial-time perfect sampler for the Q-Ising with a vertex-independent noise. The Q-Ising, one of the generalized models of the Ising, arose in the context of Bayesian image restoration in statistical mechanics. We study the distribution of Q-Ising on a two-dimensional square lattice over n vertices, that is, we deal with a discrete state space {1,…,Q} ⁿ for a positive integer Q. Employing the Q-Ising (having a parameter β) as a prior distribution, and assuming a Gaussian noise (having another parameter α), a posterior is obtained from the Bayes’ formula. Furthermore, we generalize it: the distribution of noise is not necessarily a Gaussian, but any vertex-independent noise. We first present a Gibbs sampler from our posterior, and also present a perfect sampler by defining a coupling via a monotone update function. Then, we show O(nlog n) mixing time of the Gibbs sampler for the generalized model under a condition that β is sufficiently small (whatever the distribution of noise is). In case of a Gaussian, we obtain another more natural condition for rapid mixing that α is sufficiently larger than β. Thereby, we show that the expected running time of our sampler is O(nlog n).     

Finding longest increasing and common subsequences in streaming data

We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream of elements drawn from an alphabet αbet has length at least k, we discuss a one-pass algorithm using O(k log αbetsize) space, with update time either O(log k) or O(log log αbetsize); for αbetsize = O(1), we can achieve O(log k) space and constant-time updates. We also prove a lower bound of Ω(k) on the space requirement for this problem for general alphabets αbet, even when the input stream is a permutation of αbet. For finding the actual LIS, we give a ⌈log (1 + 1/ɛ)-pass algorithm using O(k^1+ɛlog αbetsize) space, for any ɛ > 0. For LCS, there is a trivial Θ(1)-approximate O(log n)-space streaming algorithm when αbetsize = O(1). For general alphabets αbet, the problem is much harder. We prove several lower bounds on the LCS problem, of which the strongest is the following: it is necessary to use Ω(n/ρ²) space to approximate the LCS of two n-element streams to within a factor of ρ, even if the streams are permutations of each other. A preliminary version of this paper appears in the Proceedings of the 11th International Computing and Combinatorics Conference (COCOON'05), August 2005, pp. 263–272.     

A quadratic lower bound for Rocchio’s similarity-based relevance feedback algorithm with a fixed query updating factor

Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1} ⁿ , when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)³) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents with a constant query updating factor and a zero classification threshold.     

On the complexity and approximation of non-unique probe selection using d-disjunct matrix

In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(log k)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)log n)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms. The research of T. Znati was supported in part by National Science Foundation under grant CCF-0548895.     

Flattening topologically spherical surface

The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem.     

Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

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.     

Packing cycles exactly in polynomial time

Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ _v∈V ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V) ^T . We present an efficient algorithm which finds in O(|V|⁸〈w〉²+|V|¹⁴) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ₊-max-flow min-cut property.     

Labelling algorithms for paired-domination problems in block and interval graphs

Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math. 155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs. In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs.     

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.     

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.     

On the equitable k *-laceability of hypercubes

Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C _k (u,v). A k-container is a k ^*-container if it spans all vertices of G. We define G to be a k ^*-laceable graph if there is a k ^*-container joining any two vertices from different partite sets. A k ^*-container C _k ^*(u,v)={P ₁,…,P _k } is equitable if ||V(P _i )|−|V(P _j )||≤2 for all 1≤i,j≤k. A graph is equitably k ^*-laceable if there is an equitable k ^*-container joining any two vertices in different partite sets. Let Q _n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q _n is equitably k ^*-laceable for all k≤n−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.     

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.     

Approximating the chromatic index of multigraphs

It is well known that if G is a multigraph then χ′(G)≥χ′^*(G):=max {Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′^*(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max {2|E(G[U])|/(|U|−1):U⊆V(G),|U|≥3, |U| is odd}. The conjecture that χ′(G)≤max {Δ(G)+1,⌈Γ(G)⌉} was made independently by Goldberg (Discret. Anal. 23:3–7, 1973), Anderson (Math. Scand. 40:161–175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423–460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′^*(G)+c χ′^*(G) when χ′^*(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋; and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with $\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor$\chi'(G)>\lfloor\Delta(G)+\sqrt{\Delta(G)/2}\rfloor , improving the above mentioned results. As a consequence, for multigraphs G with $\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2}$\chi'(G)>\Delta(G)+\sqrt {\Delta(G)/2} the answer to a 1964 problem of Vizing is in the affirmative.