Author name cluster

Junqiang Peng

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

TCS Journal 2026 Journal Article

A Fast Algorithm for Maximum Satisfiability above Half Number of Clauses

Junqiang Peng
Mingyu Xiao

We study the following parameterization of the MaxSAT problem: Given a CNF formula with m clauses, decide whether at least m/2 + μ clauses in the formula could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspective is known as the above guarantee parameterization. Since its introduction by Mahajan and Raman in 1999, the analysis of parameterization above guarantee has become a highly active and fruitful line of research. In this paper, we develop a new algorithm with runtime O*(2.1479^μ), significantly improving the previous best upper bound O*(5.4064^μ).

Details DOI

AAAI Conference 2026 Conference Paper

How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?

Zhonghao Wang
Junqiang Peng
Yuxi Liu
Mingyu Xiao

In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph D, which encodes the outcomes of all possible matches, and a designated player v* in V(D), the Tournament Fixing problem (TFP) asks whether the tournament can be scheduled in a way that guarantees v* emerges as the winner. TFP is known to be NP-hard, but is fixed-parameter tractable (FPT) when parameterized by structural measures such as the feedback arc set (fas) or feedback vertex set (fvs) number of the tournament digraph. In this paper, we introduce and study two new structural parameters: the number of players who can defeat v* (i.e., the in-degree of v*, denoted by k) and the number of players that v* can defeat (i.e., the out-degree of v*, denoted by l). A natural question is that: can TFP be efficiently solved when k or l is small? We answer this question affirmatively by showing that TFP is FPT when parameterized by either the in-degree or out-degree of v*. Our algorithm for the in-degree parameterization is particularly involved and technically intricate. Notably, the in-degree k can remain small even when other structural parameters, such as fas or fvs, are large. Hence, our results offer a new perspective and significantly broaden the parameterized algorithmic understanding of the Tournament Fixing problem.

PDF Details DOI

TCS Journal 2025 Journal Article

Fast exact algorithms for the SAT problem with bounded occurrences of variables

Junqiang Peng
Mingyu Xiao

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O ⁎ ( c d n ), where c d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d = 3 and d = 4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O ⁎ ( 1. 1238 n ) for d = 3 and O ⁎ ( 1. 2628 n ) for d = 4, improving the previous results O ⁎ ( 1. 1279 n ) and O ⁎ ( 1. 2721 n ) obtained by Wahlström (SAT 2005) nearly 20 years ago. For d ≥ 5, we obtain a running time bound of O ⁎ ( 1. 0641 d n ), implying a bound of O ⁎ ( 1. 0641 L ) with respect to the formula length L.

Details DOI

AAAI Conference 2025 Conference Paper

Improved Approximation Algorithms for Clustered TSP and Subgroup Planning

Jingyang Zhao
Mingyu Xiao
Junqiang Peng
Ziliang Xiong

In the Clustered TSP (CTSP), we are given an edge-weighted graph satisfying the triangle inequality property, and a family of pairwise disjoint vertex groups. The goal is to find a minimum weight tour that includes all vertices, ensuring that the vertices within each group appear consecutively on the tour. The subgroup planning problem (SGPP) is an extension of CTSP by relaxing some triangle inequality requirements on edge weights. CTSP and SGPP have plentiful applications in AI and robotics. In this paper, we design three improved approximation algorithms for SGPP and CTSP. First, we propose a polynomial-time 2.167-approximation algorithm for SGPP, improving the previous ratio of 3 (IJCAI 2017). Second, we give an FPT 2.072-approximation algorithm for SGPP parameterized by the maximum group size, improving the previous ratio of 2.5 (IJCAI 2017). Third, we prove an FPT (β<1.5)-approximation algorithm for SGPP parameterized by the number of groups, which even improves the previous ratio 1.667 for CTSP (ORL 1999). We also conduct experiments to evaluate the performance of our algorithms.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

New Algorithms for #2-SAT and #3-SAT

Junqiang Peng
Zimo Sheng
Mingyu Xiao

The #2-SAT and #3-SAT problems involve counting the number of satisfying assignments (also called models) for instances of 2-SAT and 3-SAT, respectively. In 2010, Zhou et al. (https: //doi. org/10. 1609/aaai. v24i1. 7537) proposed an O*(1. 1892^m)-time algorithm for #2-SAT and an efficient approach for #3-SAT, where m denotes the number of clauses. In this paper, we show that the weighted versions of #2-SAT and #3-SAT can be solved in O*(1. 1082^m) and O*(1. 4423^m) time, respectively. These results directly apply to the unweighted cases and achieve substantial improvements over the previous results. These advancements are enabled by the introduction of novel reduction rules, a refined analysis of branching operations, and the application of path decompositions on the primal and dual graphs of the formula.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

A Fast Algorithm for MaxSAT above Half Number of Clauses

Junqiang Peng
Mingyu Xiao

We study the following parameterization of the MaxSAT problem: Given a CNF formula F with m clauses, decide whether at least m/2 + μ clauses in F could be satisfied, where μ is the excess of the number of satisfied clauses over the trivial lower bound m/2 and is taken as the parameter. This perspective is known as the "above guarantee" parameterization. Since its introduction by Mahajan and Raman [1999], the analysis of parameterization above guarantee has become a highly active and fruitful line of research. In this paper, we develop a new algorithm with runtime O*(2. 1479^μ), significantly improving the previous best upper bound O*(5. 4064^μ) for this important problem. Here, the O* notation omits polynomial factors.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Fast Algorithms for SAT with Bounded Occurrences of Variables

Junqiang Peng
Mingyu Xiao

We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*({c_d}^n), where c_d is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and n is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d=3 and d=4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O*(1. 1238^n) for d=3 and O*(1. 2628^n) for d=4, improving the previous results O*(1. 1279^n) and O*(1. 2721^n) obtained by Wahlström (SAT 2005) nearly 20 years ago. For d>=5, we obtain a running time bound of O*(1. 0641^{dn}), implying a bound of O*(1. 0641^L) with respect to the formula length L, which is also a slight improvement over the previous bound.

PDF Details DOI

I&C Journal 2023 Journal Article

Further improvements for SAT in terms of formula length

Junqiang Peng
Mingyu Xiao

In this paper, we prove that the general CNF satisfiability problem can be solved in O ⁎ ( 1. 0638 L ) time, where L is the length of the input CNF-formula (i. e. , the total number of literals in the formula), which improves the previous result of O ⁎ ( 1. 0652 L ) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks; we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method.

Details DOI