The exponential time complexity of computing the probability that a graph is connected

DOI10.1007/978-3-642-17493-3_19zbMATH Open1253.68176arXiv1009.2363OpenAlexW2210185040MaRDI QIDQ3058703FDOQ3058703

Authors: Thore Husfeldt, Nina Taslaman 

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in Omega(m/ log^2 m) for simple graphs of m edges under the Exponential Time Hypothesis.

Full work available at URL: https://arxiv.org/abs/1009.2363

Recommendations

• scientific article; zbMATH DE number 1263176
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• Computing Network Reliability in Time Polynomial in the Number of Cuts

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Which problems have strongly exponential complexity?
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The Travelling Salesman Problem in Bounded Degree Graphs
• The Complexity of Enumeration and Reliability Problems
• On the computational complexity of the Jones and Tutte polynomials
• Inapproximability of the Tutte polynomial
• The Tutte Polynomial Part I: General Theory
• New upper bound for the \#3-SAT problem
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• A recursive algorithm for finding reliability measures related to the connection of nodes in a graph
• Exponential Time Complexity of Weighted Counting of Independent Sets

Cited In (3)

• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Block interpolation: a framework for tight exponential-time counting complexity
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time

Uses Software

• tutte_bhkk

This page was built for publication: The exponential time complexity of computing the probability that a graph is connected

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