Unit interval editing is fixed-parameter tractable

DOI10.1016/j.ic.2017.01.008zbMath1359.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

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