Jianer Chen

EAAI Journal 2024 Journal Article

A wearable knee rehabilitation system based on graphene textile composite sensor: Implementation and validation

• Cheng Shen
• Zhongcai Pei
• Weihai Chen
• Yi Zhou
• Jianhua Wang
• Xingming Wu
• Jianer Chen

The effectiveness of knee rehabilitation systems in aiding patients with rehabilitation training has been well-documented. Presently, there is an increasing emphasis on the wearing comfort and user engagement of these systems. In this paper, a wearable knee rehabilitation system (WKRS) based on the graphene textile composite sensor (GTCS), which subjects perform rehabilitation training by controlling the ascent and descent of a bird in the visual feedback game utilized GTCS, is proposed and investigated. To obtain an accurate and smooth estimated knee joint angle, we propose an improved tree boosting regression algorithm based on extreme gradient boosting (XGBoost), called improved XGBoost (IXGB). Specifically, the estimated results are smoothed by two steps: curving the preliminary estimating results within the same interval and smoothing the preliminary estimating results using the weighted moving average method. An online experiment with ten subjects validates the effectiveness of the WKRS and IXGB. Results indicate that the IXGB significantly enhances the smoothness of estimated value while maintaining estimation accuracy compared to XGBoost, random forest regression (RFR) and support vector regression (SVR). IXGB achieves an average increase of 33. 43 % in root mean square error, 23. 83 % in R-squared, and a 62. 63% decrease in smoothness.

TCS Journal 2024 Journal Article

Space limited linear-time graph algorithms on big data

• Jianer Chen
• Zirui Chu
• Ying Guo
• Wei Yang

We study algorithms for graph problems in which the graphs are of extremely large size N so that super-linear time ω ( N ) or linear space Θ ( N ) would become impractical. We use a parameter k to characterize the computational power of a normal computer that can provide additional time and space bounded by polynomials of k in dealing with the large graphs. In particular, we are interested in strict linear-time algorithms using space O ( k O ( 1 ) ). In our case studies, as examples, we present (1) a randomized greedy algorithm of time O ( N ) and space O ( k 2 ) for a parameterized version of the Maximal Matching problem; and (2) randomized kernelization algorithms of time O ( N ) and space O ( k O ( 1 ) ) for a number of well-known NP-hard problems. Our kernelization algorithms have their kernel sizes match the best kernel sizes by known polynomial-time kernelization algorithms with no space constraints for the problems. We also study the relationship between our proposed model and the streaming model. This study motivates a new streaming kernelization algorithm for the famous Vertex Cover problem that has an optimal update time complexity while matches the best known space complexity of streaming algorithms for the problem.

I&C Journal 2022 Journal Article

Linear-time parameterized algorithms with limited local resources

• Jianer Chen
• Ying Guo
• Qin Huang

We propose a new computational model for the study of massive data processing. Our model measures the complexity of reading the input data in terms of their very large size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques for solving well-known computational problems on the model. In particular, randomized algorithms of running time O ( N + g 1 ( k ) ) and space O ( k 2 ), with very high probability, are developed for the famous graph matching problem on unweighted and weighted graphs. More specifically, our algorithm for unweighted graphs finds a k-matching (i. e. , a matching of k edges) in a general unweighted graph in time O ( N + k 2. 5 ), and our algorithm for weighted graphs finds a maximum weighted k-matching in a general weighted graph in time O ( N + k 3 log ⁡ k ).

TCS Journal 2022 Journal Article

Scheduling multiple two-stage flowshops with a deadline

• Jianer Chen
• Minjie Huang
• Yin Guo

