Making problem: A new approach to reachability assurance in digraphs

Document Type : Article


1 Iran Telecommunication Research Center (ITRC), Tehran, Iran

2 Faculty of Computer Engineering, Amirkabir University of Technology, Tehran, Iran


Let G be a weighted digraph and s and t be two vertices of G. The reachability assurance (RA) problem is how to label the edges of G such that every path starting at s finally reaches t and the sum of the weights of the labeled edges, called the RA cost, is minimal. The common approach to the RA problem is pathfinding, in which a path is sought from s to t and then the edges of the path are labeled. This paper introduces a new approach, the marking problem (MP), to the RA problem. Compared to the common pathfinding approach, the proposed MP approach has a lower RA cost. It is shown that the MP is NP-complete, even when the underlying digraph is an unweighted directed acyclic graph (DAG) or a weighted DAG with an out-degree of two. An appropriate heuristic algorithm to solve the MP in polynomial time is provided. To mitigate the RA problem as a serious challenge in this area, application of the MP in software testing is also presented. By evaluating the datasets from various program flow graphs, it is shown that the MP is superior to the pathfinding in the context of test case generation.


Corrigendum to: “Making problem: A new approach to reachability assurance in digraphs”[Scientia Iranica 25(3) (2018) 1441-1455]

DOI: 10.24200/sci.2018.21196


Main Subjects

Corrigendum to: “Making problem: A new approach to reachability assurance in digraphs”[Scientia Iranica 25(3) (2018) 1441-1455]

DOI: 10.24200/sci.2018.21196

1. Yu, J.X. and Cheng J. Graph reachability queries:
A survey", In Managing and Mining Graph Data,
Springer, pp. 181-215 (2010).
2. Agrawal, R., Borgida, A., and Jagadish, H.V. E-
cient management of transitive relationships in large
data and knowledge bases", In SIGMOD, 18(2), pp.
253-262 (1989).
3. Nuutila, E. Ecient transitive closure computation
in large digraphs", PhD Thesis, Finnish Academy of
Technology (1995).
4. van Schaik, S.J. and de Moor, O. A memory ecient
reachability data structure through bit vector compression",
Proceedings of the ACM SIGMOD International
Conference on Management of Data, SIGMOD 2011,
Athens, Greece, pp. 913-924 (12-16 June 2011)
5. Tril, S. and Leser, U. Fast and practical indexing and
querying of very large graphs", In SIGMOD'07 (2007).
6. Yildirim, H., Chaoji, V., and Zaki, M.J. Grail:
Scalable reachability index for large graphs", PVLDB,
3(1), pp. 276-284 (2010).
7. Juping, W. Discussion of graph reachability query
with keyword and distance constraint", IDEAL-2016,
pp. 293-301 (2016).
8. Ammann, P. and O utt, J., Introduction to Software
Testing, First Ed., Cambridge University Press, 120 p.
9. Sharma, P. and Khurana, N. Study of optimal path
nding techniques", Int. J. Adv. Technol., 4(2), pp.
124-130 (2013)
M. Valizadeh et al./Scientia Iranica, Transactions D: Computer Science & ... 25 (2018) 1441{1455 1455
10. Dellin, C. and Srinivasa, S. A unifying formalism for
shortest path problems with expensive edge evaluations
via lazy best- rst search over paths with edge
selectors", ICAPS-2016, London, UK (2016).
11. Anand, S., Burke, E., Chen, T.Y., Clark, J., Cohen,
M.B., Grieskamp, W., Harman, M., Harrold, M.J., and
McMinn, P. An orchestrated survey on automated
software test case generation", Journal of Systems and
Software, 86(8), pp. 1978-2001 (2013).
12. Do, T., Khoo, S.C., Fong, A.C.M., Pears, R., and
Quan, T.T. Goal-oriented dynamic test generation",
Information and Software Technology, 66, pp. 40-57
13. Saito, N. and Nishizeki, T. Graph theory and algorithms",
17th Symposium of Research Institute of
Electrical Communication, Tohoku University, Sendai,
Japan (1980).
14. Prosser, R.T. Applications of Boolean matrices to the
analysis of
ow diagrams", AFIPS Joint Computer
Conferences, Eastern Joint IRE-AIEE-ACM Computer
Conference (Boston, MA: ACM), pp. 133-138
15. Aho, A.V., Lam, M.S., Sethi, R., and Ullman, J.D.,
Compilers, Principles, Techniques, and Tools, the 2nd
Ed., Pearson Addison Wesley, pp. 659-666 (2007).
16. Karp, R.M. Reducibility among combinatorial problems",
In R.E. Miller and J.W. Thatcher (Eds.),
Complexity of Computer Computations, New York:
Plenum, pp. 85-103 (1972).
17. Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein,
C., Introduction to Algorithms, 2nd Ed., MIT Press
and McGraw-Hill, ISBN 0-262-03293-7 (2001).
18. Fraczak, W., Georgiadis, L., Miller, A., and Tarjan,
R.E. Finding dominators via disjoint set union",
Journal of Discrete Algorithms, 23, pp. 2-20 (2013).
19. Fredman, M.L. and Tarjan, R.E. Fibonacci heaps
and their uses in improved network optimisation algorithms",
Journal of the ACM, 34(3), pp. 596-615
20. Hecht, M.S., Flow Analysis of Computer Programs,
Amsterdam: Elsevier North-Holland (1977).
21. DeMillo, R.A. and O utt, J. Constraint-based automatic
test data generation", IEEE Transactions on
Software Engineering, 17(9), pp. 900-910 (1991).
22. Goldberg, A., Wang, T.C., and Zimmerman, D. Applications
of feasible path analysis to program testing",
In 1994 International Symposium on Software Testing
and Analysis, Seattle, Washington, USA, pp. 80-94