Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

In this paper, we address the problem of constructing required subgraphs using stock pieces of fixed length (CRS-SPFL, for short), which is a new variant of the minimum-cost edge-weighted subgraph (MCEWS, for short) problem. Concretely, for the MCEWS problem Q, it is asked to choose a minimum-cost subset of edges from a given graph G such that these edges can form a required subgraph $$G'$$G′. For the CRS-SPFL problem $$Q^{\prime }$$Q′, these edges in such a required subgraph $$G'$$G′ are further asked to be constructed by plus using some stock pieces of fixed length L. The new objective, however, is to minimize the total cost to construct such a required subgraph $$G'$$G′, where the total cost is sum of the cost to purchase stock pieces of fixed length L and the cost to construct all edges in such a subgraph $$G'$$G′. We obtain the following three main results. (1) Given an $$\alpha $$α-approximation algorithm to solve the MCEWS problem, where $$\alpha \ge 1$$α≥1 (for the case $$\alpha =1$$α=1, the MCEWS problem Q is solved optimally by a polynomial-time exact algorithm), we design a $$2\alpha $$2α-approximation algorithm and another asymptotic $$\frac{7\alpha }{4}$$7α4-approximation algorithm to solve the CRS-SPFL problem $$Q^{\prime }$$Q′, respectively; (2) When Q is the minimum spanning tree problem, we provide a $$\frac{3}{2}$$32-approximation algorithm and an AFPTAS to solve the problem $$Q^{\prime }$$Q′ of constructing a spanning tree using stock pieces of fixed length L, respectively; (3) When Q is the single-source shortest paths tree problem, we present a $$\frac{3}{2}$$32-approximation algorithm and an AFPTAS to solve the problem $$Q^{\prime }$$Q′ of constructing a single-source shortest paths tree using stock pieces of fixed length L, respectively.