Fixed-parameter tractability of graph modification problems for hereditary properties

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

zbMATH Keywords

Graph algorithms; Design of algorithms; Fixed-parameter tractability; Graph modification problems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Graph-Based Data Clustering with Overlaps, 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, Complexity classification of some edge modification problems, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, A Subexponential Parameterized Algorithm for Proper Interval Completion, 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, 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, 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, Minimal triangulations of graphs: a survey, Parameterized coloring problems on chordal graphs, 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, Parameterizing edge modification problems above lower bounds, 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, On the threshold of intractability, 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, 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, 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, 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, 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

Cites Work