7 papers
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 #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…
Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
Jingyang Zhao, Zimo Sheng, Mingyu Xiao
The Traveling Salesman Problem (TSP) is a classic and extensively studied problem with numerous real-world applications in artificial intelligence and operations research. It is we…
A Discharging Method: Improved Kernels for Edge Triangle Packing and Covering
Zimo Sheng, Mingyu Xiao
\textsc{Edge Triangle Packing} and \textsc{Edge Triangle Covering} are dual problems extensively studied in the field of parameterized complexity. Given a graph and an integer…
Extracting Densest Sub-hypergraph with Convex Edge-weight Functions
Yi Zhou, Shan Hu, Zimo Sheng
The densest subgraph problem (DSG) aiming at finding an induced subgraph such that the average edge-weights of the subgraph is maximized, is a well-studied problem. However, when t…