Polynomial kernels enable efficient interval graph completion problem
Polynomial Kernels for Interval Completion
Data Structures and AlgorithmsComputational Complexity
Summary
This paper looks at the challenge of changing a messy network into a special kind called an interval graph by adding a limited number of connections. The authors show a way to simplify this problem down to a smaller, easier one using known methods for a related problem called Odd Cycle Transversal. By doing this, they created a process that shrinks the problem size significantly while keeping it accurate. This advances previous work by confirming that this shrinking (called polynomial kernelization) is possible for interval completion.
What this means in practice
- •For network engineers: Simplify processing of network topology changes by efficiently recognizing interval graph structures.
- •For database administrators: Enhance query optimization by quickly approximating interval representations of data relationships.
A theory result. No direct application yet.
Authors
Zimo Sheng, Tian Bai, Mingyu xiao
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$.