Fixed-parameter tractability of graph modification problems for hereditary properties
From MaRDI portal
Publication:1352005
DOI10.1016/0020-0190(96)00050-6zbMath0875.68702WikidataQ56474996 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
68R10: Graph theory (including graph drawing) in computer science
Related Items
Unnamed Item, Unnamed Item, Cograph editing: Merging modules is equivalent to editing P_4s, A Polynomial Kernel for Diamond-Free Editing, On the Parameterized Complexity of Contraction to Generalization of Trees., Vertex Deletion Problems on Chordal Graphs, Paths to Trees and Cacti, Assessing the Computational Complexity of Multi-layer Subgraph Detection, Graph-Based Data Clustering with Overlaps, Dichotomy Results on the Hardness of $H$-free Edge Modification Problems, 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, Parameterized Graph Editing with Chosen Vertex Degrees, Unnamed Item, Unnamed Item, Unnamed Item, Quadratic vertex kernel for split vertex deletion, Complexity classification of some edge modification problems, Faster and enhanced inclusion-minimal cograph completion, Conflict free version of covering problems on graphs: classical and parameterized, Polynomial kernels for paw-free edge modification problems, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, A Subexponential Parameterized Algorithm for Proper Interval Completion, On structural parameterizations of firefighting, Chordless Cycle Packing Is Fixed-Parameter Tractable, A Polynomial Kernel for Line Graph Deletion, Unnamed Item, Unnamed Item, Vertex deletion into bipartite permutation graphs, On the Parameterized Approximability of Contraction to Classes of Chordal Graphs, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable, \((1,1)\)-cluster editing is polynomial-time solvable, Streaming deletion problems Parameterized by vertex cover, Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes, Computing connected-\(k\)-subgraph cover with connectivity requirement, Deletion to scattered graph classes. I: Case of finite number of graph classes, A survey of parameterized algorithms and the complexity of edge modification, On the Advice Complexity of Online Edge- and Node-Deletion Problems, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, A cubic vertex-kernel for \textsc{Trivially Perfect Editing}, Parameterized Enumeration for Modification Problems, 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, The Multi-parameterized Cluster Editing Problem, 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, Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Proper Interval Vertex Deletion, Polynomial Kernels for Proper Interval Completion and Related Problems, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Parameterized Complexity of Eulerian Deletion Problems, Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property, Editing to a Planar Graph of Given Degrees, Reducing Rank of the Adjacency Matrix by Graph Modification, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, Fast Quasi-Threshold Editing, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees, Wheel-Free Deletion Is W[2-Hard], Characterizing and Computing Minimal Cograph Completions, Obtaining a Planar Graph by Vertex Deletion, Clustering with Partial Information, Two Edge Modification Problems without Polynomial Kernels, A fast branching algorithm for cluster vertex deletion, Structural parameterizations for boxicity, Win-win kernelization for degree sequence completion problems, Chordal editing is fixed-parameter tractable, Reducing rank of the adjacency matrix by graph modification, Parameterized complexity of vertex deletion into perfect graph classes, Polynomial kernels for proper interval completion and related problems, The cluster deletion problem for cographs, Graph-based data clustering with overlaps, A survey of the algorithmic aspects of modular decomposition, A faster algorithm for the cluster editing problem on proper interval graphs, Approximate association via dissociation, Improved kernel results for some FPT problems based on simple observations, Unit interval editing is fixed-parameter tractable, Parameterized complexity of even/odd subgraph problems, Editing graphs into disjoint unions of dense clusters, Faster parameterized algorithms for \textsc{Minimum Fill-in}, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Complexity and parameterized algorithms for cograph editing, Dynamic parameterized problems, The parameterized complexity of \(k\)-edge induced subgraphs, Editing to a planar graph of given degrees, 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, Editing to Eulerian graphs, Parameterized complexity of finding connected induced subgraphs, Obtaining split graphs by edge contraction, An FPT algorithm for the vertex cover \(P_4\) problem, Fixed-parameter complexity of minimum profile problems, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Characterizing and computing minimal cograph completions, Chordal deletion is fixed-parameter tractable, Fixed-parameter algorithms for cluster vertex deletion, Closest 4-leaf power is fixed-parameter tractable, Dynamically maintaining split graphs, Parameterized complexity of finding regular induced subgraphs, Deleting edges to restrict the size of an epidemic: a new application for treewidth, Parameterizing edge modification problems above lower bounds, Two edge modification problems without polynomial kernels, On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}, The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs, Vertex deletion problems on chordal graphs, Reconstructing gene trees from Fitch's xenology relation, A polynomial kernel for trivially perfect editing, Parameterized complexity of vertex colouring, Parameterized complexity of finding subgraphs with hereditary properties., On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, Proper interval vertex deletion, Online node- and edge-deletion problems with advice, Paths to trees and cacti, On the parameterized complexity of contraction to generalization of trees, Faster parameterized algorithm for cluster vertex deletion, Subexponential parameterized algorithms and kernelization on almost chordal graphs, On the threshold of intractability, 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, (Sub)linear kernels for edge modification problems toward structured graph classes, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, 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, Vertex deletion into bipartite permutation graphs, Distance from triviality 2.0: hybrid parameterizations, Parameterized aspects of strong subgraph closure, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Edge deletion problems: branching facilitated by modular decomposition, Minimum fill-in of sparse graphs: kernelization and approximation, Clustering with partial information, Applying modular decomposition to parameterized cluster editing problems, Kernels for packing and covering problems, Complexity of modification problems for reciprocal best match graphs, Faster algorithms for cograph edge modification problems, Tractability of König edge deletion problems, A completeness theory for polynomial (Turing) kernelization, Modifying a graph using vertex elimination, 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 complexity of the induced subgraph problem in directed graphs, Additive approximation for edge-deletion problems, Polynomial kernelization for removing induced claws and diamonds, Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs, 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, Obtaining a planar graph by vertex deletion, Contracting graphs to paths and trees, Parameterized complexity of Eulerian deletion problems, Searching for better fill-in, On the interval completion of chordal graphs, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