Recently, motivated by applications in cloud computing, scheduling multiple two-stage flowshops with the objective of minimizing the makespan has drawn increasing attention. Motivated by the same applications, the current paper studies the problem of scheduling multiple two-stage flowshops with a deadline, with the objective of maximizing the profit of the jobs that can be completed by the deadline. Algorithms and complexity of the problem are investigated. For the case where the number of two-stage flowshops is part of the input, we present an efficient approximation algorithm with a constant ratio. The approximation ratio is improved via a study of the relationship between the problem and the multiple knapsack problem, combined with the recent progresses in the research in approximation algorithms for the multiple knapsack problem. By integrating techniques in the study of the classical Knapsack problem and the classical Makespan problem on multiple processors, plus additional new techniques, a polynomial-time approximation algorithm with a further improved approximation ratio is developed for the case where the number of flowshops is a fixed constant.

IROS Conference 2021 Conference Paper

Manifold Trial Selection to Reduce Negative Transfer in Motor Imagery-based Brain-Computer Interface

• Zilin Liang
• Zheng Zheng 0001
• Weihai Chen
• Jianhua Wang
• Jianbin Zhang
• Jianer Chen
• Zuobing Chen

A major challenge in electroencephalogram (EEG) signal classification is that the EEG signals recorded from different subjects are drawn from different distributions. When the unlabeled EEG data of the new subject arrive, called target domain, classifying them with a classifier trained on prerecorded EEG data of other subjects, called source domain, will greatly decrease the classification accuracy. Being able to use the classifiers trained on data of source domain to accurately classify the data of target domain could reduce the time of the calibration phase in the actual application of the brain-computer interface. This study considers an offline cross-subject classification scenario. We propose a novel manifold trial selection method, which reduces the distribution distance between the source and target domains by manifold transformation and domain adaptation. The proposed method provides a trial selection strategy to suppress negative transfer by removing some abnormal samples. The proposed method is applied to the motor imagery-based brain–computer interface and compared with several existing algorithms. Experimental results show that the proposed method outperforms the state-of-the-art methods.

TCS Journal 2020 Journal Article

Improved approximation algorithms for two-stage flowshops scheduling problem

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical makespan problem, we prove that if there is an α-approximation algorithm for the makespan problem, then for the general case of the problem, we can construct a 2α-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an ( α + 1 / 2 ) -approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the makespan problem, we get a ( 2 + ϵ ) -approximation algorithm for the general case and a ( 1. 5 + ϵ ) -approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2. 6 and 11/6 respectively.

TCS Journal 2020 Journal Article

On scheduling multiple two-stage flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2. 6-approximation algorithm along with its analysis is presented for an arbitrary m ≥ 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity O ( n log ⁡ n ) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction.

TCS Journal 2019 Journal Article

Kernels for packing and covering problems

• Jianer Chen
• Henning Fernau
• Peter Shaw
• Jianxin Wang
• Zhibiao Yang

We show how the notion of combinatorial duality, related to the well-known notion of duality from linear programming, may be used for translating kernel results obtained for packing problems into kernel results for covering problems. We exemplify this approach by having a closer look at the problems of packing a graph with vertex-disjoint trees or vertex-disjoint stars with r edges. The case r = 2 has been studied in several other papers. By establishing a general notion of a crown, we show how linear-size vertex kernels can be efficiently achieved for the mentioned problems.

TCS Journal 2019 Journal Article

On scheduling inclined jobs on multiple two-stage flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

We study scheduling on multiple two-stage flowshops in which each job has to pass through an R-operation and a T-operation. Motivated by the current research in data centers, we consider two restricted versions of the problem in which the jobs are inclined: one restricts that for each job, the R-operation consumes no less time than the T-operation, while the other assumes that the T-operation consumes no less time than the R-operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case.

IJCAI Conference 2019 Conference Paper

Resolution and Domination: An Improved Exact MaxSAT Algorithm

• Chao Xu
• Wenjun Li
• Yongjie Yang
• Jianer Chen
• Jianxin Wang

We study the Maximum Satisfiability problem (MaxSAT). Particularly, we derive a branching algorithm of running time O*(1. 2989^m) for the MaxSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1. 3248^m) by Chen and Kanj [2004] published 15 years ago. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at variables of degree 4 which occur twice both positively and negatively in the given CNF formula. To serve the branching rules and shrink the size of the CNF formula, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time and, moreover, some of them solve a bottleneck of the previous best algorithm.

