Fixed-parameter tractability of graph modification problems for hereditary properties
From MaRDI portal
Publication:1352005
DOI10.1016/0020-0190(96)00050-6zbMath0875.68702OpenAlexW2144050783WikidataQ56474996 ScholiaQ56474996MaRDI QIDQ1352005
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00050-6
Related Items
Paths to Trees and Cacti ⋮ Assessing the Computational Complexity of Multi-layer Subgraph Detection ⋮ Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ Fast Quasi-Threshold Editing ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Editing to a Planar Graph of Given Degrees ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ Graph-Based Data Clustering with Overlaps ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Structural parameterization of cluster deletion ⋮ An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the Advice Complexity of Online Edge- and Node-Deletion Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A naive algorithm for feedback vertex set ⋮ Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs ⋮ Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ Quadratic vertex kernel for split vertex deletion ⋮ On structural parameterizations of load coloring ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Vertex deletion into bipartite permutation graphs ⋮ Complexity classification of some edge modification problems ⋮ Clustering with Partial Information ⋮ Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ Proper Interval Vertex Deletion ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized Enumeration for Modification Problems ⋮ Polynomial kernels for paw-free edge modification problems ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ On structural parameterizations of firefighting ⋮ Polynomial Kernelization for Removing Induced Claws and Diamonds ⋮ Exploring the Subexponential Complexity of Completion Problems ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ Parameterized Graph Editing with Chosen Vertex Degrees ⋮ Unnamed Item ⋮ The Multi-parameterized Cluster Editing Problem ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Minimal triangulations of graphs: a survey ⋮ Parameterized coloring problems on chordal graphs ⋮ On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ On structural parameterizations of load coloring ⋮ Additive approximation of generalized Turán questions ⋮ Structural parameterizations for boxicity ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Win-win kernelization for degree sequence completion problems ⋮ Chordal editing is fixed-parameter tractable ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ Faster FPT algorithms for deletion to pairs of graph classes ⋮ Streaming deletion problems parameterized by vertex cover ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Parameterizing edge modification problems above lower bounds ⋮ Parameterized complexity of the induced subgraph problem in directed graphs ⋮ Additive approximation for edge-deletion problems ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Vertex deletion into bipartite permutation graphs ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Two edge modification problems without polynomial kernels ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} ⋮ Editing to a connected graph of given degrees ⋮ On the complexity of multi-parameterized cluster editing ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Parameterized aspects of strong subgraph closure ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Polynomial kernels for proper interval completion and related problems ⋮ The cluster deletion problem for cographs ⋮ Editing to Eulerian graphs ⋮ Parameterized complexity of finding connected induced subgraphs ⋮ Obtaining split graphs by edge contraction ⋮ Obtaining a planar graph by vertex deletion ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ Parameterized complexity of even/odd subgraph problems ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Graph-based data clustering with overlaps ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Editing graphs into disjoint unions of dense clusters ⋮ Faster parameterized algorithms for \textsc{Minimum Fill-in} ⋮ Searching for better fill-in ⋮ Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes ⋮ Online node- and edge-deletion problems with advice ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ A linear-time algorithm for computing the intersection of all odd cycles in a graph ⋮ Approximate association via dissociation ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Unit interval editing is fixed-parameter tractable ⋮ Fixed-parameter complexity of minimum profile problems ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Paths to trees and cacti ⋮ Complexity and parameterized algorithms for cograph editing ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ Characterizing and computing minimal cograph completions ⋮ Chordal deletion is fixed-parameter tractable ⋮ On the interval completion of chordal graphs ⋮ Clustering with partial information ⋮ Applying modular decomposition to parameterized cluster editing problems ⋮ Kernels for packing and covering problems ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Dynamic parameterized problems ⋮ Vertex deletion problems on chordal graphs ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Editing to a planar graph of given degrees ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Complexity of modification problems for reciprocal best match graphs ⋮ A polynomial kernel for trivially perfect editing ⋮ On the threshold of intractability ⋮ Parameterized complexity of vertex colouring ⋮ Faster algorithms for cograph edge modification problems ⋮ Dynamically maintaining split graphs ⋮ Parameterized complexity of finding regular induced subgraphs ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations ⋮ Structural parameterizations of Tracking Paths problem ⋮ Tractability of König edge deletion problems ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Parameterized complexity of finding subgraphs with hereditary properties. ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ Modifying a graph using vertex elimination ⋮ Faster parameterized algorithms for deletion to split graphs ⋮ A fast branching algorithm for cluster vertex deletion ⋮ An effective branching strategy based on structural relationship among multiple forbidden induced subgraphs ⋮ Editing to a graph of given degrees
Cites Work
- Complement reducible graphs
- Generating binary trees by transpositions
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Node-Deletion NP-Complete Problems
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Node-and edge-deletion NP-complete problems
- On the complexity of the Maximum Subgraph Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
