A survey of parameterized algorithms and the complexity of edge modification
From MaRDI portal
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
- (Meta) kernelization
- (Sub)linear kernels for edge modification problems toward structured graph classes
- A 2k kernel for the cluster editing problem
- A cubic vertex-kernel for trivially perfect editing
- A cubic-vertex kernel for flip consensus tree
- A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
- A golden ratio parameterized algorithm for cluster editing
- A kernelization algorithm for \(d\)-hitting set
- A Minimax Theorem for Directed Graphs
- A more effective linear kernelization for cluster editing
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- A more relaxed model for graph-based data clustering: s-plex cluster editing
- A new temporal interpretation of cluster editing
- A new view on rural postman based on Eulerian extension and matching
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- A polynomial kernel for diamond-free editing
- A polynomial kernel for distance-hereditary vertex deletion
- A Polynomial Kernel for Line Graph Deletion
- A polynomial-time algorithm for outerplanar diameter improvement
- A refined complexity analysis of degree anonymization in graphs
- A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs
- An Eulerian exposition
- An FPT algorithm for edge subset feedback edge set
- An improved FPT algorithm for the flip distance problem
- An improved kernel size for rotation distance in binary trees
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximation and kernelization for chordal vertex deletion
- Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Augmenting undirected node-connectivity by one
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- Can we create large \(k\)-cores by adding few edges?
- Characterizations of derived graphs
- Chordal deletion is fixed-parameter tractable
- Chordal editing is fixed-parameter tractable
- Closest 4-leaf power is fixed-parameter tractable
- Cluster editing
- Cluster Editing in Multi-Layer and Temporal Graphs.
- Cluster editing with locally bounded modifications
- Cluster editing: kernelization based on edge cuts
- Cluster graph modification problems
- Clustering to Given Connectivities
- Clustering with local restrictions
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Complexity and parameterized algorithms for cograph editing
- Complexity classification of some edge modification problems
- Component order connectivity in directed graphs
- Compression via Matroids
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Computing the Deficiency of Housing Markets with Duplicate Houses
- Computing the flip distance between triangulations
- Computing the Minimum Fill-In is NP-Complete
- Cutting up is hard to do: the parameterised complexity of k-cut and related problems
- Data reduction and exact algorithms for clique cover
- Deciding first-order properties of locally tree-decomposable structures
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- Destroying Bicolored $P_3$s by Deleting Few Edges
- Dichotomy results on the hardness of H-free edge modification problems
- Diminishable parameterized problems and strict polynomial kernelization
- Directed subset feedback vertex set is fixed-parameter tractable
- Edge bipartization faster than \(2^k\)
- Edge deletion problems: branching facilitated by modular decomposition
- Edge-connectivity augmentation problems
- Edge-Deletion Problems
- Edge-integrity: A survey
- Editing graphs to satisfy degree constraints: a parameterized approach
- Editing simple graphs
- Editing to a connected graph of given degrees
- Editing to a planar graph of given degrees
- Editing to Connected F-Degree Graph
- Editing to Eulerian graphs
- Efficient algorithms for Eulerian extension and rural Postman
- Efficient Parameterized Preprocessing for Cluster Editing
- Error compensation in leaf power problems
- Even faster parameterized cluster deletion and cluster editing
- Exact Algorithms for Treewidth and Minimum Fill-In
- Exploring the subexponential complexity of completion problems
- Fast biclustering by dual parameterization
- Fast FAST
- Faster parameterized algorithm for Bicluster Editing
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Faster parameterized algorithms for deletion to split graphs
- Faster parameterized algorithms using linear programming
- Feedback vertex set inspired kernel for chordal vertex deletion
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Finding even subgraphs even faster
- Finding highly connected subgraphs
- Finding large degree-anonymous subgraphs is hard
- Finding odd cycle transversals.
- Finding regular subgraphs in both arbitrary and planar graphs
- Finding small separators in linear time via treewidth reduction
- Finding small stabilizers for unstable graphs
- Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
- Fixed-parameter tractability and data reduction for multicut in trees
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fixed-parameter tractability results for feedback set problems in tournaments
- Fixed-parameter tractable distances to sparse graph classes
- Flip distance between triangulations of a planar point set is APX-hard
- Flip distance between two triangulations of a point set is NP-complete
- Flips in planar graphs
- FPT Inapproximability of Directed Cut and Connectivity Problems
- Fractals for kernelization lower bounds
- From few components to an Eulerian graph by adding ARCS
- Fundamentals of parameterized complexity
- Generalized Metric Repair on Graphs
- Going weighted: parameterized algorithms for cluster editing
- Graph Classes: A Survey
- Graph editing problems with extended regularity constraints
- Graph editing to a given degree sequence
- Graph minors. XI: Circuits on a surface
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- Graph theory
- Graph-based data clustering with overlaps
- Graph-modeled data clustering: Exact algorithms for clique generation
- Graph-Theoretic Concepts in Computer Science
- Hardness of approximation for \(H\)-free edge modification problems
- scientific article; zbMATH DE number 4130410 (Why is no real title available?)
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 5485473 (Why is no real title available?)
- scientific article; zbMATH DE number 5485529 (Why is no real title available?)
- scientific article; zbMATH DE number 5764786 (Why is no real title available?)
- scientific article; zbMATH DE number 4035869 (Why is no real title available?)
- scientific article; zbMATH DE number 4053662 (Why is no real title available?)
- scientific article; zbMATH DE number 125469 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 718663 (Why is no real title available?)
- scientific article; zbMATH DE number 1418487 (Why is no real title available?)
- scientific article; zbMATH DE number 3257167 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Improved Algorithms for Bicluster Editing
- Improved fixed-parameter algorithms for minimum-flip consensus trees
- Incompressibility of \(H\)-free edge modification problems
- Independence free graphs and vertex connectivity augmentation
- Interval Completion Is Fixed Parameter Tractable
- Interval deletion is fixed-parameter tractable
- Interval vertex deletion admits a polynomial kernel
- Kernel for \(K_t\)\textsc-free Edge Deletion
- Kernelization and complexity results for connectivity augmentation problems
- Kernelization for cycle transversal problems
- Kernelization. Theory of parameterized preprocessing
- Kernels for feedback arc set in tournaments
- Length-bounded cuts: proper interval graphs and structural parameters
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Linear recognition of almost interval graphs
- Listing all potential maximal cliques of a graph
- Lower bounds for kernelizations and other preprocessing procedures
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- Maximal Flow Through a Network
- Measuring the vulnerability for classes of intersection graphs
- Metric violation distance: hardness and approximation
- Minimum bisection is fixed-parameter tractable
- Minimum degree up to local complementation: bounds, parameterized complexity, and exact algorithms
- Minimum fill-in: inapproximability and almost tight lower bounds
- Modification to Planarity is Fixed Parameter Tractable
- Multi-budgeted directed cuts
- Multicut Is FPT
- Networks, crowds and markets. Reasoning about a highly connected world.
- NP-completeness results for edge modification problems
- Obtaining a bipartite graph by contracting few edges
- Obtaining planarity by contracting few edges
- Obtaining split graphs by edge contraction
- Odd multiway cut in directed acyclic graphs
- On algorithms employing treewidth for L-bounded cut problems
- On Editing Graphs into 2-Club Clusters
- On Eulerian extensions and their application to no-wait flowshop scheduling
- On generating triangle-free graphs
- On graph powers for leaf-labeled trees
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- On problems without polynomial kernels
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- On the clique editing problem
- On the complexity of multi-parameterized cluster editing
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- On the parameterized complexity of computing graph bisections
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
- On the parameterized complexity of graph modification to first-order logic properties
- Optimal covering of cacti by vertex-disjoint paths
- Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
- Parameterized algorithms
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
- Parameterized algorithms to preserve connectivity
- Parameterized analysis and crossing minimization problems
- Parameterized aspects of strong subgraph closure
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Parameterized complexity of Eulerian deletion problems
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of finding regular induced subgraphs
- Parameterized complexity of length-bounded cuts and multicuts
- Parameterized complexity of vertex colouring
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized dynamic cluster editing
- Parameterized Eulerian strong component arc deletion problem on tournaments
- Parameterized graph separation problems
- Parameterized lower bound and improved kernel for diamond-free edge deletion
- Parameterized problems related to Seidel's switching
- Parameterized tractability of multiway cut with parity constraints
- Parametrized complexity theory.
- Partial complementation of graphs
- Path-contractions, edge deletions and connectivity preservation
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Planar disjoint-paths completion
- Polynomial kernelization for removing induced claws and diamonds
- Polynomial kernels for 3-leaf power graph modification problems
- Polynomial kernels for paw-free edge modification problems
- Polynomial kernels for proper interval completion and related problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Proper interval vertex deletion
- Randomized parameterized algorithms for co-path set problem
- Rank reduction of oriented graphs by vertex and edge deletions
- Rank-width and vertex-minors
- Reducing rank of the adjacency matrix by graph modification
- Rotation distance is fixed-parameter tractable
- Rotation Distance, Triangulations, and Hyperbolic Geometry
- Simple and improved parameterized algorithms for multiterminal cuts
- Social network data analytics
- Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- Structured connectivity augmentation
- Subexponential algorithm for d-cluster edge deletion: exception or rule?
- Subexponential parameterized algorithm for {\textsc{Interval Completion}}
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
- The complexity of degree anonymization by graph contractions
- The complexity of degree anonymization by vertex addition
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The Complexity of Multiterminal Cuts
- The minimum k-way cut of bounded size is fixed-parameter tractable
- The minimum augmentation of any graph to aK-edge-connected graph
- The node-deletion problem for hereditary properties is NP-complete
- The parameterized complexity of editing graphs for bounded degeneracy
- The parametric complexity of graph diameter augmentation
- The spanning subgraphs of eulerian graphs
- The splittance of a graph
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Tractability of König edge deletion problems
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Treewidth and minimum fill-in: Grouping the minimal separators
- Two edge modification problems without polynomial kernels
- Two-Layer Planarization: Improving on Parameterized Algorithmics
- Variants of plane diameter completion
- What's next? Future directions in parameterized complexity
- Wheel-Free Deletion Is W[2]-Hard
- Which problems have strongly exponential complexity?
- Win-win kernelization for degree sequence completion problems
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
Cited in
(35)- 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
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)
