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

Question

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? :)

Answer 1

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.

1. Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10.2 (1981): 297-309.