7 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…
Polynomial Kernels for Interval Completion
Zimo Sheng, Tian Bai, Mingyu xiao
An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval g…
A Polynomial Kernel for Planar Directed Feedback Vertex Set
Zimo Sheng, Mingyu Xiao
The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most vertices. Whether DFVS admits a polynomial kernel parameterized b…
A Near-Linear Element Kernel for \(d\)-Hitting Set
Zimo Sheng, Mingyu Xiao
In \(d\)-\textsc{Hitting Set}, the input consists of a finite universe \(U\), a family \(\mathcal S\) of subsets of \(U\) with size at most \(d\), and an integer \(k\). The task is…
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…
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…