Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes

DOI10.1016/j.jcss.2023.03.004zbMath1529.68216arXiv2201.03142OpenAlexW4366086108MaRDI QIDQ6098156

Ashwin Jacob, Venkatesh Raman, Diptapriyo Majumdar

Publication date: 12 June 2023

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

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

zbMATH Keywords

chordal graphsapproximation algorithmsinterval graphsfixed-parameter tractabilitybipartite permutation graphsscattered graph classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Deletion to scattered graph classes. I: Case of finite number of graph classes

Cites Work

• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Improved upper bounds for vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Proper interval vertex deletion
• Faster deterministic \textsc{Feedback Vertex Set}
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Faster FPT algorithms for deletion to pairs of graph classes
• Representation of a finite graph by a set of intervals on the real line
• Graph Classes: A Survey
• Linear Recognition of Almost Interval Graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Faster Parameterized Algorithms Using Linear Programming
• Interval Deletion Is Fixed-Parameter Tractable
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• A Near-Optimal Planarization Algorithm
• Parameterized Algorithms
• Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
• Vertex deletion into bipartite permutation graphs

This page was built for publication: Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes