Approximation algorithms for constructing some required structures in digraphs

•We consider a new problem of constructing some required structures in digraphs.•The objective is to minimize the number of pieces of a specific material with length L.•Up to now, it is the first time to consider this new model.•We design four (asymptotic) approximation algorithms to construct the two structures.•We propose two conjectures for these required structures in digraphs.

We consider a new problem of constructing some required structures in digraphs, where all arcs installed in such required structures are supposed to be cut from some pieces of a specific material of length L. Formally, we consider the model: a digraph D = (V, A; w), a structure S and a specific material of length L, where w: A → R+, we are asked to construct a subdigraph D′ from D, having the structure S, such that each arc in D′ is constructed by a part of a piece or/and some whole pieces of such a specific material, the objective is to minimize the number of pieces of such a specific material to construct all arcs in D′.For the two required structures: (1) a directed path from a node s to a node t and (2) a strongly connected spanning subdigraph, we design four approximation algorithms with constant performance ratios to solve the both problems, respectively.