Linear recognition of almost interval graphs

DOI10.1137/1.9781611974331.CH77zbMATH Open1410.68284OpenAlexW1924811958MaRDI QIDQ4575657FDOQ4575657

Authors: Yixin Cao 

Publication date: 16 July 2018

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

Abstract: Let $mboxinterval+kv$, $mboxinterval+ke$, and $mboxinterval-ke$ denote the classes of graphs that can be obtained from some interval graph by adding $k$ vertices, adding $k$ edges, and deleting $k$ edges, respectively. When $k$ is small, these graph classes are called almost interval graphs. They are well motivated from computational biology, where the data ought to be represented by an interval graph while we can only expect an almost interval graph for the best. For any fixed $k$, we give linear-time algorithms for recognizing all these classes, and in the case of membership, our algorithms provide also a specific interval graph as evidence. When $k$ is part of the input, these problems are also known as graph modification problems, all NP-complete. Our results imply that they are fixed-parameter tractable parameterized by $k$, thereby resolving the long-standing open problem on the parameterized complexity of recognizing $mboxinterval+ke$, first asked by Bodlaender et al. [Bioinformatics, 11:49--57, 1995]. Moreover, our algorithms for recognizing $mboxinterval+kv$ and $mboxinterval-ke$ run in times $O(6^{k}cdot(n+m))$ and $O(8^{k}cdot(n+m))$, (where $n$ and $m$ stand for the numbers of vertices and edges respectively in the input graph,) significantly improving the $O(k^{2k}cdot{n}^{3}m)$-time algorithm of Heggernes et al. [STOC 2007] and the $O(10^{k}cdot{n}^9)$-time algorithm of Cao and Marx [SODA 2014] respectively.

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

Recommendations

• scientific article; zbMATH DE number 4049085
• A linear-time algorithm for proper interval graph recognition
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Interval Completion Is Fixed Parameter Tractable

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)

Cited In (35)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Conflict free version of covering problems on graphs: classical and parameterized
• The recognition problem for line bigraphs
• Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
• Paths to trees and cacti
• Simple linear time recognition of unit interval graphs
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Approximation and kernelization for chordal vertex deletion
• Graphs with at most two moplexes
• Slightly superexponential parameterized problems
• On the classes of interval graphs of limited nesting and count of lengths
• Rank reduction of oriented graphs by vertex and edge deletions
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Paths to trees and cacti
• Vertex deletion problems on chordal graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• A survey of parameterized algorithms and the complexity of edge modification
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Vertex deletion into bipartite permutation graphs
• Assistance and interdiction problems on interval graphs
• Vertex deletion problems on chordal graphs
• Parameterized complexity of diameter
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Modification problems toward proper (Helly) circular-arc graphs
• Polynomial Kernel for Interval Vertex Deletion
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Erdős–Pósa property of obstructions to interval graphs
• A constant-factor approximation for weighted bond cover
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• Line-Polar Graphs: Characterization and Recognition
• Vertex deletion into bipartite permutation graphs
• Title not available (Why is that?)

This page was built for publication: Linear recognition of almost interval graphs

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