Graph modification problems are computational tasks where the goal is to change an input graph G using operations from a fixed set, in order to make the resulting graph satisfy a target property, which usually entails membership to a desired graph class C. Some well-known examples of operations include vertex-deletion, edge-deletion, edge-addition and edge-contraction. In this paper we address an operation known as subgraph complement. Given a graph G and a subset S of its vertices, the subgraph complement G ⊕ S is the graph resulting from complementing the edge set of the subgraph induced by S in G. We say that a graph H is a subgraph complement of G if there is an S such that H is isomorphic to G⊕S. For a graph class C, the Subgraph complementation to C is the problem of deciding, for a given graph G, whether G has a subgraph complement in C. This problem has been studied and its complexity has been settled for many classes C such as H -free graphs, for various families H , and for classes of bounded degeneracy. In this work, we focus on classes of graphs of minimum/maximum degree upper/lower bounded by some value k. In particular, we answer an open question of Antony et al. [Information Processing Letters 188, 106530 (2025)], by showing that Subgraph complementation to C is NP-complete when C is the class of graphs of minimum degree at least k , if k is part of the input. We also show that Subgraph complementation to k -regular parameterized by k is fixed-parameter tractable.

For a fixed property (graph class) Π, given a graph G and an integer k, the Π-deletion problem consists in deciding if we can turn G into a graph with the property Π by deleting at most k edges. The Π-deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class Π that imply the NP-hardness of the Π-deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard.