The node-deletion problem for hereditary properties is NP-complete

1980/04/01 by John M. Lewis, Mihalis Yannakakis · 30 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems

paper · doi:10.1016/0022-0000(80)90060-4

Cited by

• Frustration index of a signed planar graph and the feedback vertex set
• A polynomial kernel for proper Helly circular-arc vertex deletion
• Linear Recognition of Almost Interval Graphs
• Extended formulations for induced tree and path polytopes of chordal graphs
• A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex\n Deletion
• Polynomial Kernels for Paw-free Edge Modification Problems
• A Complexity Analysis of the c-Closed Vertex Deletion Problem
• FO and MSO approach to Some Graph Problems: Approximation and Poly time Results
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Editing to a Graph of Given Degrees
• Editing to a Connected Graph of Given Degrees
• The maximum k-colorable subgraph problem and related problems
• Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection\n Graph Classes
• A Finer View of the Parameterized Landscape of Labeled Graph Contractions
• On the Parameterized Complexity of Reconfiguration Problems
• Gate-Based and Annealing-Based Quantum Algorithms for the Maximum K-Plex Problem
• Additive approximation for edge-deletion problems
• Editing to Eulerian Graphs
• Parameterized complexity dichotomy for (r,ℓ)-Vertex Deletion
• A Polynomial kernel for Proper Interval Vertex Deletion
• Finding small separators in linear time via treewidth reduction
• A Structural Characterization for Certifying Robinsonian Matrices
• Linear kernels and single-exponential algorithms via protrusion decompositions
• Coloring problem of signed interval graphs
• d-COS-R is FPT via Interval Deletion
• Parameterized Complexity of Eulerian Deletion Problems. [europepmc]
• Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. [europepmc]
• Vertex Deletion into Bipartite Permutation Graphs. [europepmc]
• The critical node detection problem in hypergraphs using weighted node degree centrality. [europepmc]
• Orthology and near-cographs in the context of phylogenetic networks. [europepmc]