Faster algorithms for quantitative verification in constant treewidth graphs

Chatterjee, K, Ibsen-Jensen, R ORCID: 0000-0003-4783-0389 and Pavlogiannis, A (2015) Faster algorithms for quantitative verification in constant treewidth graphs .

Text minmeancycle.pdf - Author Accepted Manuscript Download (884kB)

Abstract

We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ∈ in time O(n·log(n/∈)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n · log(|a · b|)) = O(n · log(n · W)), when the output is a/b, as compared to the previously best known algorithm with running time O(n<inf>2</inf>·log(n·W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n²·m) time and the associated decision problem can be solved in O(n·m) time, improving the previous known O(n³ ·m·log(n·W)) and O(n² · m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n · log n) time, improving the previous known O(n⁴ · log(n · W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences, Networking and Information Technology R&D (NITRD)
Depositing User:	Symplectic Admin
Date Deposited:	06 Dec 2018 09:11
Last Modified:	07 Apr 2026 08:27
DOI:	10.1007/978-3-319-21690-4_9
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3029588
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.