pipette
ENEnglish

Polynomial Kernels for Interval Completion

Zimo Sheng, Tian Bai, Mingyu xiao

PreprintDice ser un gran avance

En palabras de los autores

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 graph by adding at most edges. Although the problem is fixed-parameter tractable when parameterized by , whether it admits a polynomial kernel has long been an open question. We resolve this question by giving the first polynomial kernel for \textsc{Interval Completion}. Our main contribution is a parameter-preserving polynomial-time reduction from \textsc{Interval Completion} to \textsc{Odd Cycle Transversal} (OCT). Combining this reduction with the known randomized and deterministic polynomial kernels for OCT and a polynomial-time reduction back to \textsc{Interval Completion}, we obtain a randomized kernel with vertices and edges, and a deterministic kernel with vertices and edges. Here, suppresses polylogarithmic factors in .

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.