TCS Journal 2019 Journal Article

Resolution and linear CNF formulas: Improved (n,3)-MaxSAT algorithms

• Chao Xu
• Jianer Chen
• Jianxin Wang

We study techniques for solving the MaxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O ⁎ ( 1. 194 k ) that solves the parameterized version of the problem, and the other of running time O ⁎ ( 1. 237 n ) that solves the optimization version of the problem, both significantly improving previous best upper bounds.

TCS Journal 2019 Journal Article

Scheduling two-stage jobs on multiple flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

Scheduling two-stage jobs on multiple two-stage flowshops is studied. A new formulation for configurations of the scheduling is proposed, leading directly to improvements on complexity of scheduling algorithms for the problem. Motivated by observations in practice, we present a deeper study on the structures of the problem that leads to a new approach that gives very significant improved scheduling algorithms for the problem when the costs of the two stages differ significantly.

TCS Journal 2017 Journal Article

Dealing with 4-variables by resolution: An improved MaxSAT algorithm

• Jianer Chen
• Chao Xu
• Jianxin Wang

We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time O ⁎ ( 1. 3248 k ) for the MaxSAT problem, improving the previous best upper bound O ⁎ ( 1. 358 k ) by Ivan Bliznets and Alexander Golovnev.

I&C Journal 2017 Journal Article

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

• Wenjun Li
• Yixin Cao
• Jianer Chen
• Jianxin Wang

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an O ⁎ ( 8 k ) -time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time O ⁎ ( 4 k ). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1. 5 for the problem.

TCS Journal 2017 Journal Article

Improved kernel results for some FPT problems based on simple observations

• Wenjun Li
• Qilong Feng
• Jianer Chen
• Shuai Hu

In this paper, we study the kernelization algorithms for several parameterized problems, including Parameterized Co-Path Set problem, Parameterized Path-Contractibility problem and Parameterized Connected Dominating Set on G 7 Graphs problem. Based on simple observations, we give simple kernelization algorithms with kernel sizes 4k, 3 k + 4, and O ( k 2 ), respectively, which improves the previous best results 6k, 5 k + 3, and O ( k 3 ), respectively.

TCS Journal 2017 Journal Article

Partition on trees with supply and demand: Kernelization and algorithms

• Mugang Lin
• Qilong Feng
• Jianer Chen
• Wenjun Li

Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O ( k 2 ) for the problem. Based on branching technique, a parameterized algorithm of running time O ⁎ ( 2. 828 k ) is presented.

TCS Journal 2015 Journal Article

Edge deletion problems: Branching facilitated by modular decomposition

• Yunlong Liu
• Jianxin Wang
• Jie You
• Jianer Chen
• Yixin Cao

Edge deletion problems ask for a minimum set of edges whose deletion makes a graph have a certain property. When this property can be characterized by a finite set of forbidden induced subgraphs, the problem can be solved in fixed-parameter time by a naive bounded search tree algorithm. Sometimes deleting an edge to break an erstwhile forbidden induced subgraph might introduce new ones, which may involve the neighbors of the original forbidden induced subgraph. Therefore, in considering possible ways to break a forbidden induced subgraph one naturally takes its neighborhood into consideration. This observation easily yields more efficient branching rules, but a naive implementation will require too many tedious case analyses. Here we take advantage of modular decomposition, which allows us to focus on far simpler quotient graphs instead of the original graphs. They together yield simple improved algorithms for the edge deletion problems to chain graphs and trivially perfect graphs.

TCS Journal 2015 Journal Article

Frontiers of Algorithmics

• Jianer Chen
• John E. Hopcroft

TCS Journal 2015 Journal Article

Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees

• Jianer Chen
• Jia-Hao Fan
• Sing-Hoi Sze

