Faster algorithms for quantitative verification in constant treewidth graphs

DOI10.1007/978-3-319-21690-4_9MaRDI QIDQ1702915zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Andreas Pavlogiannis

Publication date 1 March 2018

Full work available at URL https://arxiv.org/abs/1504.07384, https://repository.ist.ac.at/319/1/long.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)

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 $epsilon$ in time $O(ncdotlog(n/epsilon))$ 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(ncdotlog(|acdotb|))=O(ncdotlog(ncdotW))$, when the output is $fracab$, as compared to the previously best known algorithm with running time $O(n^{2}cdotlog(ncdotW))$. Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in $O(n^{2}cdotm)$ time and the associated decision problem can be solved in $O(ncdotm)$ time, improving the previous known $O(n^{3}cdotmcdotlog(ncdotW))$ and $O(n^{2}cdotm)$ bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires $O(ncdotlogn)$ time, improving the previous known $O(n^{4}cdotlog(ncdotW))$ bound.

Recommendations

• Faster algorithms for quantitative verification in bounded treewidth graphs
• Algorithms for algebraic path properties in concurrent systems of constant treewidth components
• Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth
• Faster algorithms for mean-payoff games
• scientific article; zbMATH DE number 7204576

Cited in

(6)

• Treewidth in Verification: Local vs. Global
• Efficient interprocedural data-flow analysis using treedepth and treewidth
• Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth
• Faster algorithms for quantitative verification in bounded treewidth graphs
• Automated competitive analysis of real-time scheduling with graph games
• Algorithms for algebraic path properties in concurrent systems of constant treewidth components

This page was built for publication: Faster algorithms for quantitative verification in constant treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702915)