Subexponential parameterized algorithm for interval completion

DOI10.1137/1.9781611974331.CH78MaRDI QIDQ4575658zbMATH OpenOpenAlexFDO

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

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In the 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 an interval graph, i.e., a graph admitting an intersection model of intervals on a line. Motivated by applications in sparse matrix multiplication and molecular biology, Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] asked for a fixed-parameter algorithm solving this problem. This question was answer affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time $O(k^{2k}{n}^{3}m)$. We give the first subexponential parameterized algorithm solving Interval Completion in time $k^{O(sqrtk)}{n}^{O(1)}$. This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.

Recommendations

• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• A subexponential parameterized algorithm for proper interval completion
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Interval Completion Is Fixed Parameter Tractable
• An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem

Cited in

(10)

• A Subexponential Parameterized Algorithm for Proper Interval Completion
• Subexponential parameterized algorithm for {\textsc{Interval Completion}}
• Approximation and kernelization for chordal vertex deletion
• Rank reduction of oriented graphs by vertex and edge deletions
• scientific article; zbMATH DE number 7053390 (Why is no real title available?)
• A subexponential parameterized algorithm for proper interval completion
• Subexponential parameterized algorithms
• Interval Completion Is Fixed Parameter Tractable
• Polynomial kernelization for removing induced claws and diamonds
• Linear-time minimal cograph editing

This page was built for publication: Subexponential parameterized algorithm for interval completion

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