On the removal of forbidden graphs by edge-deletion or by edge- contraction

DOI10.1016/0166-218X(81)90039-1zbMath0448.05052MaRDI QIDQ1146698

S. H. Smith

Publication date: 1981

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

zbMATH Keywords

NP-hardedge contractionedge-deletionremoval of forbidden graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items (19)

Paths to Trees and Cacti ⋮ Increasing the Minimum Degree of a Graph by Contractions ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Increasing the minimum degree of a graph by contractions ⋮ Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ On the parameterized complexity of grid contraction ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Contracting graphs to paths and trees ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Path Contraction Faster than $2^n$ ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ Path Contraction Faster Than 2^n ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the NP-hardness of edge-deletion and -contraction problems ⋮ Edge-contraction problems ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Cites Work

• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Node-and edge-deletion NP-complete problems

This page was built for publication: On the removal of forbidden graphs by edge-deletion or by edge- contraction