A polynomial kernel for trivially perfect editing

DOI10.1007/978-3-662-48350-3_36zbMATH Open1397.05070arXiv1412.7558OpenAlexW1589219240WikidataQ59607877 ScholiaQ59607877MaRDI QIDQ1799208FDOQ1799208

Michał Pilipczuk, Pål Grønås Drange

Publication date: 18 October 2018

Published in: Algorithmica, Algorithms - ESA 2015 (Search for Journal in Brave)

Abstract: We give a kernel with $O(k^7)$ vertices for Trivially Perfect Editing, the problem of adding or removing at most $k$ edges in order to make a given graph trivially perfect. This answers in affirmative an open question posed by Nastos and Gao, and by Liu et al. Our general technique implies also the existence of kernels of the same size for the related problems Trivially Perfect Completion and Trivially Perfect Deletion. Whereas for the former an $O(k^3)$ kernel was given by Guo, for the latter no polynomial kernel was known. We complement our study of Trivially Perfect Editing by proving that, contrary to Trivially Perfect Completion, it cannot be solved in time $2^{o(k)}cdot{n}^{O(1)}$ unless the Exponential Time Hypothesis fails. In this manner we complete the picture of the parameterized and kernelization complexity of the classic edge modification problems for the class of trivially perfect graphs.

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

zbMATH Keywords

polynomial kernelgraph modificationtrivially perfect graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Perfect graphs (05C17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Paths, Trees, and Flowers
• Cluster editing with locally bounded modifications
• A kernelization algorithm for \(d\)-hitting set
• Modular decomposition and transitive orientation
• Which problems have strongly exponential complexity?
• Parametrized complexity theory.
• Transitiv orientierbare Graphen
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Quasi-threshold graphs
• Fast FAST
• NP-completeness results for edge modification problems
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Two Edge Modification Problems without Polynomial Kernels
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Edge-Deletion Problems
• Subexponential parameterized algorithm for Interval Completion
• The complexity of some edge deletion problems
• Complexity and parameterized algorithms for cograph editing
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• A polynomial kernel for trivially perfect editing
• On the threshold of intractability
• Faster parameterized algorithms for deletion to split graphs
• Exploring the subexponential complexity of completion problems
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Two edge modification problems without polynomial kernels
• Polynomial Kernelization for Removing Induced Claws and Diamonds
• Polynomial kernelization for removing induced claws and diamonds
• Title not available (Why is that?)

Cited In (19)

• Paths to trees and cacti
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Unit interval vertex deletion: fewer vertices are relevant
• Edge deletion problems: branching facilitated by modular decomposition
• Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
• Rank reduction of oriented graphs by vertex and edge deletions
• A Polynomial Kernel for Diamond-Free Editing
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• A survey of parameterized algorithms and the complexity of edge modification
• A polynomial kernel for trivially perfect editing
• Fast Quasi-Threshold Editing
• On the threshold of intractability
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Exploring the subexponential complexity of completion problems
• Polynomial kernelization for removing induced claws and diamonds
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• Paths to Trees and Cacti
• (Sub)linear kernels for edge modification problems toward structured graph classes

This page was built for publication: A polynomial kernel for trivially perfect editing

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