Approximately counting paths and cycles in a graph

DOI10.1016/j.dam.2016.09.002zbMath1358.05140OpenAlexW2522462178MaRDI QIDQ516844

Masaki Yamamoto

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.002

zbMATH Keywords

inapproximabilityapproximate countingFPRAS\(\#\mathrm{P}\)-hard

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Counting substrate cycles in topologically restricted metabolic networks, Unnamed Item

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• An approximation trichotomy for Boolean \#CSP
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Counting trees in a graph is \(\# \text{P}\)-complete
• The relative complexity of approximate counting problems
• Counting independent sets up to the tree threshold
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Polynomial-Time Approximation Algorithms for the Ising Model
• On Counting Independent Sets in Sparse Graphs
• Approximating the Permanent
• The Complexity of Enumeration and Reliability Problems
• On Markov Chains for Independent Sets
• On Unapproximable Versions of $NP$-Complete Problems