complexity and approximability of the markingproblem

Let g be a digraph with positive edge weights as well as s and t be two vertices of g. the marking problem (mp) states how to mark some edges of g with t and f, where every path starting at source s will reach target t and the total weight of the marked edges is minimal. when traversing the digraph, t-marked edges should be followed while fmarked edges should not. the basic applications and properties of the marking problem have been investigated in [1]. this paper provides new contributions to the marking problem as follows: (i) the mp is np-complete even if the underlying digraph is an unweighted binary dag; (ii) the mp cannot be approximated within α logn in an unweighted dag with n vertices and even in an unweighted binary dag. furthermore, a lower bound to the optimal solution of the mp is provided. we also study the complexity and challenges of the marking problem in program flow graphs.