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
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Parameterized complexity of finding regular induced subgraphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Exact interdiction models and algorithms for disconnecting networks via node deletions
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Biclique-colouring verification complexity and biclique-colouring power graphs
- On judicious bisections of graphs
- On judicious partitions of uniform hypergraphs
- Consensus algorithms for the generation of all maximal bicliques
- Graph Bipartization and via minimization
- scientific article; zbMATH DE number 7693181 (Why is no real title available?)
- An integer programming framework for critical elements detection in graphs
- The critical node detection problem in networks: a survey
- Exact exponential-time algorithms for finding bicliques
- Reducing rank of the adjacency matrix by graph modification
- Maximal and maximum transitive relation contained in a given binary relation
- An exact algorithm for MAX-CUT in sparse graphs
- Generating bicliques of a graph in lexicographic order
- Bicolored independent sets and bicliques
- On the NP-hardness of edge-deletion and -contraction problems
- Bipartite density of triangle-free subcubic graphs
- On the complexity of some subgraph problems
- Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
- Kernelization for cycle transversal problems
- On the small cycle transversal of planar graphs
- \(k\)-edge subgraph problems
- Augmenting approach for some maximum set problems
- Editing to a planar graph of given degrees
- Max-Cut and containment relations in graphs
- Detecting robust cliques in graphs subject to uncertain edge failures
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
- Heuristics for the maximum outerplanar subgraph problem
- Variable and term removal from Boolean formulae
- A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
- An exact algorithm for the maximum probabilistic clique problem
- On risk-averse maximum weighted subgraph problems
- Editing to a planar graph of given degrees
- Maximum directed cuts in graphs with degree constraints
- On the generation of bicliques of a graph
- Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
- \textsc{max-cut} and containment relations in graphs
- Fractals for kernelization lower bounds
- The maximum edge biclique problem is NP-complete
- Edge-contraction problems
- Planarization and acyclic colorings of subcubic claw-free graphs
- Compositions in the bipartite subgraph polytope
- The max-cut problem on graphs not contractible to \(K_ 5\)
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- On judicious bipartitions of graphs
- SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
- Scheduling jobs with fixed start and end times
- On the hardness of optimization in power-law graphs
- NP-completeness results for edge modification problems
- Improved induced matchings in sparse graphs
- The complexity of some edge deletion problems
- Weakly bipartite graphs and the max-cut problem
- NP-completeness: a retrospective
- Edge-disjoint odd cycles in planar graphs.
- A bound for judicious \(k\)-partitions of graphs
- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- On independent sets and bicliques in graphs
- Approximations for the maximum acyclic subgraph problem
- Maximum directed cuts in digraphs with degree restriction
- Inverse chromatic number problems in interval and permutation graphs
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
- A polynomial algorithm for the max-cut problem on graphs without long odd cycles
- Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
- Energy efficient monitoring in sensor networks
- The VC-dimension of set systems defined by graphs
- New formulae for the bipartite vertex frustration and decycling number of graphs
- Maximum cuts in \(\mathscr{H} \)-free graphs
- Editing to a connected graph of given degrees
- On the removal of forbidden graphs by edge-deletion or by edge- contraction
- The edge Hamiltonian path problem is NP-complete
- Triangle-free subcubic graphs with minimum bipartite density
- Energy Efficient Monitoring in Sensor Networks
- Additive approximation for edge-deletion problems
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Clique cycle-transversals in distance-hereditary graphs
- The complexity of uniform Nash equilibria and related regular subgraph problems
- (Sub)linear kernels for edge modification problems toward structured graph classes
- A polynomial kernel for bipartite permutation vertex deletion
- Tree-edges deletion problems with bounded diameter obstruction sets
- Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Hardness results of connected power domination for bipartite graphs and chordal graphs
- scientific article; zbMATH DE number 7236457 (Why is no real title available?)
- Complexity aspects of variants of independent Roman domination in graphs
- Coloring temporal graphs
- Trimming forests is hard (unless they are made of stars)
- Complexity issues of perfect Roman domination in graphs
- On the hardness of energy minimisation for crystal structure prediction
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- A study of the performance of classical minimizers in the quantum approximate optimization algorithm
- An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem
- Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Reconstructing gene trees from Fitch's xenology relation
- On percolation and \(\mathcal{NP}\)-hardness
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)
