Trimming forests is hard (unless they are made of stars)

DOI10.1137/23M1609373MaRDI QIDQ6654119zbMATH OpenFDO

Authors Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Publication date 18 December 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1609373

zbMATH Keywords

computational complexityedge modification problemErdős-Sós conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Dichotomy results on the hardness of H-free edge modification problems
• Hardness of approximation for \(H\)-free edge modification problems
• Hardness of approximation for \(H\)-free edge modification problems
• Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems
• The complexity of some edge deletion problems

Cites work

• A Short Proof of the Factor Theorem for Finite Graphs
• A survey of parameterized algorithms and the complexity of edge modification
• Additive approximation for edge-deletion problems
• An Application of Duality to Edge-Deletion Problems
• Characterizing and computing minimal cograph completions
• Cograph editing: Merging modules is equivalent to editing P₄s
• Edge-Deletion Problems
• Editing graphs to satisfy degree constraints: a parameterized approach
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 1317271 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Node-and edge-deletion NP-complete problems
• On maximal paths and circuits of graphs
• On the completeness of a generalized matching problem
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the number of edges of quadrilateral-free graphs
• On the parameterized complexity of graph modification to first-order logic properties
• Parameterized complexity of Eulerian deletion problems
• The Erdős‐Sós Conjecture for trees of diameter four
• The history of degenerate (bipartite) extremal graph problems
• The node-deletion problem for hereditary properties is NP-complete

This page was built for publication: Trimming forests is hard (unless they are made of stars)

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