Unit interval editing is fixed-parameter tractable

DOI10.1007/978-3-662-47672-7_25zbMATH Open1359.68230arXiv1504.04470OpenAlexW3022542130MaRDI QIDQ515577FDOQ515577

Authors: Yixin Cao 

Publication date: 16 March 2017

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

Abstract: Given a graph~$G$ and integers $k_1$, $k_2$, and~$k_3$, the unit interval editing problem asks whether $G$ can be transformed into a unit interval graph by at most $k_1$ vertex deletions, $k_2$ edge deletions, and $k_3$ edge additions. We give an algorithm solving this problem in time $2^{O(klogk)}cdot(n+m)$, where $k:=k_1+k_2+k_3$, and $n,m$ denote respectively the numbers of vertices and edges of $G$. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed-parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time $O(4^{k}cdot(n+m))$. Another result is an $O(6^{k}cdot(n+m))$-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time $O(6^{k}cdot{n}^6)$.

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

Recommendations

• Unit interval editing is fixed-parameter tractable
• Interval deletion is fixed-parameter tractable
• Interval deletion is fixed-parameter tractable
• Unit interval vertex deletion: fewer vertices are relevant
• Chordal editing is fixed-parameter tractable

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

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

Cites Work

• Fundamentals of parameterized complexity
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On intervalizing \(k\)-colored graphs for DNA physical mapping
• The node-deletion problem for hereditary properties is NP-complete
• Incidence matrices and interval graphs
• Algorithms on circular-arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Title not available (Why is that?)
• Finding small separators in linear time via treewidth reduction
• Chordal editing is fixed-parameter tractable
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Unit interval editing is fixed-parameter tractable
• Chordal deletion is fixed-parameter tractable
• Normal Helly circular-arc graphs and its subclasses
• NP-completeness results for edge modification problems
• Structure theorems for some circular-arc graphs
• Chordal editing is fixed-parameter tractable
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Proper Interval Vertex Deletion
• Polynomial kernels for proper interval completion and related problems
• Edge deletion problems: branching facilitated by modular decomposition
• On chordal proper circular arc graphs
• Unit interval vertex deletion: fewer vertices are relevant
• Proper interval vertex deletion
• Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10--12, 2016
• Measuring indifference: unit interval vertex deletion
• Linear recognition of almost interval graphs
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A Subexponential Parameterized Algorithm for Proper Interval Completion

Cited In (22)

• Title not available (Why is that?)
• Quick but odd growth of cacti
• Paths to trees and cacti
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Unit interval vertex deletion: fewer vertices are relevant
• Measuring indifference: unit interval vertex deletion
• Linear recognition of almost interval graphs
• Rank reduction of oriented graphs by vertex and edge deletions
• Paths to trees and cacti
• Chordal editing is fixed-parameter tractable
• Vertex deletion problems on chordal graphs
• Unit interval editing is fixed-parameter tractable
• A survey of parameterized algorithms and the complexity of edge modification
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Vertex deletion into bipartite permutation graphs
• Vertex deletion problems on chordal graphs
• The parameterized complexity of cycle packing: indifference is not an issue
• Modification problems toward proper (Helly) circular-arc graphs
• Polynomial Kernel for Interval Vertex Deletion
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Linear-time minimal cograph editing
• Vertex deletion into bipartite permutation graphs

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

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