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?

  • $\begingroup$ Two questions: (1) do you really mean to allow arbitrary nonnegative real-valued edge-weights, as your notation "$w(e)\geq0$" seems to suggest? (2) do you really mean "set cover problem" in the standard sense (i.e. set of edges of a hypergraph whose union equals the ground-set)? The reason for my asking (2) is that, for reasons I can't go into in a comment, your problem feels much more like the (somewhat dual) problem of minimum vertex covers (synonym: transversal; synonym: hitting set). I recall that if combinatorialists say 'X cover' they mean 'cover consisting of Xs'. $\endgroup$ – Peter Heinig Apr 15 '18 at 18:10
  • $\begingroup$ @PeterHeinig Thank you for your interest. (1) True. (2) True. I have answered my question, but I would appreciate if you can help me to get a deeper or better understanding if possible. $\endgroup$ – user122122 Apr 15 '18 at 18:31

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^{*}$ .

  • $\begingroup$ Comments: (1) The opening paragraph is vague to the point of being incomprehensible, and anyway, it is not necessary to write an introduction to answer the question. I'd recommend removing the opening paragraph. (2) A nitpick: the sentence "For each edge $e$, we define a set $T_e$ that includes the triangles that contain $e$." is not a mathematical definition, because this rather reads like an opening sentence announcing a precise definition of $T_e$ to be given later, and can be interpreted as if $T_e$ might be a strict superset of the set of all triangles containing $e$. I recommend [...] $\endgroup$ – Peter Heinig Apr 16 '18 at 6:00
  • $\begingroup$ [...] to replace it with "For each $e$, let $T_e$ denote the set of all triangles containing $e$." (3) The sentence "We next attribute the weight of edge $e$ to $T_e$." reads awkward (to me), expecially the "attribute". I' recommend to define an explicit weight-function.(4) Most seriously, I am virtually sure that your defining $T^\ast$ as consisting of ordered tuples is inappropriate or even wrong, and ruins the statement in "As a result [...] that cover $T^\ast$." I currently don't have time to write a counterexample, but would like to recommend that you reconsider. $\endgroup$ – Peter Heinig Apr 16 '18 at 6:06
  • $\begingroup$ Thank you @PeterHeinig, I updated (1) to (3) according to your guides! However, I think (4) will not cause any issues; I ran the code on few samples. Please feel free to correct me anytime. $\endgroup$ – user122122 Apr 16 '18 at 8:37
  • $\begingroup$ Comments: (5) on a data-type note, let me first mention that for your "finding the minimum total weight sub-collection of $T_e$ that cover $T^\ast$" to be meaningful, each $T_e$ must be a hyperedge of a hypergraph on ground-set $T^\ast$, which, as already mentioned, you have defined to be a set or ordered triples of edges. However, your $T_e$ is "a set of triangles containing $e$", and the standard meaning of "triangle" is 'complete graph on three vertices', which is not the same as an ordered triple of edges. Graph-theory nowadays must not tolerate such formal flaws; please [...] $\endgroup$ – Peter Heinig Apr 18 '18 at 7:33
  • $\begingroup$ [...] please make your answer formally correct. (6) On a mathematical note, I still doubt that it is possible to express the problem as a set cover problem in the way that you were suggesting in the version 2018-04-16 08:32:57Z. Even if you correct the data-type issues mentioned in (5) by letting $T_e$ denote the set of all ordered triples of edges of triangles containing $e$, with edge $e$ as the first component of the triple and the orientation chosen randomly, the reduction to a set cover-problem does not seem to work: consider the example of the graph being a single triangle with [...] $\endgroup$ – Peter Heinig Apr 18 '18 at 7:40

Your Answer

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