Node-and edge-deletion NP-complete problems
From MaRDI portal
graphcomputational complexityapproximationNP-completepolynomial hierarchyhereditaryedge-deletionmaximum subgraphnode-deletiongraph-property
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
- The complexity of some edge deletion problems
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Tractability of König edge deletion problems
- Approximating power node-deletion problems
- NP-completeness of some edge-disjoint paths problems
- A new approach for approximating node deletion problems
- A unified approximation algorithm for node-deletion problems
- Edge deletion problems: branching facilitated by modular decomposition
- Vertex deletion problems on chordal graphs
- Vertex deletion problems on chordal graphs
Cited in
(only showing first 100 items - show all)- On independent sets and bicliques in graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- Planarization and acyclic colorings of subcubic claw-free graphs
- A simple variant of node connectivity is NP-complete
- Maximum bipartite subgraphs of geometric intersection graphs
- Edge-contraction problems
- scientific article; zbMATH DE number 2230213 (Why is no real title available?)
- Improved induced matchings in sparse graphs
- Energy efficient monitoring in sensor networks
- On Independent Sets and Bicliques in Graphs
- 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
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Finding small stabilizers for unstable graphs
- Conflict free version of covering problems on graphs: classical and parameterized
- Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
- Graph Bipartization and via minimization
- Parameterized enumeration for modification problems
- On the hardness of energy minimisation for crystal structure prediction
- An exact algorithm for the maximum probabilistic clique problem
- On risk-averse maximum weighted subgraph problems
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- Optimal cuts in graphs and statistical mechanics
- Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- On judicious partitions of uniform hypergraphs
- Editing to a connected graph of given degrees
- On the complexity of some subgraph problems
- Packing and Covering a Given Directed Graph in a Directed Graph
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
- NP-completeness results for edge modification problems
- On judicious bisections of graphs
- New bounds for the signless Laplacian spread
- An integer programming framework for critical elements detection in graphs
- Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- A bound for judicious \(k\)-partitions of graphs
- Propositional truth maintenance systems: Classification and complexity analysis
- New formulae for the bipartite vertex frustration and decycling number of graphs
- Augmenting approach for some maximum set problems
- An exact algorithm for MAX-CUT in sparse graphs
- Maximal and maximum transitive relation contained in a given binary relation
- Complexity issues of perfect Roman domination in graphs
- Reducing rank of the adjacency matrix by graph modification
- Single-sink fractionally subadditive network design
- Parameterized complexity of finding regular induced subgraphs
- Kernelization for cycle transversal problems
- Maximum directed cuts in digraphs with degree restriction
- Reconstructing gene trees from Fitch's xenology relation
- Algorithmic aspects of secure connected domination in graphs
- A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
- s-club cluster vertex deletion on interval and well-partitioned chordal graphs
- The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
- Scheduling jobs with fixed start and end times
- Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network
- VC-dimensions for graphs (extended abstract)
- Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
- Approximating power node-deletion problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the small cycle transversal of planar graphs
- On the NP-hardness of edge-deletion and -contraction problems
- Reducing the vertex cover number via edge contractions
- On the computational complexity of the bipartizing matching problem
- scientific article; zbMATH DE number 89391 (Why is no real title available?)
- Primal-dual approximation algorithms for feedback problems in planar graphs
- The complexity of uniform Nash equilibria and related regular subgraph problems
- Bicolored independent sets and bicliques
- Bipartite density of triangle-free subcubic graphs
- Biased partitions and judicious \(k\)-partitions of graphs
- \(k\)-edge subgraph problems
- Variable and term removal from Boolean formulae
- A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
- Rank reduction of oriented graphs by vertex and edge deletions
- Rank correlation coefficient correction by removing worst cases
- Clique cycle-transversals in distance-hereditary graphs
- Graph partitioning: an updated survey
- scientific article; zbMATH DE number 7236457 (Why is no real title available?)
- More about NP-completeness in the frustration model of spin-glasses
- Ordered vertex removal and subgraph problems
- Generating bicliques of a graph in lexicographic order
- Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
- A probabilistic estimator for the vertex deletion problem
- Algorithmic aspects of Roman domination in graphs
- Scale reduction techniques for computing maximum induced bicliques
- Consensus algorithms for the generation of all maximal bicliques
- scientific article; zbMATH DE number 4089594 (Why is no real title available?)
- \textsc{max-cut} and containment relations in graphs
- Detecting robust cliques in graphs subject to uncertain edge failures
- Complexity framework for forbidden subgraphs. I: The framework
- Hardness of bounding influence via graph modification
- New algorithms for the weighted maximum cut problem on graphs
- Complexity and polynomially solvable special cases of QUBO
- SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
- The ferry cover problem
- Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights
- The maximum independent union of cliques problem: complexity and exact approaches
This page was built for publication: Node-and edge-deletion NP-complete problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402565)
