Binhai Zhu

TCS Journal 2025 Journal Article

Constructing red-black spanners for mixed-charging vehicular networks

• Sergey Bereg
• Yuya Higashikawa
• Naoki Katoh
• Junichi Teruyama
• Yuki Tokuni
• Binhai Zhu

Motivated by the recent trend of increasing number of e-cars and hybrid cars, we investigate the problem of building a red-black spanner for a mixed-charging vehicular network. In such a network, we have two kinds of gas/charging stations: electric (black) and the traditional gas (red) stations. Our requirement is that one cannot connect two gas stations directly in the spanner (i. e. , no red-red edge), and the goal is to build a linear-size spanner with a bounded stretch factor under this requirement. (In 2-d, it can be shown that a spanner with an optimal stretch factor could have a quadratic size and if one is constrained to build the spanner purely from a given road network then it is impossible to obtain a bounded stretch factor.) Our main results are summarized as follows. 1. In 1-d, a linear-size red-black spanner is built to satisfy the ‘no red-red edge’ requirement which achieves the optimal stretch factor. 2. In 2-d and under the L 2 metric, we build a linear-size red-black spanner satisfying the ‘no red-red edge’ requirement which achieves a stretch factor of 1. 998. 3. In 2-d and under the L 1 metric, a linear-size red-black spanner is built to satisfy the ‘no red-red edge’ requirement which achieves a stretch factor of 3. 613.

I&C Journal 2025 Journal Article

The longest subsequence-duplicated subsequence and related problems

• Manuel Lafond
• Wenfeng Lai
• Adiesha Liyanage
• Binhai Zhu

Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-duplicated subsequence (LSDS) is proposed. Given a sequence S of length n, a subsequence-duplicated subsequence is a subsequence of S in the form of x 1 d 1 x 2 d 2 ⋯ x k d k with x i being a subsequence of S, x j ≠ x j + 1 and d i ≥ 2 for all i in [ k ] and j in [ k − 1 ]. We first present an O ( n 6 ) time algorithm to compute the longest cubic subsequences of all the O ( n 2 ) substrings of S, improving the trivial O ( n 7 ) bound. Then, an O ( n 6 ) time algorithm for computing the longest subsequence-duplicated subsequence (LSDS) of S is obtained. Finally we focus on two variants of this problem. We first consider the constrained version when Σ is unbounded, each letter appears in S at most d times and all the letters in Σ must appear in the solution. We show that the problem is NP-hard for d = 4, via a reduction from a special version of SAT (which is obtained from 3-COLORING). We then show that when each letter appears in S at most d = 3 times, then the problem is solvable in O ( n 4 ) time.

TCS Journal 2024 Journal Article

New approximation algorithms for RNA secondary structures prediction problems by local search

• Aizhong Zhou
• Haodi Feng
• Jiong Guo
• Haitao Jiang
• Nan Liu
• Binhai Zhu
• Daming Zhu

This paper investigates two combinatorial problems from RNA secondary structure prediction with arbitrary pseudoknots. Given a RNA sequence and a set of base pairs, two parallel and adjacent base pairs constitute a stacking. The Maximum Stacking Base Pairs problem (MSBP) aims at finding a maximum number of based pairs, all of which form stackings, while the Maximum Base Pair Stackings problem (MBPS) is to find a maximum number of stackings. Both problems are NP-hard. We present two new approximation algorithms for the two problems by local search methods. For MSBP, the approximation factor is improved from 5 2 to 7 3; as for the MBPS, the approximation factor is improved from 8 3 to 5 2.

TCS Journal 2021 Journal Article

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs

• Peiyan Zhou
• Haitao Jiang
• Daming Zhu
• Binhai Zhu

The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0. 878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0. 792).

TCS Journal 2021 Journal Article

Dispersing and grouping points on planar segments

• Xiaozhou He
• Wenfeng Lai
• Binhai Zhu
• Peng Zou

