Trimming forests is hard (unless they are made of stars)
From MaRDI portal
Publication:6654119
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)
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)
