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

DOI10.1137/23m1609373MaRDI QIDQ6654119

Asaf Shapira, Yevgeny Levanzov, Lior Gishboliner

Publication date: 18 December 2024

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

zbMATH Keywords

computational complexityErdős-Sós conjectureedge modification problem

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• Characterizing and computing minimal cograph completions
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the number of edges of quadrilateral-free graphs
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• On the parameterized complexity of graph modification to first-order logic properties
• Editing to a graph of given degrees
• Additive approximation for edge-deletion problems
• Parameterized complexity of Eulerian deletion problems
• On maximal paths and circuits of graphs
• An Application of Duality to Edge-Deletion Problems
• Edge-Deletion Problems
• Cograph editing: Merging modules is equivalent to editing P_4s
• The Erdős‐Sós Conjecture for trees of diameter four
• On the completeness of a generalized matching problem
• Node-and edge-deletion NP-complete problems
• The History of Degenerate (Bipartite) Extremal Graph Problems
• A Short Proof of the Factor Theorem for Finite Graphs
• A survey of parameterized algorithms and the complexity of edge modification

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