A Deterministic Polynomial Kernel for Odd Cycle Transversal
En palabras de los autores
We give a deterministic polynomial kernel for Odd Cycle Transversal, derandomizing the randomized kernel of Kratsch and Wahlstr\"om (TALG 2014). Our algorithm uses a deterministic polynomial-time construction of almost multilinear representations of gammoids. Such a representation assigns a block of columns to each element so that, for every subset of elements, the normalized matrix rank approximates its matroid rank to within a prescribed additive error . The construction builds on recent breakthroughs in NC algorithms for matching. Our kernelization algorithm then computes the required representative families from these representations.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.