Given a graph $G$, the problem of determining the minimum size $\tau(G)$ of a set of edges $X$ such that $G-X$ is triangle-free is indeed NP-complete. This was proved by Yannakakis. Regarding bounds for $\tau(G)$, we can consider the following dual problem. Let $\nu(G)$ be the maximum number of edge-disjoint triangles of $G$. Clearly $\nu(G) \leq \tau(G) \leq 3\nu(G)$. A famous conjecture of Tuza asserts:

$\tau(G) \leq 2\nu(G)$, for all graphs $G$.

The complete graph $K_4$ shows that this bound is best possible. Tuza's conjecture is still open, but it has been shown to hold for many restricted graph classes. For example it holds for threshold graphs by this recent paper of Bonamy, Bożyk, Grzesik, Hatzel, Masařík, Novotná, and Okrasa. The best general bound is by Haxell, who proved that $\tau(G) \leq \frac{66}{23} \nu(G)$ for all graphs $G$.

Given a graph $G$, the problem of determining the minimum size $\tau(G)$ of a set of edges $X$ such that $G-X$ is triangle-free is indeed NP-complete. This was proved by Yannakakis. Regarding bounds for $\tau(G)$, we can consider the following dual problem. Let $\nu(G)$ be the maximum number of edge-disjoint triangles of $G$. Clearly $\nu(G) \leq \tau(G) \leq 3\nu(G)$. A famous conjecture of Tuza asserts:

$\tau(G) \leq 2\nu(G)$, for all graphs $G$.

The complete graph $K_4$ shows that this bound is best possible. Tuza's conjecture is still open, but it has been shown to hold for many restricted graph classes. For example it holds for threshold graphs by this recent paper of Bonamy, Bożyk, Grzesik, Hatzel, Masařík, Novotná, and Okrasa. The best general bound is by Haxell, who proved that $\tau(G) \leq \frac{66}{23} \nu(G)$ for all graphs $G$.