Motivated by (continuous) facility location, we study the problem of dispersing and grouping points on a set of segments (of streets) in the plane. In the former problem, given a set of n disjoint line segments in the plane, we investigate the problem of computing a point on each of the n segments such that the minimum Euclidean distance between any two of these points is maximized. We prove that this 2D dispersion problem is NP-hard, in fact, it is NP-hard even if all the segments are parallel and are of unit length. This is in contrast to the polynomial solvability of the corresponding 1D problem by Li and Wang (2016), where the intervals are in 1D and are all disjoint. With this result, we also show that the Independent Set problem on Colored Linear Unit Disk Graph (meaning the convex hulls of points with the same color form disjoint line segments) remains NP-hard, and the parameterized version of it is in W[2]. In the latter problem, given a set of n disjoint line segments in the plane we study the problem of computing a point on each of the n segments such that the maximum Euclidean distance between any two of these points is minimized. We present a factor-1. 1547 approximation algorithm which runs in O ( n log ⁡ n ) time. Our results can be generalized to the Manhattan distance.

TCS Journal 2021 Journal Article

On the solution bound of two-sided scaffold filling

• Jingjing Ma
• Daming Zhu
• Haitao Jiang
• Binhai Zhu

In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1. 4 + ε. This is achieved through a deep investigation of the optimal solution structure of Two-Sided Scaffold Filling. We make use of a relevant graph aiming at a solution of a Two-Sided Scaffold Filling instance, and evaluate the optimal solution value by the number of connected components in this graph. We show that an arbitrary optimal solution can be transformed into one whose relevant graph admits connected components that are available to compare with the solution of our algorithm in terms of their values. The performance ratio 1. 4 + ε is obtained by comparing the bound of such an optimal solution with the solution of our algorithm.

I&C Journal 2020 Journal Article

Breakpoint distance and PQ-trees

• Haitao Jiang
• Hong Liu
• Cedric Chauve
• Binhai Zhu

The PQ-tree is a fundamental data structure that has also been used in comparative genomics to model ancestral genomes with some uncertainty. To quantify the evolution between genomes represented by PQ-trees, in this paper we study two fundamental problems of PQ-tree comparison motivated by this application. First, we show that the problem of comparing two PQ-trees by computing the minimum breakpoint distance among all pairs of permutations generated respectively by the two considered PQ-trees is NP-complete for unsigned permutations. Next, we consider a generalization of the classical Breakpoint Median problem, where an ancestral genome is represented by a PQ-tree and p ≥ 1 permutations are given and we want to compute a permutation generated by the PQ-tree that minimizes the sum of the breakpoint distances to the p permutations (or k). We show that this problem is also NP-complete for p ≥ 2, and is fixed-parameter tractable with respect to k for p ≥ 1.

TCS Journal 2019 Journal Article

On some matching problems under the color-spanning model

• Sergey Bereg
• Feifei Ma
• Wencheng Wang
• Jian Zhang
• Binhai Zhu

Given a set of n points Q in the plane, each colored with one of the k given colors, a color-spanning set S ⊂ Q is a subset of k points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum. Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest. Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (FPT) when k is a parameter is open. Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where 2k is the parameter. We show that the following three problems are polynomially solvable (hence FPT): (1) MinSum Matching Color-Spanning Set, (2) MaxMin Matching Color-Spanning Set, and (3) MinMax Matching Color-Spanning Set. For the k-Multicolored Independent Matching problem, namely, computing a matching of 2k vertices in a graph such that the vertices of the edges in the matching do not share edges, we show that it is W[1]-hard. Finally, motivated by this problem, which is related to the parameterized independent set problem, we are able to prove that LCPCS is W[1]-hard.

TCS Journal 2019 Journal Article

The discrete and mixed minimax 2-center problems

• Yi Xu
• Jigen Peng
• Yinfeng Xu
• Binhai Zhu

Letting P be a set of n points in the plane, the discrete minimax 2-center problem ( D M M 2 C P ) is to find two disks centered at { p 1, p 2 } ∈ P that minimize the maximum of two terms, namely, the Euclidean distance between two centers and the distance of any other point to the closer center. The mixed minimax 2-center problem ( M M M 2 C P ) is when one of the two centers is not in P. We present algorithms solving the D M M 2 C P and M M M 2 C P. The time complexities of solving the D M M 2 C P and M M M 2 C P are O ( n 2 log ⁡ n ) and O ( n 2 log 2 ⁡ n ) respectively. Furthermore, we consider two Steiner minimum sum dipolar spanning tree problems, in which one of the two dipoles is a Steiner point and the dipoles are both Steiner points. These two problems are shown to be solvable in O ( n log ⁡ n ) and O ( n ) time respectively.

