Assume that we are given a weighted, undirected graph $G = (V; E)$ where each edge $e \in E$ is assigned weight $w(e) \geq 0$. The goal is to remove a set of edges $D \subseteq E$ with minimum weight such that the remaining graph $G = (V; E\setminus D)$ has no triangles.


How can we formulate this problem as a set cover problem?



Removing the minimum number of edges to make a graph triangle-free (using set cover)
In order to formulate the given question as a set cover problem, let's assume that $T^{\*}$ to be the set of all triangles in the graph. 


$T^{\*}=\{(e\_{i}, e\_{j}, e\_{k})\in E^{3}: e\_{i}, e\_{j}, e\_{k}$ form a triangle$\}$


For each $e$, let $T\_{e}$ denote the set of all triangles containing $e$. We define the weight of each each set $T\_{e}$ to be the weight of its corresponding edge $e$ ($w(T\_{e})=w(e)$). In result of these changes, the problem of interest would become finding the minimum total weight sub-collection of $T\_{e}$'s that cover $T^{\*}$. And this is exactly the problem of weighted set cover.


In sum, we could formulate the problem of *finding the minimum weight set of edges that destroy triangles* as the problem of *finding the minimum total weight subcollection of $T\_{e}$'s that cover $T^{\*}$* .


