A subexponential parameterized algorithm for proper interval completion

DOI10.1007/978-3-662-44777-2_15MaRDI QIDQ5891808zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk, I. A. Bliznets

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3472

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in $O(16^k(n+m))$ time. In this paper we present an algorithm with running time $k^{O(k^{2/3})}+O(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

Recommendations

• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Subexponential parameterized algorithm for interval completion
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Polynomial kernels for proper interval completion and related problems
• Polynomial kernels for proper interval completion and related problems

Cited in

(9)

• Polynomial kernelization for removing induced claws and diamonds
• Exploring the subexponential complexity of completion problems
• Polynomial kernels for proper interval completion and related problems
• Interval Completion Is Fixed Parameter Tractable
• Polynomial kernels for proper interval completion and related problems
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Subexponential parameterized algorithm for interval completion
• Paths to trees and cacti
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: A subexponential parameterized algorithm for proper interval completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891808)