3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Perfect! I wouldn't have thought to go about searching for it under those terms. Thanks! $\endgroup$ – Alex Meiburg Feb 7 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.