Node-and edge-deletion NP-complete problems

DOI10.1145/800133.804355zbMath1282.68131DBLPconf/stoc/Yannakakis78OpenAlexW2045027193WikidataQ56209809 ScholiaQ56209809MaRDI QIDQ5402565

Mihalis Yannakakis

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804355

zbMATH Keywords

computational complexitygraphapproximationNP-completepolynomial hierarchyhereditaryedge-deletionmaximum subgraphnode-deletiongraph-property

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (only showing first 100 items - show all)

Further Results on Online Node- and Edge-Deletion Problems with Advice ⋮ Rank Correlation Coefficient Correction by Removing Worst Cases ⋮ Biased partitions and judicious \(k\)-partitions of graphs ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ On Independent Sets and Bicliques in Graphs ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Mathematical programming approaches for dual multicast routing problem with multilayer risk cost ⋮ Editing to a Planar Graph of Given Degrees ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ Maximal and Maximum Transitive Relation Contained in a Given Binary Relation ⋮ Unnamed Item ⋮ NP-completeness: A retrospective ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ Editing to a connected graph of given degrees ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ On the computational complexity of the bipartizing matching problem ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ On maximum ratio clique relaxations ⋮ Optimizing concurrency under Scheduling by Edge Reversal ⋮ Splitting plane graphs to outerplanarity ⋮ Reducing the vertex cover number via edge contractions ⋮ Lower Bounds for Maximum Weighted Cut ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Graph partitioning: an updated survey ⋮ VC-dimensions for graphs (extended abstract) ⋮ NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ Packing and Covering a Given Directed Graph in a Directed Graph ⋮ On the Advice Complexity of Online Edge- and Node-Deletion Problems ⋮ Hardness of bounding influence via graph modification ⋮ On independent sets and bicliques in graphs ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ Asymptotic bounds for clustering problems in random graphs ⋮ The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs ⋮ Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network ⋮ Fractals for Kernelization Lower Bounds ⋮ Contracting graphs to paths and trees ⋮ Unnamed Item ⋮ Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs ⋮ Unnamed Item ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ A polynomial algorithm for the max-cut problem on graphs without long odd cycles ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ Unnamed Item ⋮ Independent roman $\{3\}$-domination ⋮ On the hardness of optimization in power-law graphs ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ Unnamed Item ⋮ Duality and admissible transformations in combinatorial optimization ⋮ The ferry cover problem ⋮ On maximum planar induced subgraphs ⋮ Unnamed Item ⋮ NC algorithms for partitioning sparse graphs into induced forests with an application ⋮ Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs ⋮ Proportionally Fair Matching with Multiple Groups ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ max-cut and Containment Relations in Graphs ⋮ On the Small Cycle Transversal of Planar Graphs ⋮ On judicious bipartitions of graphs ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Packing and covering odd cycles in cubic plane graphs with small faces ⋮ New kernels for several problems on planar graphs ⋮ Parameterized Enumeration for Modification Problems ⋮ Complexity of Roman {2}-domination and the double Roman domination in graphs ⋮ Energy Efficient Monitoring in Sensor Networks ⋮ Bipartite subgraphs of triangle-free subcubic graphs ⋮ Unnamed Item ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Unnamed Item ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ A bound on judicious bipartitions of directed graphs ⋮ Maximum directed cuts in digraphs with degree restriction ⋮ On the generation of bicliques of a graph ⋮ Approximability of the eight-vertex model ⋮ Unnamed Item ⋮ Triangle edge deletion on planar glasses-free RGB-digraphs ⋮ Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs ⋮ Cycle transversals in bounded degree graphs ⋮ Improved Induced Matchings in Sparse Graphs ⋮ A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs ⋮ Heuristics for the maximum outerplanar subgraph problem ⋮ On the typical case complexity of graph optimization ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction* ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Algorithmic aspects of total Roman {3}-domination in graphs ⋮ Editing to a graph of given degrees ⋮ On judicious partitions of uniform hypergraphs ⋮ Approximations for the maximum acyclic subgraph problem ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Augmenting approach for some maximum set problems ⋮ Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Clique cycle-transversals in distance-hereditary graphs ⋮ On Halin subgraphs and supergraphs

This page was built for publication: Node-and edge-deletion NP-complete problems