We study parameterized algorithms and approximation algorithms for the maximum agreement forest problem, which, for two given leaf-labeled trees, is to find a maximum forest that is a subgraph of both trees. The problem was motivated by research in phylogenetics. For parameterized algorithms, while the problem is known to be fixed-parameter tractable for binary trees, it was an open problem whether the problem is still fixed-parameter tractable for general trees. We resolve this open problem by developing an O ( 3 k n ) -time parameterized algorithm for general trees. Our techniques on tree structures also lead to a polynomial-time approximation algorithm of ratio 3 for the problem, giving the first constant-ratio approximation algorithm for general trees.

TCS Journal 2015 Journal Article

Parameterized complexity of control and bribery for d-approval elections

• Jianxin Wang
• Weimin Su
• Min Yang
• Jiong Guo
• Qilong Feng
• Feng Shi
• Jianer Chen

A d-Approval election consists of a set C of candidates and a set V of votes, where each vote v can be presented as a set of d candidates. For a vote v ∈ V, the d-Approval voting protocol assigns one point to each candidate in v. The candidate getting the most points from all votes wins the election. An important aspect of studying election systems is the strategic behavior such as control and bribery problems. The control by deleting votes problem decides whether for a given election ( C, V ), a specific candidate c, and an integer k, it is possible to delete at most k votes such that c wins the resulting election. In the control by adding votes setting, one has two sets V and U of votes and asks for a subset U ′ ⊆ U such that | U ′ | ≤ k and c becomes the winner in V ∪ U ′. The bribery problem has the same input as the vote deleting control problem and asks for changing at most k votes to make c win. All three problems have been shown NP-hard. We initialize the study of the parameterized complexity of these problems and present a collection of tractability and intractability results. In particular, we derive a polynomial-size problem kernel for the standard parameterization of the control by deleting votes problem, the seemingly first non-trivial problem kernel for the control problem of elections.

TCS Journal 2014 Journal Article

Algorithms for parameterized maximum agreement forest problem on multiple trees

• Feng Shi
• Jianxin Wang
• Jianer Chen
• Qilong Feng
• Jiong Guo

The Maximum Agreement Forest problem (MAF) asks for a largest common subforest of a collection of phylogenetic trees. The MAF problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we present a group of fixed-parameter tractable algorithms for the MAF problem on multiple (i. e. , two or more) binary phylogenetic trees. Our techniques work fine for the problem for both rooted trees and unrooted trees. The computational complexity of our algorithms is comparable with that of the known algorithms for two trees, and is independent of the number of phylogenetic trees for which a maximum agreement forest is constructed.

TCS Journal 2014 Journal Article

Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

• Qilong Feng
• Jianxin Wang
• Chao Xu
• Jinyi Yao
• Jianer Chen

The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R d (d-RSP), for a given set S of n points in R d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time O ⁎ ( ( 1 + 1 + 4 ( d − 1 ) 2 ) k ) is given for the Constrained d-RSP problem, which significantly improves the current best result O ⁎ ( ( 0. 74 d k ) k ).

TCS Journal 2014 Journal Article

Matching and Weighted P 2 -Packing: Algorithms and Kernels

• Qilong Feng
• Jianxin Wang
• Jianer Chen

Parameterized algorithms and kernelization algorithms are presented for the weighted P 2 -Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the following new techniques and observations: (1) new study on structure relationship between graph matchings in general graphs and P 2 -packings in bipartite graphs; (2) an effective graph bi-partitioning algorithm; and (3) a polynomial-time algorithm for a constrained weighted P 2 -Packing problem in bipartite graphs. The kernelization algorithms are based on the following new techniques: (1) the application of graph matching in kernelization; (2) a crown reduction structure for weighted problems. These techniques lead to randomized and deterministic parameterized algorithms that significantly improve the previous best upper bounds for the problem for both weighted and unweighted versions. For the kernelization algorithm, by using a weighted version of crown reduction, a kernel of size O ( k 2 ) is presented, where k is the given parameter of the problem.

TCS Journal 2014 Journal Article

Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks

• Weizhong Luo
• Jianxin Wang
• Jiong Guo
• Jianer Chen

