A triangle packing in a graph G is a set of triangles in G that are edge-disjoint. A triangle cover in G is a set of edges in G such that every triangle in G contains at least one of these edges. (equivalently: a set of edges whose removal causes tt to be triangle-free). The maximum size of a triangle packing in G is denoted ν(G), and the minimum size of a triangle cover in G is denoted τ (G).
(1) Explain briefly why τ (G) ≤ 3ν(G).
(2) Give an example of a graph where τ (G) < 3ν(G).
Let A be the edge-triangle incidence matrix of G: the 0, 1-matrix with rows indexed by edges of G, columns indexed by triangles of G, and Ai,j = 1 iff edge i is a part of triangle j. Let T (G) denote the set of all triangles in G. Use A and T (G) to help answer the following questions.
(3) State an IP for which the characteristic vector of any triangle packing of G is a feasible solution, and ν(G) is the optimal value. Briefly justify your answer. (Use variables named x)
(4) State an IP for which the characteristic vector of any triangle cover of G is a feasible solution, and τ (G) is the optimal value. Briefly justify your answer. (Use variables named y)
(5) Take the LP-relaxation of each of your IPs in (3) and (4). (Note: These LPs will be duals, so packing and covering triangles are dual concepts in graphs).
(6) State the complimentary slackness conditions corresponding your pair of LPs in (5).
Suppose both of your LPs in (5) have optimal solutions. Let x∗ be an optimal solution to the LP-relaxation for the IP from (3), with optimal value ν∗(G). Let y∗ be an optimal solution to the LP-relaxation for the IP from (4), with optimal value T∗(G).
(7) Suppose that you are told that there is a triangle packing in G with at least k triangles. Suppose also that you are told that the following inequality holds:
e:e∈E(G),y∈*> 0∑(t:t∈T(G),e∈t∑x*t) ≤ 2k.
Prove that ν(G) ≤ ν∗(G) ≤ 2ν(G). (Hint: Use (6) and Strong Duality.)