TCS Journal 2018 Journal Article

A 2k-kernelization algorithm for vertex cover based on crown decomposition

• Wenjun Li
• Binhai Zhu

We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming; moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems.

TCS Journal 2018 Journal Article

Finding disjoint dense clubs in a social network

• Peng Zou
• Hui Li
• Wencheng Wang
• Chunlin Xin
• Binhai Zhu

In a social network, the trust among its members usually cannot be carried over many hops. So it is important to find disjoint clusters with a small diameter and with a decent size, formally called dense clubs. We focus on handling this NP-complete problem in this paper. First, from the parameterized computational complexity point of view, we show that this problem does not admit a polynomial kernel (implying that it is unlikely to apply some reduction rules to obtain a practically small problem size). Then, we focus on the dual version of the problem, i. e. , deleting d vertices to obtain some isolated dense clubs. We show that this dual problem admits a simple FPT algorithm using a bounded search tree method (the running time is still too high for practical datasets). Finally, we combine a simple reduction rule together with two branching rules to obtain a practical solution (verified by extensive testing on practical datasets).

TCS Journal 2018 Journal Article

Solving the maximum internal spanning tree problem on interval graphs in polynomial time

• Xingfu Li
• Haodi Feng
• Haotao Jiang
• Binhai Zhu

This paper studies the Maximum Internal Spanning Tree problem which is to find a spanning tree with the maximum number of internal vertices on a graph. We prove that the problem can be solved in polynomial time on interval graphs. The idea is based on the observation that the number of internal vertices in a maximum internal spanning tree is at most one less than the number of edges in a maximum path cover on any graph. On an interval graph, we present an O ( n 2 ) -algorithm to find a spanning tree in which the number of internal vertices is exactly one less than the number of edges in a maximum path cover of the graph, where n is the number of vertices in the interval graph.

TCS Journal 2017 Journal Article

Improved algorithms for intermediate dataset storage in a cloud-based dataflow

• Jie Cheng
• Daming Zhu
• Binhai Zhu

In order to run a dataflow with as low cost as possible, it is often faced with deciding which data-sets in a data-set sequence should be stored, with the rest regenerated. The Intermediate Data-set Storage problem arises from this situation. The current best algorithm for this problem takes O ( n 4 ) time. In this paper, we present two improved algorithms for this problem, the first of which can achieve a time complexity O ( n 2 ), the second of which O ( r n ), where n is the number of data-sets in a dataflow, r is a numerical number which indicates how large it is for the maximum storage cost to be divided by the minimum computation cost in the dataflow.

MFCS Conference 2016 Conference Paper

On the General Chain Pair Simplification Problem

• Chenglin Fan
• Omrit Filtser
• Matthew J. Katz
• Binhai Zhu

The Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated by the problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones. In this problem, given two polygonal chains of lengths n and m, the goal is to simplify both of them simultaneously, so that the lengths of the resulting simplifications as well as the discrete Frechet distance between them are bounded. When the vertices of the simplifications are arbitrary (i. e. , not necessarily from the original chains), the problem is called General CPS (GCPS). In this paper we consider for the first time the complexity of GCPS under both the discrete Frechet distance (GCPS-3F) and the Hausdorff distance (GCPS-2H). (In the former version, the quality of the two simplifications is measured by the discrete Fr'echet distance, and in the latter version it is measured by the Hausdorff distance.) We prove that GCPS-3F is polynomially solvable, by presenting an widetilde-O((n+m)^6 min{n, m}) time algorithm for the corresponding minimization problem. We also present an O((n+m)^4) 2-approximation algorithm for the problem. On the other hand, we show that GCPS-2H is NP-complete, and present an approximation algorithm for the problem.

TCS Journal 2015 Journal Article

A factor-(1.408 +ε) approximation for sorting unsigned genomes by reciprocal translocations

• Haitao Jiang
• Lusheng Wang
• Binhai Zhu
• Daming Zhu

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1. 5 + ε. In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1. 408 + ε, where ε = O ( 1 / log ⁡ n ).

TCS Journal 2015 Journal Article

Improved parameterized and exact algorithms for cut problems on trees

• Iyad Kanj
• Guohui Lin
• Tian Liu
• Weitian Tong
• Ge Xia
• Jinhui Xu
• Boting Yang
• Fenghui Zhang

We study the Multicut on Trees and the Generalized Multiway Cut on Trees problems. For the Multicut on Trees problem, we present a parameterized algorithm that runs in time O ⁎ ( ρ k ), where ρ = 2 + 1 < 1. 554 is the positive root of the polynomial x 4 − 2 x 2 − 1. This improves the current-best algorithm of Chen et al. that runs in time O ⁎ ( 1. 619 k ). For the Generalized Multiway Cut on Trees problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the Generalized Multiway Cut on Trees problem to the Multicut on Trees problem, our results give a parameterized algorithm that solves the Generalized Multiway Cut on Trees problem in time O ⁎ ( ρ k ).

TCS Journal 2014 Journal Article

Combinatorial Optimization and Applications

• Peter Widmayer
• Yinfeng Xu
• Binhai Zhu

TCS Journal 2014 Journal Article

Following a curve with the discrete Fréchet distance

• Tim Wylie
• Binhai Zhu

Finding the similarity between curves is an important problem that comes up in many areas such as 3D modeling, GIS applications, ordering, and reachability. A related problem is to find one of the curves given a measure of similarity and another curve. Given a set of points S, a polygonal curve P, and an ε > 0, the discrete set-chain matching problem is to find another polygonal curve Q such that the nodes of Q are points in S and d F ( P, Q ) ≤ ε. Here, d F is the discrete Fréchet distance between the two polygonal curves. For the first time we study the set-chain matching problem based on the discrete Fréchet distance rather than the continuous Fréchet distance. We further extend the problem based on unique or non-unique nodes and on limiting the number of points used. We prove that three of the variations of the set-chain matching problem are NP-complete. For the version of the problem that is polynomial, we give an O ( | P | | S | ) time greedy solution.

TCS Journal 2014 Journal Article

On the approximability of the exemplar adjacency number problem for genomes with gene repetitions

• Zhixiang Chen
• Bin Fu
• Randy Goebel
• Guohui Lin
• Weitian Tong
• Jinhui Xu
• Boting Yang
• Zhiyu Zhao

In this paper, we apply a measure, exemplar adjacency number, which complements and extends the well-studied breakpoint distance between two permutations, to measure the similarity between two genomes (or in general, between any two sequences drawn from the same alphabet). For two genomes G and H drawn from the same set of n gene families and containing gene repetitions, we consider the corresponding Exemplar Adjacency Number problem (EAN), in which we delete duplicated genes from G and H such that the resultant exemplar genomes (permutations) G and H have the maximum adjacency number. We obtain the following results. First, we prove that the one-sided 2-repetitive EAN problem, i. e. , when one of G and H is given exemplar and each gene occurs in the other genome at most twice, can be linearly reduced from the Maximum Independent Set problem. This implies that EAN does not admit any O ( n 0. 5 − ϵ ) -approximation algorithm, for any ϵ > 0, unless P = NP. This hardness result also implies that EAN, parameterized by the optimal solution value, is W[1]-hard. Secondly, we show that the two-sided 2-repetitive EAN problem has an O ( n 0. 5 ) -approximation algorithm, which is tight up to a constant factor.

TCS Journal 2014 Journal Article

Voronoi diagram with visual restriction

• Chenglin Fan
• Jun Luo
• Wencheng Wang
• Binhai Zhu

In a normal Voronoi diagram, each site is able to see all the points in the plane. In this paper, we study the case such that each site is only able to see a visually restricted region in the plane and construct the so-called Visual Restriction Voronoi Diagram (VRVD). We show that the visual restriction Voronoi cell of each site is not necessarily convex and it could consist of many disjoint regions. We prove that the combinatorial complexity of the VRVD on n sites is Θ ( n 2 ), and then show that the VRVD can be constructed in O ( n 2 ) time and O ( n 2 ) space. Besides that, we also give another algorithm with an extra log n factor of running time to compute VRVD, which is easy to implement in practice.

TCS Journal 2013 Journal Article

Preface

• Binhai Zhu
• Jun Luo

TCS Journal 2013 Journal Article

Streaming with minimum space: An algorithm for covering by two congruent balls

• Chung Keung Poon
• Binhai Zhu

In this paper we design a simple streaming algorithm for maintaining two smallest balls (of equal radius) in d -dimension to cover a set of points in an on-line fashion. Different from most of the traditional streaming models, at any step we use the minimum amount of space by only storing the locations and the (common) radius of the balls. Previously, such a geometric algorithm is only investigated for covering with one ball (one-center) by Zarrabi-Zadeh and Chan (2006) [16]. We give an analysis of our algorithm, which is significantly different from the one-center algorithm due to the obvious possibility of grouping points wrongly under this streaming model. We show that our algorithm has an approximation ratio 2 for d = 1 and at most 5. 611 for any fixed d > 1. We also present lower bounds of 1. 5 and 1. 604 for the problem in the d = 1 and d > 1 cases respectively.

TCS Journal 2012 Journal Article

A ( 1 + ε )-approximation algorithm for sorting by short block-moves

• Haitao Jiang
• Daming Zhu
• Binhai Zhu

Sorting permutations by operations such as reversals and block-moves has received much attention because of its applications in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. In this paper, we investigate the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation, and devise a ( 1 + ε )-approximation algorithm for this problem, where ε is the number of elements divided by the number of inversions in the permutation. The algorithm mostly relies on a new structure in the permutation graph called an umbrella, which can be optimally sorted in O ( n 2 ) time.

TCS Journal 2011 Journal Article

On the red/blue spanning tree problem

• Sergey Bereg
• Minghui Jiang
• Boting Yang
• Binhai Zhu

A geometric spanning tree of a point set S is a tree whose vertex set is S and whose edge set is a set of non-crossing straight line segments with endpoints in S. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is a minimum. If no three points are collinear, we show that the minimum number of crossing points is completely determined by the number of maximal red (or blue) chains on the convex hull of all red points and blue points. We design an optimal algorithm for constructing a geometric spanning tree of all the red points and a geometric spanning tree of all the blue points with the minimum number of crossing points. If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.

TCS Journal 2006 Journal Article

On the edge l ∞ radius of Saitou and Nei's method for phylogenetic reconstruction

• Wenqiang Dai
• Yinfeng Xu
• Binhai Zhu

In this paper, we study the performance of Saitou and Nei's neighbor-joining method for phylogenetic reconstruction. We show that the edge l ∞ radius of the method is 1 4. This improves an result by Atteson [The performance of neighbor-joining methods of phylogenetic reconstruction, Algorithmica 25 (1999) 251–278] and Xu et al. [A lower bound on the edge l ∞ radius of Saitou and Nei's method for phylogenetic reconstruction, Inform. Process. Lett. 94(5) (2005) 225–230]. Previously, only an upper bound 1 4 and a lower bound 1 6 were known.