Max-lifetime Target Coverage can be viewed as a family of problems where the task is to partition the sensors into groups and assign their time-slots such that the coverage lifetime is maximized while satisfying some coverage requirement. Unfortunately, these problems are NP-hard. To gain insight into the source of the complexity, we initiate a systematic parameterized complexity study of two types of Max-lifetime Target Coverage: Max–min Target Coverage and Max-individual Target Coverage. We first prove that both problems remain NP-hard even in the special cases where each target is covered by at most two sensors or each sensor can cover at most two targets. By contrast, restricting the number of targets reduces the complexity of the considered problems. In other words, they are both fixed parameter tractable (FPT) with respect to the parameter “number of targets”. Moreover, we extend our studies to the structural parameter “number k of sensors covering at least two targets”. Positively, both problems are in FPT with respect to k. Finally, we show that Max–min Target Coverage is in FPT with respect to the combined parameters “number of groups” and “number of targets covered by each group”.

TCS Journal 2013 Journal Article

Improved linear problem kernel for planar connected dominating set

• Weizhong Luo
• Jianxin Wang
• Qilong Feng
• Jiong Guo
• Jianer Chen

In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph G = ( V, E ) and a non-negative integer k, asks for a subset D ⊆ V with ∣ D ∣ ≤ k such that D forms a dominating set of G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most 130 k vertices, improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size.

TCS Journal 2013 Journal Article

Parameterized top- K algorithms

• Jianer Chen
• Iyad A. Kanj
• Jie Meng
• Ge Xia
• Fenghui Zhang

We study algorithmic techniques that produce the best K solutions to an instance of a parameterized NP-hard problem whose solutions are associated with a scoring function. Our parameterized top- K algorithms proceed in two stages. The first stage is a structure algorithm that on a problem instance constructs a structure of feasible size, and the second stage is an enumerating algorithm that produces the K best solutions to the instance based on the structure. We show that many algorithm-design techniques for parameterized algorithms, such as branch-and-search, color coding, and bounded treewidth, can be adopted for designing efficient structure algorithms. We then develop new techniques that support efficient enumerating algorithms. In particular, we show that for a large class of well-known NP optimization problems, there are parameterized top- K algorithms that produce the best K solutions for the problems in feasible amount of average time per solution when the parameter value is small. Finally, we investigate the relation between fixed-parameter tractability and parameterized top- K algorithms.

TCS Journal 2012 Journal Article

Complexity and parameterized algorithms for Cograph Editing

• Yunlong Liu
• Jianxin Wang
• Jiong Guo
• Jianer Chen

Cograph Editing is to find for a given graph G = ( V, E ) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O ( 4. 61 2 k + | V | 4. 5 ), which improves the trivial algorithm of running time O ( 6 k + | V | 4. 5 ).

TCS Journal 2011 Journal Article

Algorithms, complexity and computational models

• Jianer Chen
• S. Barry Cooper

TCS Journal 2011 Journal Article

An O ∗ ( 3.5 3 3 k ) -time parameterized algorithm for the 3-set packing problem

• Jianxin Wang
• Qilong Feng
• Jianer Chen

A parameterized algorithm for the well-known NP-complete problem 3-set packing is presented. The algorithm is based on the following new approaches: (1) an efficient algorithm for problem instances in which one element is known for each of the 3-sets in a solution packing (i. e. , type-1 instances); (2) an efficient algorithm for problem instances in which at least two elements are known for each of the 3-sets in a solution packing (i. e. , type-2 instances); and (3) an effective decomposition of a general instance of 3-set packing into two instances of type-1 and type-2, respectively, whose base sets are disjoint. This technique results in an improved parameterized algorithm of running time O ∗ ( 3. 5 3 3 k ) for the 3-set packing problem, improving the previous best upper bound O ∗ ( 4. 6 1 3 k ).

TCS Journal 2011 Journal Article

Improved deterministic algorithms for weighted matching and packing problems

• Jianer Chen
• Qilong Feng
• Yang Liu
• Songjian Lu
• Jianxin Wang

