Complexity and approximability of the marking problem

Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
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.

Language:
English
Published:
Journal of Mathematical Extension, Volume:15 Issue: 1, Winter 2021
Pages:
41 to 60
https://www.magiran.com/p2262938