Approximating the maximum weight of a triangle-free subgraph
03 Mar 2024This is a write-up of a problem that appeared on one of my course tests. The problem is as follows:
The problem is \(NP\)-hard, so we might as well try approximating it instead. The most natural triangle-free subgraphs are the bipartite subgraphs of \(G\) - how large a bipartite subgraph can we construct from \(G\) in polynomial time?
Hint 1: The problem is a classic example of a greedy algorithm.
Hint 2: Can you guarantee that for every vertex \(v\), the edge weight between \(v\) and its neighbors in its part is at most the edge weight between \(v\) and its neighbors in the other part? That would imply the problem.
Hint 3: Starting from an arbitrary partition and then greedily moving vertices across the parts may not be a good idea. Start from empty bins. There is a \(\mathcal{O}(n + m)\) time algorithm.
Solution: Set up two empty bins, which will serve as the bipartition. Order the vertices arbitrarily - \(v_1, …, v_n\). Starting from \(i = 1\), put \(v_i\) into the bin with the smaller total edge weight to the vertices already in the bin. Notice that each edge of the graph will be looked at precisely once, and at least half the total weight of the edges goes across the bins. The running time is the sum of the degrees + \(cn\) overhead - \(\mathcal{O}(n + m)\).
The motivation for this algorithm comes from the following inductive proof of the existence of such a subgraph. We induct on the number of vertices \(n\) - the statement is vacuously true when \(n = 1\). For \(n = k+1\), delete an arbitrary vertex \(v\); the rest of the graph, by hypothesis, has such a subgraph - suppose the partition is \([U, V]\). Finally, put \(v\) into the bin with the smaller total edge weight to the vertices already in the bin.
Before we get back to our original problem, let us consider the "complement" problem: finding a minimum weight subgraph \(H'\) such that every triangle in \(G\) contains at least one edge of \(H'\). It is clear that any solution \(H'\) when complemented in \(G\) is triangle-free. Can we manage to get a low-enough solution to the complement, then?
Hint 1: LP rounding/Primal Dual.
Solution: We first write down the LP (linear program) corresponding to the relaxation of the complement problem. Letting \(x_e\) denote the variable representing whether edge \(e\) is in our subgraph or not, we have the following LP relaxation:
\(\begin{aligned} \text{minimize} \quad & \sum_{e \in E} w_e x_e \\ \text{subject to} \quad & x_{uv} + x_{vw} + x_{wu} \geq 1 \quad \text{for all triangles $uvw$ in $G$} \\ & x_e \in \{0, 1\} \quad \text{for all $e \in E$}. \end{aligned}\)
This is actually an instance of the [set cover](https://en.wikipedia.org/wiki/Set_cover_problem) problem, which has an \(f\)-approximation rounding/Primal Dual algorithm (where \(f\) is the maximum number of sets containing an element of the universe - here, the elements are the triangles of the graph \(G\) and the sets are the edges; each edge covers triangles it is a part of and each triangle is covered by precisely 3 edges).
The rounding algorithm is easy; we solve the LP relaxation optimally, and then round every \(x_e\) with \(x_e^* \geq 1/3\) (\(*\) denoting the optimal solution) to \(1\), and the rest to \(0\). The resulting solution is integral, feasible for the integer linear program, and has scaled up the objective by at most a factor of \(3\).
The Primal Dual algorithm is also fairly simple, but we do not go into that here, at the moment.
We are ready for the first approximation algorithm for the original problem.
Hint 1: Leverage both algorithms we have already seen. How do you leverage two algorithms to get the best of both worlds?
Hint 2: Suppose the optimal value \(\text{OPT}_1 \leq \frac{5W}{6}\). Are we done? If this is not the case, does the algorithm we have for the complement problem help us?
Solution: Simply run both algorithms (of course, after running the second algorithm and getting a subgraph \(H'\) we must complement it in \(G\) to get a triangle-free subgraph), and take the larger of the two solutions. That way we are able to avoid the worst-case scenarios of each algorithm individually, if the worst-case scenarios are different for the two (they happen to be beautifully complementary in this case). Let \(h_1\) be the weight of the graph returned by the first algorithm, \(h_2\) by the second, and \(\mathcal{A} = \max(h_1, h_2)\) is the value returned by our final algorithm.
We have:
\[\begin{aligned}h_1 &\geq \frac{W}{2} = \frac{3}{5}\cdot\frac{5W}{6},\\ h_2 &\geq W - 3\text{OPT}_2 = W - 3(W - \text{OPT}_1) = 3\text{OPT}_1 - 2W.\end{aligned}\]If the optimal value \(\text{OPT}_1\) is at most \(\frac{5W}{6}\), then indeed, \(\mathcal{A} \geq h_1 \geq \frac{3}{5}\text{OPT}_1\). If this is not the case, then \(\text{OPT}_1 > \frac{5W}{6}\), and
\[\mathcal{A} \geq h_2 \geq 3\text{OPT}_1 - 2W \geq 3\text{OPT}_1 - 2\left(\frac{6\text{OPT}_1}{5}\right) = \frac{3}{5}\text{OPT}_1.\]Incredible, right?
It is also easy to see that bettering each of the two algorithms individually could improve the approximation factor of the final algorithm. The first algorithm is actually the best we can hope for; the max weight of a bipartite subgraph of the complete uniform-weight graph on \(n\) vertices is \(W\left(\frac{1}{2} + o_n(1)\right)\). The second algorithm, on the other hand, can be improved (thanks not to the fact that it is a set-cover; for the set cover that is the best we can hope for with that formulation, since the integrality gap is \(3\)) to an approximation factor of \(2\)!
The factor \(2\) approximation then establishes a \(2/3\)-approximation for our final algorithm, by completely analogous reasoning as above. It remains to show the \(2\)-approximation for the second algorithm.
Hint 1: Induct on the number of edges of \(G\). You wish for some \(x_e\) to be at least \(1/2\) so you can round it up to \(1\) and only scale the objective by a factor of \(2\). If there is an edge \(e\) with \(x_e^* = 0\), use induction to reduce the problem to a smaller graph. You might need to have to solve the LP optimally each time down this iterative reduction, this is okay.
Hint 2: The bad case is then when every \(x_e\) is positive. Complementary slackness comes to the rescue. Compute the exact dual optimal solution. Is this small enough that a \(2\)-approximation to this is quite easy to find?
Solution: We induct on the number of edges in the graph.
(the reader is invited to finish the solution until the author gets around to it 🫣)