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

DOI10.1007/978-3-642-17493-3_19MaRDI QIDQ3058703zbMATH OpenOpenAlexFDO

Authors Thore Husfeldt, Nina Taslaman

Publication date 7 December 2010

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• 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
• Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
• Inapproximability of the Tutte polynomial
• New upper bound for the \#3-SAT problem
• On the computational complexity of the Jones and Tutte polynomials
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• The Tutte polynomial. I: General theory
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Which problems have strongly exponential complexity?

Cited in

(2)

• Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time

Describes a project that uses

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)