On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems

DOI10.1007/978-3-642-17493-3_15zbMath1309.68151arXiv1007.4011OpenAlexW3123623337MaRDI QIDQ3058699

Sylvain Guillemot, Anthony Perez, Christophe Paul

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Two edge modification problems without polynomial kernels ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Complexity and parameterized algorithms for cograph editing ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Incompressibility of \(H\)-free edge modification problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A general method to speed up fixed-parameter-tractable algorithms
• Cluster graph modification problems
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Two Edge Modification Problems without Polynomial Kernels
• The complexity of some edge deletion problems
• Graph Classes: A Survey
• Graph Sandwich Problems
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Efficient Parameterized Preprocessing for Cluster Editing
• Complexity classification of some edge modification problems

This page was built for publication: On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems