Node-and edge-deletion NP-complete problems
From MaRDI portal
Publication:5402565
DOI10.1145/800133.804355zbMath1282.68131OpenAlexW2045027193WikidataQ56209809 ScholiaQ56209809MaRDI QIDQ5402565
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
computational complexitygraphapproximationNP-completepolynomial hierarchyhereditaryedge-deletionmaximum subgraphnode-deletiongraph-property
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
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, 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, Scheduling jobs with fixed start and end times, Fixed-parameter tractability of graph modification problems for hereditary properties, Inverse chromatic number problems in interval and permutation graphs, \(k\)-edge subgraph problems, Hardness results of connected power domination for bipartite graphs and chordal graphs, Variable and term removal from Boolean formulae, The VC-dimension of set systems defined by graphs, New algorithms for the weighted maximum cut problem on graphs, Reducing rank of the adjacency matrix by graph modification, The max-cut problem on graphs not contractible to \(K_ 5\), Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, The maximum independent union of cliques problem: complexity and exact approaches, Parameterized complexity of fair deletion problems, Propositional truth maintenance systems: Classification and complexity analysis, Improved induced matchings in sparse graphs, Maximum directed cuts in graphs with degree constraints, A probabilistic estimator for the vertex deletion problem, Exact interdiction models and algorithms for disconnecting networks via node deletions, MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), Maximum weight relaxed cliques and Russian doll search revisited, On judicious bisections of graphs, An exact algorithm for the maximum probabilistic clique problem, On risk-averse maximum weighted subgraph problems, An integer programming framework for critical elements detection in graphs, Finding small stabilizers for unstable graphs, On a bipartition problem of Bollobás and Scott, Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs, On the removal of forbidden graphs by edge-deletion or by edge- contraction, Energy efficient monitoring in sensor networks, Local search is a PTAS for feedback vertex set in minor-free graphs, Exact exponential-time algorithms for finding bicliques, Kernelization for cycle transversal problems, Bicolored independent sets and bicliques, A note on the bounded fragmentation property and its applications in network reliability, Hardness of subgraph and supergraph problems in \(c\)-tournaments, The maximum edge biclique problem is NP-complete, \textsc{max-cut} and containment relations in graphs, On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs, On structured output training: hard cases and an efficient alternative, Edge-disjoint odd cycles in planar graphs., Weakly bipartite graphs and the max-cut problem, The edge Hamiltonian path problem is NP-complete, A bound for judicious \(k\)-partitions of graphs, Maximum cuts in \(\mathscr{H} \)-free graphs, The complexity of uniform Nash equilibria and related regular subgraph problems, New bounds for the signless Laplacian spread, Knowledge representation for mathematical discovery: Three experiments in graph theory, Biclique-colouring verification complexity and biclique-colouring power graphs, Efficient algorithms for acyclic colorings of graphs, Online node- and edge-deletion problems with advice, Coloring temporal graphs, An effective branch-and-bound algorithm for the maximum \(s\)-bundle problem, The critical node detection problem in networks: a survey, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, Compositions in the bipartite subgraph polytope, Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs, On the complexity of some subgraph problems, Optimal cuts in graphs and statistical mechanics, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, New formulae for the bipartite vertex frustration and decycling number of graphs, On the small cycle transversal of planar graphs, Consensus algorithms for the generation of all maximal bicliques, Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms, Generating bicliques of a graph in lexicographic order, More about NP-completeness in the frustration model of spin-glasses, Computing maximum \(k\)-defective cliques in massive graphs, Rank reduction of oriented graphs by vertex and edge deletions, Finding the root graph through minimum edge deletion, Reconstructing gene trees from Fitch's xenology relation, Editing to a planar graph of given degrees, Reducing graph transversals via edge contractions, Algorithmic aspects of secure connected domination in graphs, Algorithmic aspects of Roman domination in graphs, Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal, A study of the performance of classical minimizers in the quantum approximate optimization algorithm, Parameterized complexity of finding regular induced subgraphs, A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis, Bipartite density of triangle-free subcubic graphs, On the NP-hardness of edge-deletion and -contraction problems, 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, Edge-contraction problems, Algorithms and complexity of \(s\)-club cluster vertex deletion, \((p,k)\)-coloring problems in line graphs, 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, 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
