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

DOI10.1007/S00453-022-01070-3MaRDI QIDQ2696282zbMATH OpenOpenAlexFDO

Authors Maël Dumas, Anthony Perez, Ioan Todinca

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

graph modification problemskernelization algorithmsparameterized complexitytrivially perfect graphs

Mathematics Subject Classification ID

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

Recommendations

• A cubic vertex-kernel for trivially perfect editing
• (Sub)linear kernels for edge modification problems toward structured graph classes
• (Sub)linear kernels for edge modification problems towards structured graph classes

Cites work

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

Cited in

(4)

• A Polynomial Kernel for Diamond-Free Editing
• A cubic vertex-kernel for trivially perfect editing
• An improved kernelization algorithm for trivially perfect editing
• Polynomial kernels for edge modification problems towards block and strictly chordal graphs

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

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