7 papers
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…
Feedback Set Problems on Bounded-Degree (Planar) Graphs
Tian Bai, Yixin Cao, Mingyu Xiao
The feedback set problems are about removing the minimum number of vertices or edges from a graph to break all its cycles. Much effort has gone into understanding their complexity…
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 Complexity of Tournament Fixing: Subset FAS Number and Acyclic Neighborhoods
Yuxi Liu, Junqiang Peng, Mingyu Xiao
The \textsc{Tournament Fixing Problem} (TFP) asks whether a knockout tournament can be scheduled to guarantee that a given player wins. Although TFP is NP-hard in general, it…
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…