Based on the method of ( n, k ) -universal sets, we present a deterministic parameterized algorithm for the weighted r d-matching problem with time complexity O ∗ ( 4 ( r − 1 ) k + o ( k ) ), improving the previous best upper bound O ∗ ( 4 r k + o ( k ) ). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O ∗ ( 1 6 k + o ( k ) ), improving the previous best result O ∗ ( 21. 2 6 k ). For the weighted r -set packing problem, we present a deterministic parameterized algorithm with time complexity O ∗ ( 2 ( 2 r − 1 ) k + o ( k ) ), improving the previous best result O ∗ ( 2 2 r k + o ( k ) ). The algorithm, when applied to the unweighted 3-set packing problem, has running time O ∗ ( 3 2 k + o ( k ) ), improving the previous best result O ∗ ( 43. 6 2 k + o ( k ) ). Moreover, for the weighted r -set packing and weighted r d-matching problems, we give a kernel of size O ( k r ), which is the first kernelization algorithm for the problems on weighted versions.

MFCS Conference 2011 Conference Paper

Linear Problem Kernels for Planar Graph Problems with Small Distance Property

• Jianxin Wang 0001
• Yongjie Yang 0001
• Jiong Guo
• Jianer Chen

Abstract Recently, various linear problem kernels for NP-hard planar graph problems have been achieved, finally resulting in a meta-theorem for classification of problems admitting linear kernels. Almost all of these results are based on a so-called region decomposition technique. In this paper, we introduce a simple partition of the vertex set to analyze kernels for planar graph problems which admit the distance property with small constants. Without introducing new reduction rules, this vertex partition directly leads to improved kernel sizes for several problems. Moreover, we derive new kernelization algorithms for Connected Vertex Cover, Edge Dominating Set, and Maximum Triangle Packing problems, further improving the kernel size upper bounds for these problems.

TCS Journal 2010 Journal Article

A parameterized algorithm for the hyperplane-cover problem

• Jianxin Wang
• Wenjun Li
• Jianer Chen

We consider the problem of covering a given set of points in the Euclidean space R m by a small number k of hyperplanes of dimensions bounded by d, where d ≤ m. We present a very simple parameterized algorithm for the problem, and give thorough mathematical analysis to prove the correctness and derive the complexity of the algorithm. When the algorithm is applied on the standard hyperplane-cover problem in R d, it runs in time O ∗ ( k ( d − 1 ) k / 1. 3 k ), improving the previous best algorithm of running time O ∗ ( k d k + d ) for the problem. When the algorithm is applied on the line-cover problem in R 2, it runs in time O ∗ ( k k / 1. 3 5 k ), improving the previous best algorithm of running time O ∗ ( k 2 k / 4. 8 4 k ) for the problem.

TCS Journal 2010 Journal Article

Improved upper bounds for vertex cover

• Jianer Chen
• Iyad A. Kanj
• Ge Xia

This paper presents an O ( 1. 273 8 k + k n ) -time polynomial-space algorithm for Vertex Cover improving the previous O ( 1. 28 6 k + k n ) -time polynomial-space upper bound by Chen, Kanj, and Jia. Most of the previous algorithms rely on exhaustive case-by-case branching rules, and an underlying conservative worst-case-scenario assumption. The contribution of the paper lies in the simplicity, uniformity, and obliviousness of the algorithm presented. Several new techniques, as well as generalizations of previous techniques, are introduced including: general folding, struction, tuples, and local amortized analysis. The algorithm also improves the O ( 1. 274 5 k k 4 + k n ) -time exponential-space upper bound for the problem by Chandran and Grandoni.

TCS Journal 2009 Journal Article

On parameterized exponential time complexity

• Jianer Chen
• Iyad A. Kanj
• Ge Xia

