History

Please fill in your query. A complete syntax description you will find on the General Help page.
Polynomial kernels for proper interval completion and related problems. (English)
Owe, Olaf (ed.) et al., Fundamentals of computation theory. 18th international symposium, FCT 2011, Oslo, Norway, August 22‒25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22952-7/pbk). Lecture Notes in Computer Science 6914, 229-239 (2011).
Summary: Given a graph $G = (V,E)$ and a positive integer $k$, the Proper Interval Completion problem asks whether there exists a set $F$ of at most $k$ pairs of $(V \times V) \setminus E$ such that the graph $H = (V, E \cup F)$ is a proper interval graph. The Proper Interval Completion problem finds applications in molecular biology and genomic research [11]. First announced by Kaplan, Tarjan and Shamir in FOCS ’94, this problem is known to be FPT [11], but no polynomial kernel was known to exist. We settle this question by proving that Proper Interval Completion admits a kernel with $O(k ^{5})$ vertices. Moreover, we prove that a related problem, the so-called Bipartite Chain Deletion problem admits a kernel with $O(k ^{2})$ vertices, completing a previous result of Guo [10].