Node-and edge-deletion NP-complete problems
From MaRDI portal
approximationcomputational complexityedge-deletiongraphgraph-propertyhereditarymaximum subgraphnode-deletionNP-completepolynomial hierarchy
Complexity of computation (including implicit computational complexity) (03D15) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)
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)- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- Parameterized complexity of finding regular induced subgraphs
- Bipartite density of triangle-free subcubic graphs
- Scheduling jobs with fixed start and end times
- A probabilistic estimator for the vertex deletion problem
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- Weakly bipartite graphs and the max-cut problem
- The edge Hamiltonian path problem is NP-complete
- Knowledge representation for mathematical discovery: Three experiments in graph theory
- Compositions in the bipartite subgraph polytope
- A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
- Approximations for the maximum acyclic subgraph problem
- On Halin subgraphs and supergraphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- \(k\)-edge subgraph problems
- Variable and term removal from Boolean formulae
- The VC-dimension of set systems defined by graphs
- A note on the bounded fragmentation property and its applications in network reliability
- The maximum edge biclique problem is NP-complete
- Edge-disjoint odd cycles in planar graphs.
- Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights
- Detecting robust cliques in graphs subject to uncertain edge failures
- Maximum weight relaxed cliques and Russian doll search revisited
- New bounds for the signless Laplacian spread
- The critical node detection problem in networks: a survey
- Reconstructing gene trees from Fitch's xenology relation
- On the NP-hardness of edge-deletion and -contraction problems
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- New algorithms for the weighted maximum cut problem on graphs
- Propositional truth maintenance systems: Classification and complexity analysis
- Maximum directed cuts in graphs with degree constraints
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Exact exponential-time algorithms for finding bicliques
- On structured output training: hard cases and an efficient alternative
- Efficient algorithms for acyclic colorings of graphs
- Online node- and edge-deletion problems with advice
- New formulae for the bipartite vertex frustration and decycling number of graphs
- Computing maximum \(k\)-defective cliques in massive graphs
- Finding the root graph through minimum edge deletion
- Reducing graph transversals via edge contractions
- Algorithmic aspects of secure connected domination in graphs
- Algorithmic aspects of Roman domination in graphs
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- A study of the performance of classical minimizers in the quantum approximate optimization algorithm
- Revising Johnson's table for the 21st century
- A polynomial kernel for bipartite permutation vertex deletion
- (Sub)linear kernels for edge modification problems toward structured graph classes
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- Hardness results of connected power domination for bipartite graphs and chordal graphs
- The maximum independent union of cliques problem: complexity and exact approaches
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Maximum cuts in \(\mathscr{H} \)-free graphs
- Coloring temporal graphs
- An effective branch-and-bound algorithm for the maximum s-bundle problem
- The ferry cover problem
- New kernels for several problems on planar graphs
- Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- A bound on judicious bipartitions of directed graphs
- Triangle edge deletion on planar glasses-free RGB-digraphs
- A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
- Tree-edges deletion problems with bounded diameter obstruction sets
- Additive approximation for edge-deletion problems
- Mathematical programming approaches for dual multicast routing problem with multilayer risk cost
- Minimum bisection is NP-hard on unit disk graphs
- Editing to a connected graph of given degrees
- Deletion graph problems based on deadlock resolution
- On independent sets and bicliques in graphs
- Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
- An exact algorithm for MAX-CUT in sparse graphs
- On the hardness of optimization in power-law graphs
- Triangle-free subcubic graphs with minimum bipartite density
- On maximum planar induced subgraphs
- NP-completeness results for edge modification problems
- Bipartite subgraphs of triangle-free subcubic graphs
- Heuristics for the maximum outerplanar subgraph problem
- On the typical case complexity of graph optimization
- Biased partitions and judicious \(k\)-partitions of graphs
- Scale reduction techniques for computing maximum induced bicliques
- Complexity aspects of variants of independent Roman domination in graphs
- On the computational complexity of the bipartizing matching problem
- Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
- On judicious partitions of uniform hypergraphs
- SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
- Parameterized enumeration for modification problems
- Cycle transversals in bounded degree graphs
- Augmenting approach for some maximum set problems
- Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
- Clique cycle-transversals in distance-hereditary graphs
- Duality and admissible transformations in combinatorial optimization
- Max-Cut and containment relations in graphs
- On the small cycle transversal of planar graphs
- Planarization and acyclic colorings of subcubic claw-free graphs
- Rank correlation coefficient correction by removing worst cases
- Inverse chromatic number problems in interval and permutation graphs
- Editing to a planar graph of given degrees
- Reducing rank of the adjacency matrix by graph modification
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)
