A survey of parameterized algorithms and the complexity of edge modification

DOI10.1016/j.cosrev.2023.100556arXiv2001.06867OpenAlexW3001552648WikidataQ126176041 ScholiaQ126176041MaRDI QIDQ6158862

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

Publication date: 20 June 2023

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

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

zbMATH Keywords

algorithmsgraph modificationedge modificationparameterized graph algorithms

Mathematics Subject Classification ID

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

Related Items (3)

Building large \(k\)-cores from sparse graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy

Cites Work

• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Win-win kernelization for degree sequence completion problems
• Chordal editing is fixed-parameter tractable
• Planar disjoint-paths completion
• Reducing rank of the adjacency matrix by graph modification
• Fundamentals of parameterized complexity
• Parameterized complexity of vertex deletion into perfect graph classes
• Polynomial kernels for proper interval completion and related problems
• Editing graphs to satisfy degree constraints: a parameterized approach
• A \(2k\) kernel for the cluster editing problem
• Kernelization for cycle transversal problems
• Parameterized Eulerian strong component arc deletion problem on tournaments
• Graph-based data clustering with overlaps
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Augmenting graphs to minimize the diameter
• A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
• Graph editing to a given degree sequence
• Unit interval editing is fixed-parameter tractable
• Graph editing problems with extended regularity constraints
• List H-coloring a graph by removing few vertices
• Lower bounds for kernelizations and other preprocessing procedures
• Polynomial kernels for 3-leaf power graph modification problems
• Parameterized complexity of even/odd subgraph problems
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• Kernels for feedback arc set in tournaments
• Edge bipartization faster than \(2^k\)
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Complexity and parameterized algorithms for cograph editing
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Cluster editing with locally bounded modifications
• Rank reduction of oriented graphs by vertex and edge deletions
• On the computational complexity of vertex integrity and component order connectivity
• Editing to a planar graph of given degrees
• An FPT algorithm for edge subset feedback edge set
• An improved kernel size for rotation distance in binary trees
• Multi-budgeted directed cuts
• Graph-modeled data clustering: Exact algorithms for clique generation
• Parameterized graph separation problems
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Editing to Eulerian graphs
• Finding small stabilizers for unstable graphs
• The complexity of degree anonymization by vertex addition
• Obtaining split graphs by edge contraction
• Flip distance between two triangulations of a point set is NP-complete
• Flips in planar graphs
• Chordal deletion is fixed-parameter tractable
• The parameterized complexity of editing graphs for bounded degeneracy
• Simple and improved parameterized algorithms for multiterminal cuts
• A kernelization algorithm for \(d\)-hitting set
• Rotation distance is fixed-parameter tractable
• Closest 4-leaf power is fixed-parameter tractable
• A more effective linear kernelization for cluster editing
• Parameterized complexity of finding regular induced subgraphs
• On problems without polynomial kernels
• Going weighted: parameterized algorithms for cluster editing
• Edge-connectivity augmentation problems
• The node-deletion problem for hereditary properties is NP-complete
• The splittance of a graph
• Optimal covering of cacti by vertex-disjoint paths
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Edge-integrity: A survey
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Graph minors. XI: Circuits on a surface
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Measuring the vulnerability for classes of intersection graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Which problems have strongly exponential complexity?
• Listing all potential maximal cliques of a graph
• Can we create large \(k\)-cores by adding few edges?
• Parameterizing edge modification problems above lower bounds
• Two edge modification problems without polynomial kernels
• Finding even subgraphs even faster
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Path-contractions, edge deletions and connectivity preservation
• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• Cluster editing: kernelization based on edge cuts
• Independence free graphs and vertex connectivity augmentation
• A polynomial kernel for trivially perfect editing
• Parameterized complexity of length-bounded cuts and multicuts
• Parameterized complexity of vertex colouring
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Cluster graph modification problems
• Graph minors. XIII: The disjoint paths problem
• Finding regular subgraphs in both arbitrary and planar graphs
• A new view on rural postman based on Eulerian extension and matching
• A golden ratio parameterized algorithm for cluster editing
• Even faster parameterized cluster deletion and cluster editing
• Obtaining planarity by contracting few edges
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Proper interval vertex deletion
• Clustering with local restrictions
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• An improved FPT algorithm for the flip distance problem
• On the threshold of intractability
• A polynomial kernel for diamond-free editing
• (Sub)linear kernels for edge modification problems toward structured graph classes
• Length-bounded cuts: proper interval graphs and structural parameters
• Metric violation distance: hardness and approximation
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• The Complexity of Multiterminal Cuts
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>
• Structured Connectivity Augmentation
• Linear Recognition of Almost Interval Graphs
• Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
• Directed multicut is W[1-hard, even for four terminal pairs]
• Approximation and Kernelization for Chordal Vertex Deletion
• Multicut Is FPT
• Fractals for Kernelization Lower Bounds
• A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Minimum Bisection Is Fixed-Parameter Tractable
• On Algorithms Employing Treewidth for $L$-bounded Cut Problems
• Kernelization
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Compression via Matroids
• Faster Parameterized Algorithms Using Linear Programming
• Interval Deletion Is Fixed-Parameter Tractable
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Hardness of Approximation for H -free Edge Modification Problems
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Modification to Planarity is Fixed Parameter Tractable
• Cluster Editing in Multi-Layer and Temporal Graphs.
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• Partial complementation of graphs
• Diminishable parameterized problems and strict polynomial kernelization
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Parameterized Algorithms to Preserve Connectivity
• Finding Highly Connected Subgraphs
• Editing to Connected F-Degree Graph
• Interval Vertex Deletion Admits a Polynomial Kernel
• Efficient Algorithms for Eulerian Extension and Rural Postman
• Cluster Editing
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Variants of Plane Diameter Completion
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Fast biclustering by dual parameterization
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Data reduction and exact algorithms for clique cover
• Obtaining a Bipartite Graph by Contracting Few Edges
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Efficient Parameterized Preprocessing for Cluster Editing
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• Parameterized Algorithms
• Characterizations of derived graphs
• A Polynomial Kernel for Line Graph Deletion
• FPT Inapproximability of Directed Cut and Connectivity Problems
• Clustering to Given Connectivities
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
• NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
• Graph-Theoretic Concepts in Computer Science
• A Subexponential Parameterized Algorithm for Proper Interval Completion
• On the relation of strong triadic closure and cluster deletion
• A polynomial kernel for distance-hereditary vertex deletion
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors
• Polynomial kernels for paw-free edge modification problems
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Complexity classification of some edge modification problems
• Finding large degree-anonymous subgraphs is hard
• Generalized Metric Repair on Graphs
• Component order connectivity in directed graphs
• A new temporal interpretation of cluster editing
• Parameterized analysis and crossing minimization problems
• Parameterized aspects of strong subgraph closure
• Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Parameterized dynamic cluster editing
• Edge deletion problems: branching facilitated by modular decomposition
• Fixed-parameter tractability results for feedback set problems in tournaments
• On the parameterized complexity of graph modification to first-order logic properties
• Minimum fill-in: inapproximability and almost tight lower bounds
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Tractability of König edge deletion problems
• Incompressibility of \(H\)-free edge modification problems
• A refined complexity analysis of degree anonymization in graphs
• Faster parameterized algorithms for deletion to split graphs
• An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
• Editing to a graph of given degrees
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Polynomial kernelization for removing induced claws and diamonds
• A polynomial-time algorithm for outerplanar diameter improvement
• Editing to a connected graph of given degrees
• The complexity of degree anonymization by graph contractions
• On the complexity of multi-parameterized cluster editing
• Fixed-parameter tractable distances to sparse graph classes
• Computing the flip distance between triangulations
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Parameterized complexity of Eulerian deletion problems
• A cubic-vertex kernel for flip consensus tree
• Flip distance between triangulations of a planar point set is APX-hard
• A faster FPT algorithm for bipartite contraction
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• The parametric complexity of graph diameter augmentation
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Parametrized complexity theory.
• Error compensation in leaf power problems
• NP-completeness results for edge modification problems
• Rank-width and vertex-minors
• Kernel for \(K_t\)\textsc{-free Edge Deletion}
• Faster parameterized algorithm for \textsc{Bicluster Editing}
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• On Graph Powers for Leaf-Labeled Trees
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Exploring the Subexponential Complexity of Completion Problems
• Graph Theory
• On Generating Triangle-Free Graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Parameterized Tractability of Multiway Cut with Parity Constraints
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Social Network Data Analytics
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• On the Parameterized Complexity of Computing Graph Bisections
• On Editing Graphs into 2-Club Clusters
• BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES
• What’s Next? Future Directions in Parameterized Complexity
• On the Clique Editing Problem
• Finding small separators in linear time via treewidth reduction
• Editing Simple Graphs
• A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
• Kernelization and complexity results for connectivity augmentation problems
• Computing the Deficiency of Housing Markets with Duplicate Houses
• Augmenting Undirected Node-Connectivity by One
• From Few Components to an Eulerian Graph by Adding Arcs
• (Meta) Kernelization
• Randomized Parameterized Algorithms for Co-path Set Problem
• Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
• Deciding first-order properties of locally tree-decomposable structures
• An Eulerian exposition
• Maximal Flow Through a Network
• Odd Multiway Cut in Directed Acyclic Graphs
• Fixed-parameter tractability and data reduction for multicut in trees
• Two-Layer Planarization: Improving on Parameterized Algorithmics
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
• Improved Algorithms for Bicluster Editing
• Wheel-Free Deletion Is W[2-Hard]
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Exact Algorithms for Treewidth and Minimum Fill-In
• Fast FAST
• Interval Completion Is Fixed Parameter Tractable
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The minimum augmentation of any graph to aK-edge-connected graph
• Edge-Deletion Problems
• Computing the Minimum Fill-In is NP-Complete
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmentation Problems
• The spanning subgraphs of eulerian graphs
• A Minimax Theorem for Directed Graphs
• Graph Classes: A Survey
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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