The Complexity of Counting in Sparse, Regular, and Planar Graphs

DOI10.1137/S0097539797321602zbMath0994.68070MaRDI QIDQ2784460

Salil P. Vadhan

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

completenessFibonacci numbersmatchingsindependent setsvertex coverspolynomial interpolation\(\#\mathcal P\)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Some observations on holographic algorithms ⋮ Counting Maximal Independent Sets in Subcubic Graphs ⋮ Sequential Monte Carlo for counting vertex covers in general graphs ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems ⋮ Minimal autocatalytic networks ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Block interpolation: a framework for tight exponential-time counting complexity ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra ⋮ Proof systems and transformation games ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ Algorithms for four variants of the exact satisfiability problem ⋮ On planar Toeplitz graphs ⋮ Holographic reduction, interpolation and hardness ⋮ Closest pair and the post office problem for stochastic points ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ The complexity of complex weighted Boolean \#CSP ⋮ Holographic algorithms by Fibonacci gates ⋮ The complexity of generalized domino tilings ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Holographic algorithms: from art to science ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. ⋮ Holographic reduction for some counting problems ⋮ Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial ⋮ Unnamed Item ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ The complexity of Bayesian networks specified by propositional and relational languages ⋮ Counting minimal transversals of \(\beta\)-acyclic hypergraphs ⋮ Edge flipping in graphs ⋮ Fair cost allocations under conflicts - a game-theoretic point of view - ⋮ Counting independent sets in cocomparability graphs ⋮ Counting Minimal Dominating Sets ⋮ Counting subset repairs with functional dependencies ⋮ Counting polygon triangulations is hard ⋮ The computational complexity of random serial dictatorship ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Counting the number of independent sets in chordal graphs ⋮ Computing cooperative solution concepts in coalitional skill games ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Stochastic enumeration method for counting trees ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Counting models for 2SAT and 3SAT formulae ⋮ A fixed-parameter perspective on \#BIS ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time ⋮ Computational aspects of mining maximal frequent patterns ⋮ Parameterized counting of partially injective homomorphisms ⋮ Counting independent sets in tree convex bipartite graphs ⋮ Maximum box problem on stochastic points ⋮ FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ Using binary patterns for counting falsifying assignments of conjunctive forms ⋮ Dichotomy result on 3-regular bipartite non-negative functions ⋮ Bipartite 3-regular counting problems with mixed signs ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle ⋮ Sampling Eulerian orientations of triangular lattice graphs ⋮ Counting Independent Sets in Claw-Free Graphs ⋮ Counting edge-injective homomorphisms and matchings on restricted graph classes ⋮ ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS ⋮ On counting 3-D matchings of size \(k\) ⋮ Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ On the spectrum and number of convex sets in graphs ⋮ Unnamed Item ⋮ Expected computations on color spanning sets