TCS Journal 2006 Journal Article

Preface

• Nimrod Megiddo
• Yinfeng Xu
• Binhai Zhu

TCS Journal 2004 Journal Article

Preface

• Tandy Warnow
• Binhai Zhu

TCS Journal 2003 Journal Article

Polynomial time algorithms for three-label point labeling

• Rob Duncan
• Jianbo Qian
• Antoine Vigneron
• Binhai Zhu

In this paper, we present an O(n2 log n) time solution for the following multi-label map labeling problem: given a set S of n distinct sites in the plane, place at each site a triple of uniform squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundaries of its three labeling squares. We also study the problem under the discrete model, i. e. , a site must be at the corners of its three label squares. We obtain an optimal Θ(n log n) time algorithm for the latter problem.

TCS Journal 2000 Journal Article

Three-dimensional weak visibility: Complexity and applications

• Cao An Wang
• Binhai Zhu

In this paper, we study the complexity of 3D weak visibility. We obtain an O(n8) time and Θ(n6) space algorithm to compute the weakly visible region of a triangle F from another triangle G among general scenes, which are a set of n disjoint triangles. We also consider the cases when the scenes are rectilinear objects and polyhedral terrains. We show that in these special situations the weakly visible regions can be computed much faster in O(n6) time and O(n4) space. With these results, we obtain the first known polynomial time algorithm to decide whether or not a simple polyhedron is weakly (internally or externally) visible.

SODA Conference 1997 Conference Paper

Map Labeling and Its Generalizations

• Srinivas Doddi
• Madhav V. Marathe
• Andranik Mirzaian
• Bernard M. E. Moret
• Binhai Zhu