(Sub)linear kernels for edge modification problems toward structured graph classes

DOI10.1007/S00453-022-00969-1MaRDI QIDQ2093576zbMATH OpenOpenAlexFDO

Authors Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron

Publication date 27 October 2022

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

kernelizationsplit graphsgraph editing(Sub)linear kernels

Mathematics Subject Classification ID

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

Recommendations

• (Sub)linear kernels for edge modification problems towards structured graph classes
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems

Cites work

• A \(2k\) kernel for the cluster editing problem
• A cubic vertex-kernel for trivially perfect editing
• A golden ratio parameterized algorithm for cluster editing
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Complexity classification of some edge modification problems
• Correlation clustering
• Edge deletion problems: branching facilitated by modular decomposition
• Editing simple graphs
• 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
• Kernelization. Theory of parameterized preprocessing
• NP-completeness results for edge modification problems
• Node-and edge-deletion NP-complete problems
• On the complexity of \(k\)-SAT
• Parameterized algorithms
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Quasi-threshold graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• The Comparability Graph of a Tree
• The splittance of a graph
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters

Cited in

(6)

• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• A quasi-quadratic vertex-kernel for cograph edge editing
• A survey of parameterized algorithms and the complexity of edge modification
• (Sub)linear kernels for edge modification problems towards structured graph classes
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• A cubic vertex-kernel for trivially perfect editing

This page was built for publication: (Sub)linear kernels for edge modification problems toward structured graph classes

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