Unit interval editing is fixed-parameter tractable

DOI10.1007/978-3-662-47672-7_25zbMath1359.68230arXiv1504.04470OpenAlexW3022542130MaRDI QIDQ515577

Yixin Cao

Publication date: 16 March 2017

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

forbidden induced subgraphgraph modification problemcertifying algorithm(proper, Helly) arc model(proper, unit) interval model\(\{\text{claw},S_3,\overline{S_3},C_4\}\)-free graphproper Helly circular-arc graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (19)

Paths to Trees and Cacti ⋮ Chordal editing is fixed-parameter tractable ⋮ Linear-time minimal cograph editing ⋮ Vertex deletion into bipartite permutation graphs ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Quick but odd growth of cacti ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Unit interval editing is fixed-parameter tractable ⋮ Paths to trees and cacti ⋮ Vertex deletion into bipartite permutation graphs ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Vertex deletion problems on chordal graphs ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work

• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Fundamentals of parameterized complexity
• Polynomial kernels for proper interval completion and related problems
• Unit interval editing is fixed-parameter tractable
• Chordal deletion is fixed-parameter tractable
• The node-deletion problem for hereditary properties is NP-complete
• On chordal proper circular arc graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Unit interval vertex deletion: fewer vertices are relevant
• Normal Helly circular-arc graphs and its subclasses
• Proper interval vertex deletion
• Edge deletion problems: branching facilitated by modular decomposition
• Incidence matrices and interval graphs
• NP-completeness results for edge modification problems
• Structure theorems for some circular-arc graphs
• Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
• Finding small separators in linear time via treewidth reduction
• Chordal Editing is Fixed-Parameter Tractable
• Measuring Indifference: Unit Interval Vertex Deletion
• Proper Interval Vertex Deletion
• Computing the Minimum Fill-In is NP-Complete
• Algorithms on circular-arc graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Linear Recognition of Almost Interval Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• On intervalizing \(k\)-colored graphs for DNA physical mapping

This page was built for publication: Unit interval editing is fixed-parameter tractable