Unit interval editing is fixed-parameter tractable

DOI10.1016/j.ic.2017.01.008zbMath1359.68230arXiv1504.04470MaRDI 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 subgraph; graph modification problem; certifying algorithm; (proper, Helly) arc model; (proper, unit) interval model; \(\{\text{claw},S_3,\overline{S_3},C_4\}\)-free graph; proper Helly circular-arc graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

68Q27: Parameterized complexity, tractability and kernelization

Related Items

Vertex Deletion Problems on Chordal Graphs, Paths to Trees and Cacti, Unnamed Item, The parameterized complexity of cycle packing: indifference is not an issue, Vertex deletion into bipartite permutation graphs, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, Polynomial Kernel for Interval Vertex Deletion, A survey of parameterized algorithms and the complexity of edge modification, Chordal editing is fixed-parameter tractable, Unit interval editing is fixed-parameter tractable, Rank reduction of oriented graphs by vertex and edge deletions, Unit interval vertex deletion: fewer vertices are relevant, Vertex deletion problems on chordal graphs, Paths to trees and cacti, Subexponential parameterized algorithms and kernelization on almost chordal graphs, 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

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