Complexity and approximability of the marking problem

Mohammad Valizadeh, Mohammad Hesam Tadayon


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.


Marking problem, Reachability, Approximability, Complexity, Feasibility

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.