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.CC2026
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…
cs.IT2026
On the Leaky Private Information Retrieval with Side Information
Yingying Huangfu, Tian Bai
This paper investigates the problem of Leaky Private Information Retrieval with Side Information (L-PIR-SI), providing a fundamental characterization of the trade-off among leaky p…