In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2 o ( f ( k ) ) p ( n ) time if and only if it is solvable in time O ( 2 δ f ( k ) q ( n ) ) for any constant δ > 0, where p and q are polynomials. We then illustrate how this equivalence can be used to show that special instances of parameterized NP-hard problems are as difficult as the general instances. For example, we show that the Planar Dominating Set problem on degree-3 graphs can be solved in 2 o ( k ) p ( n ) parameterized time if and only if the general Planar Dominating Set problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well.

TCS Journal 2009 Journal Article

On the pseudo-achromatic number problem

• Jianer Chen
• Iyad A. Kanj
• Jie Meng
• Ge Xia
• Fenghui Zhang

We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter k, determine if the graph can be partitioned into k groups such that every two groups are connected by at least one edge. This problem has been extensively studied in graph theory and combinatorial optimization. We show that the problem has a kernel of at most ( k − 2 ) ( k + 1 ) vertices that is constructable in time O ( m n ), where n and m are the number of vertices and edges, respectively, in the graph, and k is the parameter. This directly implies that the problem is fixed-parameter tractable. We also study generalizations of the problem and show that they are parameterized intractable.

STOC Conference 2008 Conference Paper

A fixed-parameter algorithm for the directed feedback vertex set problem

• Jianer Chen
• Yang Liu 0002
• Songjian Lu
• Barry O'Sullivan
• Igor Razgon

The (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph G and a parameter k, either construct a feedback vertex set of at most k vertices in G or report that no such set exists. Whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)n O(1) for some function f. In this paper we develop new algorithmic techniques that result in an algorithm with running time 4 k k! n O(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.

SODA Conference 2007 Conference Paper

Improved algorithms for path, matching, and packing problems

• Jianer Chen
• Songjian Lu
• Sing-Hoi Sze
• Fenghui Zhang

MFCS Conference 2006 Conference Paper

Improved Parameterized Upper Bounds for Vertex Cover

• Jianer Chen
• Iyad A. Kanj
• Ge Xia

Abstract This paper presents an O (1. 2738 k + kn )-time polynomial-space parameterized algorithm for Vertex Cover improving the previous O (1. 286 k + kn )-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the O (1. 2745 k k 4 + kn )-time exponential-space upper bound for the problem by Chandran and Grandoni.

TCS Journal 2006 Journal Article

On product covering in 3-tier supply chain models: Natural complete problems for W [ 3 ] and W [ 4 ]

• Jianer Chen
• Fenghui Zhang

The field of supply chain management has been growing at a rapid pace in recent years, both as a research area and as a practical discipline. In this paper, we study the computational complexity of product covering problems in 3-tier supply chain models, and present natural complete problems for the classes W [ 3 ] and W [ 4 ] in parameterized complexity theory. This seems the first group of natural complete problems for higher levels in the parameterized intractability hierarchy (i. e. , the W -hierarchy), and the first precise complexity characterizations of certain optimization problems in the research of supply chain management. Our results also derive strong computational lower bounds and inapproximability for these optimization problems.

TCS Journal 2005 Journal Article

On approximating minimum vertex cover for graphs with perfect matching

• Jianer Chen
• Iyad A. Kanj

It has been a challenging open problem whether there is a polynomial time approximation algorithm for the VERTEX COVER problem whose approximation ratio is bounded by a constant less than 2. In this paper, we study the VERTEX COVER problem on graphs with perfect matching (shortly, VC-PM). We show that if the VC-PM problem has a polynomial time approximation algorithm with approximation ratio bounded by a constant less than 2, then so does the VERTEX COVER problem on general graphs. Approximation algorithms for VC-PM are developed, which induce improvements over previously known algorithms on sparse graphs. For example, for graphs of average degree 5, the approximation ratio of our algorithm is 1. 414, compared with the previously best ratio 1. 615 by Halldórsson and Radhakrishnan.

I&C Journal 2005 Journal Article

Tight lower bounds for certain parameterized NP-hard problems

• Jianer Chen
• Benny Chor
• Mike Fellows
• Xiuzhen Huang
• David Juedes
• Iyad A. Kanj
• Ge Xia

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n o(k) m O(1), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t −1)-st level W[t −1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set, set cover, and feature set, cannot be solved in time n o(k) m O(1), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q -sat (for any fixed q ⩾2), clique, independent set, and dominating set, cannot be solved in time n o(k) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n k m O(1) or O(n k ).

STOC Conference 2004 Conference Paper

Linear FPT reductions and computational lower bounds

• Jianer Chen
• Xiuzhen Huang
• Iyad A. Kanj
• Ge Xia

We develop new techniques for deriving very strong computational lower bounds for a class of well-known NP-hard problems, including weighted satisfiability , dominating set , hitting set , set cover , clique , and independent set . For example, although a trivial enumeration can easily test in time O(n k ) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k) n o(k) for any function f, even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be Θ(μ(n)) for any reasonable function μ, no algorithm of running time n o(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds are also derived for other problems in the above class. Our techniques can be extended to derive computational lower bounds on approximation algorithms for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/ε)n o(1/ε) for any function f unless an unlikely collapse occurs in parameterized complexity theory.

