A cubic vertex-kernel for \textsc{Trivially Perfect Editing}

DOI10.1007/s00453-022-01070-3OpenAlexW3161835050MaRDI QIDQ2696282

Ioan Todinca, Maël Dumas, Anthony Perez

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexitygraph modification problemskernelization algorithmstrivially perfect graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Chordal editing is fixed-parameter tractable
• Polynomial kernels for proper interval completion and related problems
• Polynomial kernels for 3-leaf power graph modification problems
• On low tree-depth decompositions
• Trivially perfect graphs
• On the complexity of DNA physical mapping
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Two edge modification problems without polynomial kernels
• A polynomial kernel for trivially perfect editing
• Quasi-threshold graphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Applying modular decomposition to parameterized cluster editing problems
• Incompressibility of \(H\)-free edge modification problems
• Faster parameterized algorithms for deletion to split graphs
• NP-completeness results for edge modification problems
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Exploring the Subexponential Complexity of Completion Problems
• The complexity of some edge deletion problems
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Kernelization
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Subexponential Parameterized Algorithm for Minimum Fill-In
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: A cubic vertex-kernel for \textsc{Trivially Perfect Editing}