×

Empirical analysis of algorithms for the shortest negative cost cycle problem. (English) Zbl 1401.05276

Summary: In this paper, we empirically profile three algorithms for the shortest negative cost cycle (SNCC) problem. In this problem, we are given a directed, weighted graph \(G = \langle V, E, c \rangle\), and the goal is to identify a negative cost cycle with the fewest number of edges. The SNCC problem finds applications in a number of domains ranging from program verification to certifying algorithm design. The first polynomial time algorithm for this problem was proposed in [K. Subramani, J. Autom. Reasoning 43, No. 2, 121–137 (2009; Zbl 1184.68468)]. Since then, several additional techniques, including a randomized approach, have been proposed for the SNCC problem. Our goal in this paper is to analyze three algorithmic paradigms for this problem from the empirical perspective. Towards this end, we profile these algorithmic approaches over a wide range of inputs. Our results indicated that the randomized algorithm is the algorithm of choice over a number of graph classes.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C22 Signed and weighted graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)

Citations:

Zbl 1184.68468

Software:

DIMACS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, J. Comput. Syst. Sci., 47, 3, 549-595, (1993) · Zbl 0795.68131
[2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms, (2009), The MIT Press: The MIT Press Cambridge, MA · Zbl 1187.68679
[3] S. Cotton, E. Asarin, O. Maler, P. Niebert, Some progress in satisfiability checking for difference logic, in: FORMATS/FTRTFT, 2004, pp. 263-276.; S. Cotton, E. Asarin, O. Maler, P. Niebert, Some progress in satisfiability checking for difference logic, in: FORMATS/FTRTFT, 2004, pp. 263-276. · Zbl 1109.68513
[4] S. Cotton, O. Maler, Fast and flexible difference constraint propagation for dpll(t), in: SAT, 2006, pp. 170-183.; S. Cotton, O. Maler, Fast and flexible difference constraint propagation for dpll(t), in: SAT, 2006, pp. 170-183. · Zbl 1187.68537
[5] P. Cousot, R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: POPL, 1977, pp. 238-252.; P. Cousot, R. Cousot, Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints, in: POPL, 1977, pp. 238-252.
[6] L. de Moura, S. Owre, H. Ruess, J.M. Rushby, N. Shankar, The ICS decision procedures for embedded deduction, in: IJCAR, 2004, pp. 218-222.; L. de Moura, S. Owre, H. Ruess, J.M. Rushby, N. Shankar, The ICS decision procedures for embedded deduction, in: IJCAR, 2004, pp. 218-222. · Zbl 1126.68575
[7] C. Demetrescu, A. Goldberg, D. Johnson, 9th DIMACS implementation challenge -Shortest Paths, 2005, http://www.dis.uniroma1.it/ challenge9/; C. Demetrescu, A. Goldberg, D. Johnson, 9th DIMACS implementation challenge -Shortest Paths, 2005, http://www.dis.uniroma1.it/ challenge9/
[8] Durstenfeld, R., Algorithm 235: Random permutation, Commun. ACM, 7, 7, 420, (1964), URL http://doi.acm.org/10.1145/364520.364540
[9] J. Ford, N. Shankar, Formal verification of a combination decision procedure, in: CADE, 2002, pp. 347-362.; J. Ford, N. Shankar, Formal verification of a combination decision procedure, in: CADE, 2002, pp. 347-362. · Zbl 1072.68570
[10] C.C. Han, K.J. Lin, Job scheduling with temporal distance constraints, Tech. Rep. UIUCDCS-R-89-1560, University of Illinois at Urbana-Champaign, Department of Computer Science, 1989.; C.C. Han, K.J. Lin, Job scheduling with temporal distance constraints, Tech. Rep. UIUCDCS-R-89-1560, University of Illinois at Urbana-Champaign, Department of Computer Science, 1989.
[11] Levi, S. T.; Tripathi, S. K.; Carson, S. D.; Agrawala, A. K., The hard real-time operating system, ACM Spec. Interest Group Oper. Syst., 23, 3, 90-106, (1989)
[12] Orlin, J. B.; Subramani, K.; Wojciechowski, P., Randomized algorithms for finding the shortest negative cost cycle in networks, Discrete Appl. Math., 236, 1, 387-394, (2018) · Zbl 1377.05181
[13] Papadimitriou, C. H., Computational Complexity, (1994), Addison-Wesley: Addison-Wesley New York · Zbl 0833.68049
[14] Pinedo, M., Scheduling: Theory, Algorithms, and Systems, (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 1145.90393
[15] J.M. Rushby, Tutorial: Automated formal methods with pvs, sal, and yices, in: SEFM, 2006, p. 262.; J.M. Rushby, Tutorial: Automated formal methods with pvs, sal, and yices, in: SEFM, 2006, p. 262.
[16] Seshia, S.; Bryant, R. E., Deciding quantifier-free Presburger formulas using parameterized solution bounds, Log. Methods Comput. Sci., 1, 2, (2005) · Zbl 1125.03010
[17] S.A. Seshia, S.K. Lahiri, R.E. Bryant, A hybrid sat-based decision procedure for separation logic with uninterpreted functions, in: DAC, 2003, pp. 425-430.; S.A. Seshia, S.K. Lahiri, R.E. Bryant, A hybrid sat-based decision procedure for separation logic with uninterpreted functions, in: DAC, 2003, pp. 425-430.
[18] Stankovic, J. A.; Ramamritham, K., Hard Real-Time Systems, (1988), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos
[19] Subramani, K., A comprehensive framework for specifying clairvoyance, constraints and periodicty in real-time scheduling, Comput. J., 48, 3, 259-272, (2005)
[20] Subramani, K., An analysis of totally clairvoyant scheduling, J. Sched., 8, 2, 113-133, (2005) · Zbl 1154.90493
[21] Subramani, K., Optimal length resolution refutations of difference constraint systems, J. Automat. Reason. (JAR), 43, 2, 121-137, (2009) · Zbl 1184.68468
[22] Subramani, K.; Williamson, M.; Gu, X., Improved algorithms for optimal length resolution refutation in difference constraint systems, Form. Asp. Comput., 25, 2, 319-341, (2013) · Zbl 1259.68261
[23] Tseitin, G., On the complexity of derivation in propositional calculus, (Studies in Constructive Mathematics and Mathematical Logic, (1970)), 115-125
[24] Williamson, M. D.; Subramani, K., A parallel implementation for the negative cost girth problem, Int. J. Parallel Program., 43, 2, 240-259, (2015)
[25] Williamson, M. D.; Subramani, K., On the negative cost girth problem in planar networks, J. Discrete Algorithms, 35, 40-50, (2015) · Zbl 1343.05144
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.