1 citations · 1 across the 6 of their papers we have counts for
8 papers
Solving Restricted Versions of #SAT Faster than : Algorithms and Lower Bounds
Sanjay Jain, Junqiang Peng, Frank Stephan +1
Under the Strong Exponential Time Hypothesis (SETH), for any constant , the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be…
New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
Sanjay Jain, Junqiang Peng, Frank Stephan +2
Parity-SAT is the problem of determining whether a given CNF formula has an odd number of satisfying assignments. As a canonical P-complete problem, it represents a fundame…
Faster Parameterized Vertex Multicut
Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3
In the {\sc Vertex Multicut} problem the input consists of a graph , integer , and a set of pairs of vertices of . The ta…
The Role of Degrees and Acyclic Neighborhoods in the Complexity of Tournament Fixing
Yuxi Liu, Junqiang Peng, Mingyu Xiao +1
The \textsc{Tournament Fixing} problem asks whether a knockout tournament can be scheduled to make a favorite player win when all pairwise match outcomes are given. Such tournament…
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 +1
In knockout tournaments, players compete in successive rounds, with losers eliminated and winners advancing until a single champion remains. Given a tournament digraph , which e…
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. propo…
Systematic Parameter Decision in Approximate Model Counting
Jinping Lei, Toru Takisaka, Junqiang Peng +1
This paper proposes a novel approach to determining the internal parameters of the hashing-based approximate model counting algorithm . In this problem, the chos…
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 time, where is the length of the input CNF-formula (i.e., the total number…