On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
From MaRDI portal
Publication:1949740
DOI10.1007/s00453-012-9619-5zbMath1262.68048OpenAlexW1754878559MaRDI QIDQ1949740
Sylvain Guillemot, Christophe Paul, Anthony Perez, Frédéric Havet
Publication date: 16 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9619-5
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (30)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Linear-time minimal cograph editing ⋮ Parameterizing edge modification problems above lower bounds ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ On subgraph complementation to \(H\)-free graphs ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ On the computational complexity of the bipartizing matching problem ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Unnamed Item ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Fractals for Kernelization Lower Bounds ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Unnamed Item ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ A polynomial kernel for trivially perfect editing ⋮ Polynomial kernels for paw-free edge modification problems ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ On subgraph complementation to \(H\)-free Graphs ⋮ Incompressibility of \(H\)-free edge modification problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A survey of the algorithmic aspects of modular decomposition
- Polynomial kernels for 3-leaf power graph modification problems
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernels for feedback arc set in tournaments
- On problems without polynomial kernels
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A general method to speed up fixed-parameter-tractable algorithms
- Cluster graph modification problems
- Handle-rewriting hypergraph grammars
- Parametrized complexity theory.
- On Generating Triangle-Free Graphs
- Cograph Editing: Complexity and Parameterized Algorithms
- Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A 2k Kernel for the Cluster Editing Problem
- Two Edge Modification Problems without Polynomial Kernels
- The complexity of some edge deletion problems
- A Combinatorial Decomposition Theory
- Graph Classes: A Survey
- An O(n2) Algorithm for Undirected Split Decomposition
- Graph Sandwich Problems
- Efficient Parameterized Preprocessing for Cluster Editing
- Graph-Theoretic Concepts in Computer Science
- 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
