Maximum Series‐Parallel Subgraph

Consider the NP‐hard problem of, given a simple graph G, to find a series‐parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a $\frac{1}{2}$ ‐approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series‐parallel graph on n vertices has at most 2n-3 edges. We present a $\frac{7}{12}$ ‐approximation for this problem and results showing the limits of our approach.