arXiv preprint ·
Polynomial Kernels for Interval Completion
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $k$ edges. Although the problem is fixed-parameter tractable when parameterized by $k$, 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 $\widetilde O(k^{18})$ vertices and $\widetilde O(k^{36})$ edges, and a deterministic kernel with $O(k^{36})$ vertices and $O(k^{72})$ edges. Here, $\widetilde O$ suppresses polylogarithmic factors in $k$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Quantum Approximation Complexity of Classical Optimization Problems
A QPTAS for Stochastic Scheduling of Bernoulli Jobs
A deterministic algorithm for signing bipartite graphs at the Ramanujan bound
A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds
The Multiple Unicast Conjecture is False
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.