Complexity and approximability of the marking problem

Abstract

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.