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}$$ 3 2 -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}$$ 3 2 -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.