A survey of parameterized algorithms and the complexity of edge modification

DOI10.1016/J.COSREV.2023.100556MaRDI QIDQ6158862zbMATH OpenOpenAlexWikidataFDO

Authors Christophe Crespelle, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach

Publication date 20 June 2023

Published in Computer Science Review (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

algorithmsedge modificationgraph modificationparameterized graph algorithms

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computer science (68-XX)

Abstract: The survey provides an overview of the developing area of parameterized algorithms for graph modification problems. We concentrate on edge modification problems, where the task is to change a small number of adjacencies in a graph in order to satisfy some required property.

Cites work

Cited in

(37)

• On the Wimer method for designing edge-based algorithms
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Building large \(k\)-cores from sparse graphs
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Parameterized Complexity of Edge Interdiction Problems
• On the \(d\)-claw vertex deletion problem
• A quasi-quadratic vertex-kernel for cograph edge editing
• Modification problems toward proper (Helly) circular-arc graphs
• Trimming forests is hard (unless they are made of stars)
• Algorithms for subgraph complementation to some classes of graphs
• Faster algorithms for 3-leaf power modification problems
• Fundamental problems on bounded-treewidth graphs: the real source of hardness
• Algorithms and hardness results for the (k, )-cover problem
• Destroying densest subgraphs is hard
• Smaller kernels for 3-leaf power modifications problems
• Kernel for proper Helly circular-arc vertex deletion: smaller and simpler via graph isomorphism
• An improved kernelization algorithm for trivially perfect editing
• Vertex identification to a forest
• The st-planar edge completion problem is fixed-parameter tractable
• Algorithms and hardness results for the (3, 1)-cover problem
• A quadratic vertex kernel for diamond-free edge deletion
• Polynomial kernels for edge modification problems towards block and strictly chordal graphs
• Destroying densest subgraphs is hard
• The complexity of cluster vertex splitting and company
• Triangle-covered graphs: algorithms, complexity, and structure
• Minimum k-critical-bipartite graphs: the irregular case
• On the descriptive complexity of vertex deletion problems
• On the complexity of establishing hereditary graph properties via vertex splitting
• Polynomial kernel and incompressibility for prison-free edge deletion and completion
• A quadratic kernel for \{Claw, Diamond\}-free deletion
• Improved upper bounds on color reversal by local inversions
• Kernelization in almost linear time for clustering into bounded vertex cover components
• On the complexity of minimising the moving distance for dispersing objects
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• Kernel for proper Helly circular-arc vertex deletion
• A quadratic kernel for \{\textit{claw, diamond}\}-free deletion
• Tight upper bounds on color reversal by local inversions

This page was built for publication: A survey of parameterized algorithms and the complexity of edge modification

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