# Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $$G$$ with weights $$w_e$$ on the edges, choose a subset $$S$$ of the ''edges'' such that $$S$$ doesn't contain any 3-cycles, maximizing $$\sum_{e\in S} w_e$$.

Is this problem NP-hard? I thought I saw some mention or folk-theorems that it was, but I can't find anything. There is a similar problem which is known to be NP-hard:

Given a graph $$G$$ with weights $$w_v$$ on the vertices, choose a subset $$S$$ of the ''vertices'' such that the induced subgraph $$G_S$$ doesn't contain any 3-cycles, maximizing $$\sum_{v\in S} w_v$$.

There are many sources online talking about how MAX-IND-SET can be reduced to this. It's not immediately obvious to me if this generalizes to the above, though. The closest thing I did find was https://www.sciencedirect.com/science/article/pii/S0166218X14002182 which mentions that finding maximum-cardinality triangle-free 2-matchings (so that $$S$$ has max degree 2) is easy, and it seemed to suggest that it would work for the weighted version as well, although I didn't quite follow it all the way through.

Anyone have a reference for this, or want to provide a reduction? :)

The problem is $$NP$$-complete even in the unweighted case (e.g.: all edge weights are equal to $$1$$). Instead of looking for a maximum edge-induced, triangle-free subgraph we may equivalently consider the minimum number of edges to delete from the original graph in order to leave a triangle-free graph. This problem (and other, related problems) are demonstrated to be $$NP$$-complete in [1]:
If $$\pi$$ is a property on graphs or digraphs, the edge-deletion problem can be stated as follows: find the minimum number of edges whose deletion results in a subgraph (or subdigraph) satisfying property $$\pi$$. Several well-studied graph problems can be formulated as edge-deletion problems.
In this paper we show that the edge-deletion problem is NP-complete for the following properties: (1) without cycles of specified length l, or of any length $$\leqq l$$, (2) connected and degree-constrained, (3) outerplanar, (4) transitive digraph, (5) line-invertible, (6) bipartite, (7) transitively orientable. For problems (5), (6), (7) we determine the best possible bounds on the node-degrees for which the problems remain NP-complete.