1 citations · 1 across the 6 of their papers we have counts for
5 papers · 1 filter
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…