A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph (Q6558687)

The graphs in this paper are simple and undirected. The aximum Weight Series-Parallel Subgraph (MWSPS) problem is: Given a simple graph \(G(V, E)\) with a nonnegative weight \(w\) defined on edges, find a maximum weight subgraph of \(G\) which is series-parallel for an edge set \(H\subseteq E(G)\), \(w(H) = \sum_{ e\in H} w(e)\). Note that, without loss of generality, one can sum up the weight of multi-edges to reduce the same problem on multigraphs to MWSPS. Also, note that the output is not required to be an induced subgraph of \(G\).\N\NSection 2 presents the notions needed for an algorithm presented in Section 3. Section 4 analyzes the approximation ratio of the algorithm, and concludes in Section 5.\N\NIn a related work, \textit{L. Cai} and \textit{F. Maffray} [ibid. 44, No. 1--3, 139--156 (1993; Zbl 0788.68107)] considered the variant of the problem where a complete weighted simple graph is given, and one wants to find a maximal series-parallel simple graph of minimum weight. He presented a 1.655 approximation for this variant when the input simple graph is a set of points in the plane with their distances as weights. Here, the authors recall the maximum weight series-parallel subgraph problem. The authors' algorithm for MWSPS exploits the fact that a spruce cactus is a series-parallel simple graph.\N\NThe idea for using \(R_T (Q)\) is as follows. The algorithm tries to increase the weight of a maximum spanning tree \(T_j\) by considering inserting spruces and removing tree edges while keeping a spruce cactus. The edges that will be removed from the tree \(T_{j}\) will be \(R_{T_j} (Q)\), where \(Q\) is the vertex set of spruce.\N\NConclusions are worth noting as follows: the authors improve the approximation ratio for the maximum weight series-parallel subgraph problem from 1/2 to 1/2 + 1/60, by building on the framework of the algorithm of \textit{P. Berman} and \textit{V. Ramaiyer} [J. Algorithms 17, No. 3, 381--408 (1994; Zbl 0820.68049)] to get better non-trivial solutions for this maximization problem.\N\NThey use the tried-and-true method of using blocks of very simple structure. Applying the method was not easy, as one has to use blocks of unbounded size. Maybe one can use a completely different approach to this type of maximization problem, i.e. linear programming.\N\NIt is a nice piece of work. Interestingly, many challenging things are provided.