MFCS Conference 2004 Conference Paper

Polynomial Time Approximation Schemes and Parameterized Complexity

• Jianer Chen
• Xiuzhen Huang
• Iyad A. Kanj
• Ge Xia

Abstract In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce the notion of efficient fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is efficiently fixed-parameter tractable. By enforcing a constraint of planarity on the W -hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W -hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS).

STOC Conference 1999 Conference Paper

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract)

• Jianer Chen
• Antonio Miranda

TCS Journal 1997 Journal Article

Algorithmic graph embeddings

• Jianer Chen

The complexity of embedding a graph into a variety of topological surfaces is investigated. A new data structure for graph embeddings is introduced and shown to be superior to the previously known data structures. In particular, the new data structure efficiently supports all on-line operations for general graph embeddings. Based on this new data structure, very efficient algorithms are developed to solve the problem “given a graph G and an integer k, construct a genus k embedding for the graph G” for a large range of integers k and for a large class of graphs G.

TCS Journal 1995 Journal Article

On input read-modes of alternating Turing machines

• Liming Cai
• Jianer Chen

A number of input read-modes of Turing machines have appeared in the literature. To investigate the differences among these input read-modes, we study log-time alternating Turing machines of constant alternations. For each fixed integer k ⩾ 1 and for each read-mode, a precise circuit characterization is established for log-time alternating Turing machines of k alternations, which is a nontrivial refinement of Ruzzo's circuit characterization of alternating Turing machines. These circuit characterizations indicate clearly the differences among the input read-modes. Complete languages in strong sense for each level of the log-time hierarchy are presented, refining a result by Buss. An application of these results to computational optimization problems is described.

MFCS Conference 1993 Conference Paper

On the Amount of Nondeterminism and the Power of Verifying (Extended Abstract)

• Liming Cai
• Jianer Chen

Abstract The relationship between nondeterminism and other computational resources is studied based on a special interactive-proof system model GC. Let s ( n ) be a function and C be a complexity class. Define GC ( s ( n ), C ) to be the class of languages that are accepted by verifiers in C that can make an extra O ( s ( n )) amount of nondeterminism. Our main results are (1) A systematic technique is developed to show that for many functions s ( n ) and for many complexity classes C, the class GC ( s ( n ), C ) has natural complete languages; (2) The class ∏ 0 h of languages accepted by log-time alternating Turing machines making h alternations is precisely the class of languages accepted by uniform families of circuits of depth h; (3) The classes GC ( s ( n ), II h 0 ), h ≥ 1, characterize precisely the fixed-parameter intractability of NP -hard optimization problems. In particular, the (2 h )th level W [2 h ] of W -hierarchy introduced by Downey and Fellows collapses if and only if \(GC(s(n), \prod _{2h}^0 ) \subseteq P\) for some s ( n )= ω (log n ).

FOCS Conference 1991 Conference Paper

On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract)

• Arkady Kanevsky
• Roberto Tamassia
• Giuseppe Di Battista
• Jianer Chen

Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for k >