An improved kernelization algorithm for trivially perfect editing

DOI10.4230/LIPICS.IPEC.2023.15MaRDI QIDQ6926194zbMATH OpenFDO

Authors Maël Dumas, Anthony Perez

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.15

zbMATH Keywords

parameterized complexitygraph modificationkernelization algorithmstrivially perfect graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7803595 (Why is no real title available?)
• (Sub)linear kernels for edge modification problems toward structured graph classes
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• A cubic-vertex kernel for flip consensus tree
• A polynomial kernel for trivially perfect editing
• A survey of parameterized algorithms and the complexity of edge modification
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Edge deletion problems: branching facilitated by modular decomposition
• Exploring the subexponential complexity of completion problems
• Fast quasi-threshold editing
• 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 threshold of intractability
• Paths, Trees, and Flowers
• 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
• Reducibility among combinatorial problems
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Trivially perfect graphs
• Two edge modification problems without polynomial kernels
• \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms

Cited in

(3)

• Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• On the descriptive complexity of vertex deletion problems
• A polynomial kernel for deletion to the scattered class of cliques and trees

This page was built for publication: An improved kernelization algorithm for trivially perfect editing

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