NP-completeness results for edge modification problems

DOI10.1016/J.DAM.2006.03.031MaRDI QIDQ2500532zbMATH OpenOpenAlexFDO

Authors Pablo Burzyn, Guillermo Durán, Flavia Bonomo

Publication date 17 August 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2006.03.031

zbMATH Keywords

computational complexityedge modification problemsgraph classesNP-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Publication:4944968
• Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems
• Dichotomy results on the hardness of H-free edge modification problems
• Graph modification problem for some classes of graphs
• Node-and edge-deletion NP-complete problems

Cites work

• Algorithms for weakly triangulated graphs
• Bicliques in graphs. I: Bounds on their number
• Clique Graphs of Chordal and Path Graphs
• Complexity classification of some edge modification problems
• Computing the Minimum Fill-In is NP-Complete
• Coordinated graphs and clique graphs of clique-Helly perfect graphs
• Edge-Deletion Problems
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1107738 (Why is no real title available?)
• scientific article; zbMATH DE number 2096438 (Why is no real title available?)
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• scientific article; zbMATH DE number 2188345 (Why is no real title available?)
• scientific article; zbMATH DE number 6472574 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• scientific article; zbMATH DE number 2230201 (Why is no real title available?)
• Linear-time recognition of circular-arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On intervalizing k-colored graphs for DNA physical mapping
• On local convexity in graphs
• On the complexity of DNA physical mapping
• Orienting graphs to optimize reachability
• Polynomial time recognition of unit circular-arc graphs
• Recognition of Circle Graphs
• Recognizing Berge graphs
• Representation of a finite graph by a set of intervals on the real line
• Some complexity results about threshold graphs
• Some simplified NP-complete graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of some edge deletion problems
• The splittance of a graph

Cited in

(44)

• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Blockers and transversals
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Two edge modification problems without polynomial kernels
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem
• An NP-completeness result of edge search in graphs
• Indirect identification of horizontal gene transfer
• (Sub)linear kernels for edge modification problems toward structured graph classes
• Exact-2-relation graphs
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
• MPF problem over modified medial semigroup is NP-complete
• On the hardness of solving edge matching puzzles as SAT or CSP problems
• Editing to a connected graph of given degrees
• Parameterized complexity of Eulerian deletion problems
• A cubic-vertex kernel for flip consensus tree
• Critical edges for the assignment problem: complexity and exact resolution
• Biclique-Helly graphs
• On the computational complexity of the bipartizing matching problem
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
• Exploring the subexponential complexity of completion problems
• Efficient algorithms for Eulerian extension
• Parameterized complexity of Eulerian deletion problems
• Editing to a planar graph of given degrees
• Reducing rank of the adjacency matrix by graph modification
• Reducing rank of the adjacency matrix by graph modification
• Graph editing to a fixed target
• Graph modification problem for some classes of graphs
• Characterizing and Computing Minimal Cograph Completions
• Two edge modification problems without polynomial kernels
• NP-completeness for minimizing maximum edge length in grid embeddings
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• scientific article; zbMATH DE number 1420899 (Why is no real title available?)
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Matching interdiction
• A survey of parameterized algorithms and the complexity of edge modification
• Switches in Eulerian graphs
• Complexity and parameterized algorithms for cograph editing
• An improved kernelization algorithm for trivially perfect editing
• The st-planar edge completion problem is fixed-parameter tractable
• Editing to a planar graph of given degrees
• Editing to Eulerian graphs
• Characterizing and computing minimal cograph completions

This page was built for publication: NP-completeness results for edge modification problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500532)