License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.323
URN: urn:nbn:de:0030-drops-53101
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5310/
Go to the corresponding LIPIcs Volume Portal

Harris, David G. ; Sullivan, Francis

Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs

pdf-format:
20.pdf (0.5 MB)

Abstract

The all-terminal reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We show upper bounds on the relative error of three sequential importance sampling algorithms. We use these to create a hybrid algorithm, which selects the best SIS algorithm for a particular graph G and particular coefficient of the polynomial.

This hybrid algorithm is particularly effective when G has low degree. For graphs of average degree < 11, it is the fastest known algorithm; for graphs of average degree <= 45 it is the fastest known polynomial-space algorithm. For example, when a graph has average degree 3, this algorithm estimates to error epsilon in time O(1.26^n * epsilon^{-2}).

Although the algorithm may take exponential time, in practice it can have good performance even on medium-scale graphs. We provide experimental results that show quite practical performance on graphs with hundreds of vertices and thousands of edges. By contrast, alternative algorithms are either not rigorous or are completely impractical for such large graphs.

BibTeX - Entry

@InProceedings{harris_et_al:LIPIcs:2015:5310,
  author =	{David G. Harris and Francis Sullivan},
  title =	{{Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{323--340},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5310},
  URN =		{urn:nbn:de:0030-drops-53101},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.323},
  annote =	{Keywords: All-terminal reliability, sequential importance sampling}
}

Keywords: All-terminal reliability, sequential importance sampling
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI