Showing 2026Show all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
A Near-Linear Element-Kernel for \(d\)-Hitting Set
Zimo Sheng, Mingyu Xiao
In \(d\)-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 to decid…