Unit interval vertex deletion: fewer vertices are relevant

DOI10.1016/j.jcss.2018.01.001zbMath1391.68058arXiv1607.01162OpenAlexW2964327184WikidataQ130160419 ScholiaQ130160419MaRDI QIDQ1747495

Jianxin Wang, Yixin Cao, Yuping Ke, Wenjun Li, Xiating Ouyang

Publication date: 8 May 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

kernelizationforbidden induced subgraphgraph modification problemunit interval graph(proper, unit) interval modelmodulator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

Approximation and Kernelization for Chordal Vertex Deletion ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Unit interval editing is fixed-parameter tractable ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ The parameterized complexity of cycle packing: indifference is not an issue ⋮ A polynomial kernel for bipartite permutation vertex deletion

Cites Work

• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Unit interval editing is fixed-parameter tractable
• On rigid circuit graphs
• Chordal deletion is fixed-parameter tractable
• The node-deletion problem for hereditary properties is NP-complete
• A short proof that `proper = unit'
• A polynomial kernel for trivially perfect editing
• Proper interval vertex deletion
• Optimal greedy algorithms for indifference graphs
• Parametrized complexity theory.
• Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
• Measuring Indifference: Unit Interval Vertex Deletion
• Intersection Theorems for Systems of Sets
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Approximation and Kernelization for Chordal Vertex Deletion
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• A Polynomial Kernel for Proper Interval Vertex Deletion

This page was built for publication: Unit interval vertex deletion: fewer vertices are relevant